Trouble with recursive javascript code?

Question

I have the following code of a simple recursive function in javascript :

function print(text) {
    if (!text) {
        throw 'No text in input !';
    }
    console.log('print : '+text);
}

function stack(msg, stackSize) {
    stackSize++;
    print('Stack Entry '+stackSize);
    if (stackSize < 4) {
        stack(msg, stackSize);
    } else {
        print(msg);
    }
    print('Stack exit '+stackSize);
}

stack('foobar',0);

which produce the following output :

print : Stack Entry 1
print : Stack Entry 2
print : Stack Entry 3
print : Stack Entry 4
print : foobar
print : Stack exit 4
print : Stack exit 3
print : Stack exit 2
print : Stack exit 1

After banging my head on this very trivial code, i still don't get why the stack exit value is decrementing ?

it makes perfect sense, since each call will wait for its child call to finish before printing "stack exit". — Timothy Groote
– Timothy Groote, Commented Oct 2, 2015 at 8:52
Are you expecting stackSize to be shared between every call to stack? It won't be. They each have their own local copy of the variable. — James Thorpe
– James Thorpe, Commented Oct 2, 2015 at 8:53

Ionică Bizău · Accepted Answer · 2015-10-02 09:10:37Z

12

This is how it's executed, and it's actually obvious. When you have recursive functions, think at them like having boxes in boxes in boxes ... in boxes:

 +-------------------------+
 | 1                       |
 |   +-------------------+ |
 |   | 2                 | |
 |   | +----------------+| |
 |   | | 3              || |
 |   | | +-------------+|| |
 |   | | | 4           ||| |
 |   | | +-------------+|| |
 |   | +----------------+| |
 |   +-------------------+ |
 +-------------------------+

First it goes in, and then out:

stackSize: 1
- stackSize: 2
  - stackSize: 3
    - stackSize: 4
    - stackSize: 4
  - stackSize: 3
- stackSize: 2
stackSize: 1

edited Oct 2, 2015 at 9:10

answered Oct 2, 2015 at 8:56

Ionică Bizău

114k95 gold badges311 silver badges490 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Tushar Over a year ago

Nice visual represnentation +1

Ionică Bizău Over a year ago

@Tushar Credits go to my high school computer science teacher–I was also amazed by this representation. :)

seb_kaine Over a year ago

This is great Ionica ... a good drawing is always the best thing you can have to catch the idea !

Ionică Bizău Over a year ago

@seb_kaine Yes, always! Glad to help. :-)

Tushar · Accepted Answer · 2015-10-02 09:05:54Z

What is happening

stackSize is function parameter, so it is stored in the stack, when the function is returning from recursion, the value is accessed from stack, it is the same value that was passed when the function is called.

When returning from the recursive call, the topmost frame from the stack is popped out and the parameter values are read from it. Function parameters are stored on stack which are not shared between two function calls, even when the same function is called recursively.

What you were expecting

You've never declared the variable stackSize so the scope of the variable(parameter) is in the function only. If you declare the variable and don't pass it as parameter, it will be shared.

Following is what you're expecting, because the variable is shared the same value is accessed while returning from the recursive call and same value is returned.

var stackSize = 0;
function print(text) {
  if (!text) {
    throw 'No text in input !';
  }
  console.log('print : ' + text);
}

function stack(msg) {
  stackSize++;
  print('Stack Entry ' + stackSize);
  if (stackSize < 4) {
    stack(msg, stackSize);
  } else {
    print(msg);
  }
  print('Stack exit ' + stackSize);
}

stack('foobar', stackSize);

Pinguin895 · Accepted Answer · 2015-10-02 08:56:42Z

1

each time you call stack you go to a deeper layer in your call stack. You could write it down like this to see the function calls you do:

stack('foobar',0);
    print('Stack Entry 1');
    stack('foobar',1);
        print('Stack Entry 2');
        stack('foobar',2);
            print('Stack Entry 3');
            stack('foobar',3);
                print('Stack Entry 4');
                stack('foobar',4);
                    print('foobar');
                print('Stack exit 4');
            print('Stack exit 3');
        print('Stack exit 2');
    print('Stack exit 1');

answered Oct 2, 2015 at 8:56

Pinguin895

1,0112 gold badges12 silver badges30 bronze badges

Comments

Sarjan Desai · Accepted Answer · 2015-10-02 09:00:23Z

1

Basic of stack is that Last In First Out or First In Last Out which means whatever something is push on stack at last comes out from stack at first and first push comes out on last so when recursive function call for last time, the value is 4 and complete execution then 3rd stack function execute and so on.

edited Oct 2, 2015 at 9:00

answered Oct 2, 2015 at 8:54

Sarjan Desai

3,7332 gold badges21 silver badges32 bronze badges

Comments

Alex · Accepted Answer · 2015-10-02 10:03:19Z

1

As described by @Tushar, the value of stackSize is retrieved from the stack when returning from the recursion call. You can share stackSize between every call by passing it as an array with one element, see my code snippet below:

function print(text) {
  if (!text) {
    throw 'No text in input !';
  }
  console.log('print : ' + text);
}

function stack(msg, stackSize) {
  stackSize[0] ++;
  document.write('Stack Entry ' + stackSize[0] + '<br/>');
  if (stackSize[0] < 4) {
    stack(msg, stackSize);
  } else {
    print(msg);
  }
  document.write('Stack exit ' + stackSize[0] + '<br/>');
}

stack('foobar', [0]);

edited Oct 2, 2015 at 10:03

answered Oct 2, 2015 at 9:05

Alex

21.8k11 gold badges68 silver badges77 bronze badges

4 Comments

Mr Lister Over a year ago

What's with the ?

Alex Over a year ago

I added the  tag to add a carriage return after each output line. I found it the easiest way to quickly format output in a code snippet, but I am open for suggestions if you know a better way of achieving this.

Mr Lister Over a year ago

But why are you writing  instead of  ? It doesn't make sense! The br element doesn't have an end tag!

Alex Over a year ago

changed my example to use   instead of `, see stackoverflow.com/questions/1946426/html-5-is-it-br-br-or-br.

Collectives™ on Stack Overflow

Trouble with recursive javascript code?

5 Answers 5

4 Comments

Comments

Comments

Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

4 Comments

Comments

Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related