dwix dwix - 1 month ago 8
Javascript Question

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

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

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.