CODEWITHSUNDEEP
javascriptrecursion
seb_kaine
seb_kaine

Reputation: 149

Trouble with recursive javascript code?

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 ?

Upvotes: 6

Views: 125

Answers (5)

Alex
Alex

Reputation: 21766

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]);

Upvotes: 1

Ionică Bizău
Ionică Bizău

Reputation: 113345

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

Upvotes: 12

Tushar
Tushar

Reputation: 87203

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);

Upvotes: 3

Sarjan Desai
Sarjan Desai

Reputation: 3733

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.

Upvotes: 1

Pinguin895
Pinguin895

Reputation: 1011

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');

Upvotes: 1

Related Questions