The curious case of recursive and iterative processes
Note that the title is not recursion vs. iteration. Usually, the distinction between these two terms is clear-cut: recursion is about functions that call themselves, while iteration is done through looping. That is correct, but here, we specifically refer to the shape of how a function evolves.
What do we mean by the shape of how a function evolves?
Let's say for now that if the shape grows and shrinks, then it is recursive, if it doesn't, then it is an iterative process.
The terminology here might be a bit confusing, but one thing to keep in mind throughout this post is:
recursive function !== recursive process
Which means, what if there are recursive functions that have iterative processes?
Is this a recursive function?
function plus(a, b) {
if (a === 0) {
return b;
} else {
return 1 + plus(a - 1, b);
}
}
function plus(a, b) {
if (a === 0) {
return b;
} else {
return 1 + plus(a - 1, b);
}
}
What about this one?
function plus(a, b) {
if (a === 0) {
return b;
} else {
return plus(a - 1, b + 1);
}
}
function plus(a, b) {
if (a === 0) {
return b;
} else {
return plus(a - 1, b + 1);
}
}
They are both recursive functions alright, but the processes they generate are different. In fact, the second one is what is called a tail-recursive function, but let's not get ahead of ourselves.
Let's say we want to see how plus(2, 3) works with both examples.
With the first function, a is not equal to 0, so we return 1 + plus(a - 1, b). But we first need to compute plus(a - 1, b) for that. So, we go on and call plus with new arguments: plus(1, 3). Again, a is not equal to 0, so we return 1 + plus(a - 1, b). But again, we need to do a recursive call first, so we go on to plus(0, 3). Now the base case holds, and we return b, which is 3. As this function is popped off the stack, the previous function takes this value and adds 1 to it. Our value is now 4. When this one is popped off the stack as well, we're left with the very first function call; it adds 1 to the value it gets, which is 4, and the result is 5. And, we're done. This is good old recursion as we know it.
Here is a visual display of what is just described:
To see the shape more clearly, let's give it different arguments: 5 and 3 this time. The process would look like this:
plus(5, 3)
1 + plus(4, 3)
1 + (1 + plus(3, 3))
1 + (1 + (1 + plus(2, 3)))
1 + (1 + (1 + (1 + plus(1, 3))))
1 + (1 + (1 + (1 + (1 + plus(0, 3)))))
1 + (1 + (1 + (1 + (1 + 3))))
1 + (1 + (1 + (1 + 4)))
1 + (1 + (1 + 5))
1 + (1 + 6)
1 + 7
8
plus(5, 3)
1 + plus(4, 3)
1 + (1 + plus(3, 3))
1 + (1 + (1 + plus(2, 3)))
1 + (1 + (1 + (1 + plus(1, 3))))
1 + (1 + (1 + (1 + (1 + plus(0, 3)))))
1 + (1 + (1 + (1 + (1 + 3))))
1 + (1 + (1 + (1 + 4)))
1 + (1 + (1 + 5))
1 + (1 + 6)
1 + 7
8
Now the grow-and-shrink part is more obvious.
The actual work of adding 1 is done on the way out, so to speak.
With the second example, though, things are a bit different. With this one, note that the final operation is a recursive call, there is no waiting to add 1 like in the other example.
Let's see it again with the same arguments, plus(2, 3).
a is not equal to 0, so we call plus(1, 4).
Once again, a is not equal to 0, so we go on to plus(0, 5).
And now the base case holds, a is 0, so we return b which is 5.
Here's how it goes:
If we were to use 5 and 3:
plus(5, 3)
plus(4, 4)
plus(3, 5)
plus(2, 6)
plus(1, 7)
plus(0, 8)
8
plus(5, 3)
plus(4, 4)
plus(3, 5)
plus(2, 6)
plus(1, 7)
plus(0, 8)
8
So, while the first example has a recursive process, the second one has an iterative process.
The second one is also an example of a tail-recursive function because there is nothing left to do after the recursive call.
Note that the second function is still a recursive function, it calls itself, but it has an iterative process.
Most of these sound like a confusion of terminology, but they eventually make sense.
More information can be found at https://sourceacademy.org/sicpjs/1.2.1, in fact, the example is adapted from one of the exercises. You can also read the section from the original book or watch Brian Harvey's lecture, which dives into the subject at the 17~ minute mark.
The animated GIFs are inspired by Lydia Hallie's JavaScript Visualized series.