Geek Answers Handbook

Problem with javascript recursive code?

I have the following simple recursive function code 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 I hit my head with this very trivial code, I still don't get why the stack output value is decreasing ?

+6
source share
5 answers

This is how it is done, and it is actually obvious. When you have recursive functions, think of them as with boxes in drawers in drawers ... in the fields:

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

First he goes in and then he goes out:

  • stackSize: 1
    • stackSize: 2
      • stackSize: 3
        • stackSize: 4
        • stackSize: 4
      • stackSize: 3
    • stackSize: 2
  • stackSize: 1
+12
source

What's happening

stackSize is a functional parameter, so it is stored on the stack when the function returns from recursion, the value is accessed from the stack, this is the same value that was passed when the function was called.

When returning from a recursive call, the top frame from the stack is issued, and the parameter values ​​are read from it. Function parameters are stored on the stack , which are not shared between two function calls, even if the same function is called recursively.

What did you expect

You never declared a variable stackSize , so the scope of the variable (parameter) is only in the function. If you declare a variable and do not pass it as a parameter, it will be split.

Below you expect, because the variable is shared, which refers to the same value when returning from a recursive call and returns the same value.

 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);
+3
source

The base of the stack is Last In First Out or First In Last Out , which means that something clicks on the stack, finally leaves the stack the first and first clicks exit last, so when you call the recursive function for the last time, this value is 4 and completion of execution, and then execution of the third function of the stack, etc.

+1
source

every time you call stack , you go to a deeper level in the call stack. You can write it like this to see function calls:

 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');
+1
source

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

 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]);
+1
source

More articles:


All Articles