CODEWITHSUNDEEP
javascriptrecursion
Gwater17
Gwater17

Reputation: 2314

Struggling to grasp Recursion in JavaScript

Right now I'm going through Codecademy's recursion track and I'm confused how to interpret this correct code.

// Create an empty array called "stack"
var stack = []
// Here is our recursive function
function power(base, exponent) {
  // Base case 
  if ( exponent === 0 ) {
    return 1;
  }
  // Recursive case
  else {
    stack[exponent-1] = base * power(base, exponent - 1); //confused by start of this line
    return stack[exponent-1];
  }
}
power(3,3)
console.log(stack) // [3,9,27]

If exponent-1 becomes 2 then 1 then 0, why does 3 become the element at the 0th position in the array rather than at the 2nd position (and so on) ?

I'd really appreciate any help.

Upvotes: 2

Views: 145

Answers (3)

Bergi
Bergi

Reputation: 664444

Notice that there are four different exponents in the execution of this call, one in each scope of the power invocation.

call power(3, 3)
    exponent' = 3
    is not 0
    calls power(3, 2)
        exponent'' = 2
        is not 0
        calls power(3, 1)
            exponent''' = 1
            is not 0
            calls power(3, 0)
                exponent'''' = 0
                is 0
                returns 1
            multiplies the return value by 3
            assigns it to stack[exponent'''-1]: stack[0] = 3
            returns 3
        multiplies the return value by 3
        assigns it to stack[exponent''-1]: stack[1] = 9
        returns 9
    multiplies the return value by 3
    asigns it to stack[exponent'-1]: stack[2] = 27
    returns 27
logs the value of stack

Indeed the stack is built "backwards", after returning from the recursive calls, not before entering them. If you want to have a better representation of the call stack, you can try to add

callstack.push(exponent);

in the first line of your function body. After the execution of your script, the callstack would look like [3, 2, 1, 0] as you might have expected.

Upvotes: 2

Jasen
Jasen

Reputation: 14250

It helps if you write it out in a table:

power(3, 3)   stack[2] = 3 * power(3, 2)
power(3, 2)   stack[1] = 3 * power(3, 1)
power(3, 1)   stack[0] = 3 * power(3, 0)
power(3, 0)   return 1

Then substitute the values:

stack[0] = 3 * 1
stack[1] = 3 * 3
stack[2] = 3 * 9

Upvotes: 0

Shripathi Kamath
Shripathi Kamath

Reputation: 313

On the first pass, exponent is 3, so you will store a value at stack[2]. But that value is not calculated until the recursive call has completed with power(3,2)...power(3, 1).

So the assignment to stack[3-1] is preceded by the one to stack [3-2], which in turn is preceded by the one to stack[3-2]

Upvotes: 2

Related Questions