Standard ML: Iterative vs. Recursive

Question

I'm reading through ML for the Working Programmer and am a bit confused by the author's distinction between iterative and recursive. My understanding was that "recursive" just refers to a function that calls itself. Any function that isn't recursive is iterative (where an iterative algorithm usually involves some kind of looping).

However, in this book, the author will say something like "luckily the obvious recursive solution is iterative." So my understanding of these terms is definitely different from how the author is using them.

Can someone clarify where I'm misunderstanding these terms?

Thanks, bclayman

Answer 1

Iterative means you can express it with a loop. However, generally speaking, a loop is just a special case of recursion. For example, in SML, the loop

while A do B

is literally defined as a syntactic abbreviation for the recursive definition

let fun loop() = if A then (B; loop()) else () in loop() end

That's why "iterative" is not understood as the opposite of "recursive", but as a special case: some recursive definitions are iterative, others are not. More specifically, it is a special case of linear recursion, where the recursive definition is invoked at most once.