How does this recursive function resolve and why does it output what it does

Question

I found myself unable to understand this example of a recursive function:

function foo(i) {
  if (i < 0)
    return;
  console.log('begin:' + i);
  foo(i - 1);
  console.log('end:' + i);
}
foo(3);

The output is:

begin:3
begin:2
begin:1
begin:0
end:0
end:1
end:2
end:3

I understand how normal and nested functions work, and I think the return; here is supposed to exit the function when i gets lower than 0, so when i = -1, the first console.log() didn't show, but why after foo(-1 - 1) we get the output end:0 ?

Answer 1

To understand you must visualize the stack. Let me take you through the execution process:

1. We start by calling foo(3), so i is 3. Since i is not less than 0, log begin:3. Call foo(2)
2. i is now 2. Since i is not less than 0, log begin:2. Call foo(1)
3. i is now 1. Since i is not less than 0, log begin:1. Call foo(0)
4. i is now 0. Since i is not less than 0, log begin:0. Call foo(-1)

5. i is now -1. Since i is less than 0, we return and go up the stack. Continue from where we left off, the second log in foo(0):

   console.log('end:' + i);
   

   end:0 is logged because i is equal to 0. foo(0) has resolved, go up the stack to foo(1)

6. Continue from the second log in foo(1). end:1 is logged because i is equal to 1. foo(1) has resolved, go up the stack to foo(2)
7. Continue from the second log in foo(2). end:2 is logged because i is equal to 2. foo(2) has resolved, go up the stack to foo(3).
8. Continue from the second log in foo(3). end:3 is logged because i is equal to 3. foo(3) has resolved and thus the call is completely resolved.

This will yield:

begin:3 //Step 1
begin:2 //Step 2
begin:1 //Step 3
begin:0 //Step 4
end:0   //Step 5
end:1   //Step 6
end:2   //Step 7
end:3   //Step 8

Now, to answer the question:

but why after foo(-1 - 1) we get the output end:0 ?

We never call foo(-1 - 1) because foo(-1) returns immediately - it's the base case. The reason it starts logging end:i where i is ascending is because execution continues where it left off before you recursed and called foo(i - 1). Consequently, it logs end:i and then calls are resolved.

Answer 2

In fact, the function do stop when i=0 but since foo(i-1) is called before console.log('end:' + i); the output of all the console.log('begin:' + i); are displayed before the end are displayed with the i value.

Indeed, what really happens here is:

• foo(3)
  • i=3 --> display : "begin 3";
  • Call foo(2)
    • i=2 --> display : "begin 2";
    • Call foo(1)
      • i = 1 --> display : "begin 1";
      • Call foo(0)
        • i = 0 --> display : "begin 0";
        • Call foo(-1) --> return
        • Go back to foo(0), display "end 0"
        • End of foo(0)
      • Go back to foo(1), display "end 1"
      • End of foo(1) ...

And so on.