CODEWITHSUNDEEP
javascriptfunctionrecursion
abaracedo
abaracedo

Reputation: 1454

Trying to understand the stack-like behaviour on recursive functions

I'm reading the article about functions on the MDN, and I reached the Recursive part but I don't understand the last part that talks about using the stack-like behavior.

The example is that one:

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

// Output:

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

On that function, I understand when the begin log is shown but I don't when the end log is shown. Can someone help me and explain it me?

Upvotes: 5

Views: 430

Answers (3)

Mik378
Mik378

Reputation: 22181

The end is showed right after EVERY foo(i - 1); has been called and processed.

Basically the process is:

1) calling foo(i)
2) calling foo(i - 1) n times;
Then, when i reaches -1: 3) the deepest stack returns.
4) console.log('end:' + i) n times since it's still part of the function calls until i reaches -1;

Upvotes: 2

Maciej
Maciej

Reputation: 9605

The best way to see it is probably to 'unfold' recursion and write it as sequence of consecutive calls:

foo(3);
begin:3
        foo(2);
        begin:2
                foo(1);
                begin:1
                        foo(0);
                        begin:0
                                foo(-1);
                                return;
                        end:0
                end:1
        end:2
end:3

'end:' strings are printed after reaching deepest recursion

Upvotes: 2

jefffan24
jefffan24

Reputation: 1326

So basically on each call to foo while it does the i-1 it keeps the function open, it hasn't returned. It keeps going hence the begin keeps getting called, once it reaches 0 the last function call returns. Once this happens the other foo calls can start finishing as well. They will finish from oldest to newest.

You can see a visulization of this using loupe by Philip Roberts. Here is a Loupe of your example.

Upvotes: 3

Related Questions