recursion - Trouble with recursive javascript code? - Stack Overflow

admin管理员组

文章数量:1314514

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 ?

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 ?

• javascript
• recursion

Share Improve this question Follow asked Oct 2, 2015 at 8:49 seb_kaineseb_kaine 14988 bronze badges 3

• 3 it makes perfect sense, since each call will wait for its child call to finish before printing "stack exit". – Timothy Groote Commented Oct 2, 2015 at 8:52
• 1 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 Commented Oct 2, 2015 at 8:53
• Is stackSize a local variable in the function stack? – Codor Commented Oct 2, 2015 at 8:53

Add a ment  | 

5 Answers 5

Sorted by: Reset to default 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

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

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

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

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

本文标签： recursionTrouble with recursive javascript codeStack Overflow