Recursion is so powerful. Even with a seemingly small change to the code, the results of a recursive function can be wildly different.
When working with recursive functions, you have a choice of processing a graph top-down, or bottom-up.
Let's look at these two functions. They both traverse through a linked list and print the value of each node.
Examples are in JavaScript, TypeScript.
function linkedListRecursionV1(node: LinkedList) {
console.log(node.value);
if (node.next) linkedListRecursionV1(node.next);
}
function linkedListRecursionV2(node: LinkedList) {
if (node.next) linkedListRecursionV2(node.next);
console.log(node.value);
}They look basically the same, right? Notice that the statements are flipped in the second function.
Assume they both take an argument of type LinkedList, which is a linked list. It has a value property, which is a string, and it may or may not have a next property, which is another LinkedList.
interface LinkedList {
next?: LinkedList;
value: string;
}Such a linked list could look like this JavaScript object:
{
next: {
value: 'banana'
},
value: 'apple'
}The linked list above has two nodes: one with the value "apple" and one with the value "banana".
Let's take a look again at the two functions:
function linkedListRecursionV1(node: LinkedList) {
console.log(node.value);
if (node.next) linkedListRecursionV1(node.next);
}
function linkedListRecursionV2(node: LinkedList) {
if (node.next) linkedListRecursionV2(node.next);
console.log(node.value);
}Both of these functions seem basically the same -- each function calls console.log() with the value of node.value, and checks if node.next exists. If it does, it recursively calls itself with the value of node.next.
Eventually, all of the values of all nodes are printed.
We would expect the output from running these functions on the linked list above to be something like:
"apple"
"banana"
"orange"
That makes sense because we're just:
- going through each node
- printing the value of the node
The only real difference is that each function does these two things in a different order. linkedListRecursionV1 prints the value of the node first, while linkedListRecursionV2 makes the recursive call first.
But, that's a pretty harmless change, right?
Right?
No! It's a huge change. Suppose we called both functions like so:
const linkedList = {
next: {
next: {
value: "coconut",
},
value: "banana",
},
value: "apple",
};
function linkedListRecursionV1(node) {
console.log(node.value);
if (node.next) linkedListRecursionV1(node.next);
}
function linkedListRecursionV2(node) {
if (node.next) linkedListRecursionV2(node.next);
console.log(node.value);
}
console.log("\nTesting linkedListRecursionV1...");
linkedListRecursionV1(linkedList);
console.log("\nTesting linkedListRecursionV2...");
linkedListRecursionV2(linkedList);We would get this output:
Testing linkedListRecursionV1...
apple
banana
coconut
Testing linkedListRecursionV2...
coconut
banana
apple
What gives?!
Well, calling a function recursively makes a big difference depending on where inside the parent context the recursive function is called. This is because, when we recursively call a function, we're pushing it on to the call stack.
Further execution in the parent function halts until the now-top-of-the-call-stack recursive function finishes.
Let's take a look at what happens to the call stack with the first function.
const linkedList = {
next: {
next: {
value: "coconut",
},
value: "banana",
},
value: "apple",
};
function linkedListRecursionV1(node) {
console.log(node.value);
if (node.next) linkedListRecursionV1(node.next);
}
linkedListRecursionV1(linkedList);Let's imagine that our call stack begins with the very first call to the function linkedListRecursionV1:
[ linkedListRecursionV1(linkedList) ]
The first thing that happens in that function is that we call console.log(), so that's pushed to the top of the call stack:
[ console.log() // apple ]
[ linkedListRecursionV1(linkedList) ]
The console.log() call completes, and it's popped off the stack:
[ linkedListRecursionV1(linkedList) ]
Then the first recursive call is pushed on to the stack:
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(linkedList) ]
Notice that the original linkedListRecursionV1() call is still on the stack since it hasn't completed yet!
The first recursive call calls console.log():
[ console.log() // banana ]
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(linkedList) ]
That call to console.log() is popped off, and we reach our second and last recursive call of linkedListRecursionV1():
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(linkedList) ]
The other two previous linkedListRecursionV1() calls have still not completed yet.
The last console.log() statement fires:
[ console.log() // coconut ]
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(linkedList) ]
It's popped off the stack.
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(linkedList) ]
And, would you look at that, the second recursive call completes and is popped off:
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(linkedList) ]
The first recursive call also completes:
[ linkedListRecursionV1(linkedList) ]
And finally the parent call is done.
Let's go through the call stack for the second function. Here it is again:
const linkedList = {
next: {
next: {
value: "coconut",
},
value: "banana",
},
value: "apple",
};
function linkedListRecursionV2(node) {
if (node.next) linkedListRecursionV2(node.next);
console.log(node.value);
}
linkedListRecursionV2(linkedList);We first call the function:
[ linkedListRecursionV2(linkedList) ]
Then, we make the first recursive call:
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(linkedList) ]
Then the second recursive call:
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(linkedList) ]
At this point, we've exhausted all the nodes, and the inner-most recursive call skips making another recursive call! It proceeds to its console.log() statement:
[ console.log(node.value) // coconut ]
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(linkedList) ]
The console.log() call is popped off the stack, and consequently the inner-most recursive call is also popped off the stack:
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(linkedList) ]
The first recursive call's console.log() statement is pushed onto the stack:
[ console.log(node.value) // banana ]
[ linkedListRecursionV1(node.next) ]
[ linkedListRecursionV1(linkedList) ]
It's popped off, and the recursive call that made it is also popped off:
[ linkedListRecursionV1(linkedList) ]
Finally, the original parent call makes its console.log() call:
[ console.log(node.value) // apple ]
[ linkedListRecursionV1(linkedList) ]
It's popped off the stack, and we're back to square one.
[ linkedListRecursionV1(linkedList) ]
Aha! So that's how we get two completely different answers for these very similar functions. One prints forward, and the other prints backward.
apple
banana
coconut
coconut
banana
apple
And, of course, this is not just true for linked lists. It's true for any kind of graph. Take, for example, these functions which process trees:
treeRecursionV1(tree) {
if (tree.children?.length) {
for (const child of tree.children) {
treeRecursionV1(child);
}
}
console.log(tree.value);
}
treeRecursionV2(tree) {
console.log(tree.value);
if (tree.children?.length) {
for (const child of tree.children) {
treeRecursionV2(child);
}
}
}After going through the linked list example, you could see how these tree functions would work essentially in the same way.