dwix - 1 year ago 67
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`
?

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
``````

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.