How exactly does this recursive function work in JavaScript?

Question

I have the following example of a recursive function, and what I don't understand is the order in which things are happening:

function power(base, exponent) {
  if (exponent == 0)
    return 1;
  else
    return base * power(base, exponent - 1);
}

When does the function return the values, at the end of all the process or each time?

Answer 1

A simple way to visualize what happens in recursion in general is this:

1. a stack of calls to the function is created: this process needs a proper termination condition to end (otherwise you'll have infinite recursion, which is evil)
2. the single results are popped out of the stack: each result is used to calculate the next step, until the stack is empty

I.e. if base=5 and exponent=3, the call stack is (last element on top):

5*(5*(5*1))
5*(5*(5*power(5, 0)))
5*(5*power(5, 1))
5*power(5, 2)
power(5, 3)

then every called function has real parameters and is ready to return a value (first element on top):

5*(5*(5*1))
5*(5*5)
5*25
125

Note that here the functions are calulated in inverse order: first power(5, 0), then power(5, 1), and so on.. After each calulation an element of the stack is released (i.e. memory is freed).

Hope it helps :)

Answer 2

It is generally helpful in understanding recursive functions such as this to work things out like you would in an algebra class. Consider:

power(3, 4) 
= 3 * power(3, 3)
= 3 * (3 * power(3, 2))
= 3 * (3 * (3 * power(3, 1)))
= 3 * (3 * (3 * (3 * power(3, 0))))
= 3 * (3 * (3 * (3 * 1)))
= 3 * (3 * (3 * 3))
...
= 81

Answer 3

The key here is that power is calling itself exactly in the way it could call any other function. So when it does that, it waits for the function to return and uses its return value.

So if you do

var x = power(10, 2);

1. Your call to power will get to this line:

   return base * power(base, exponent - 1)
   

   ...and call power(10, 1), waiting for that to return.

2. The call to power(10, 1) will, of course, get to the line:

   return base * power(base, exponent - 1)
   

   ...and call power(10, 0), waiting for that to return.

3. The call to power(10, 0) will return 1, which is then used by the call in #2 above to complete its work and return 10 * 1 = 10, which will then let your original call in #1 above return the value 10 * 10 = 100.

When seeking to understand things like this, there's nothing quite like walking through the code with a debugger. In this modern world, you have plenty to choose from, many of which may already be on your computer.

Answer 4

For better visualization, just substitute the function call with the function body (may be pseudo code for instance).

function power(base, exponent) {
  if (exponent == 0)
    return 1;
  else
    return base * power(base, exponent - 1);
}

power(5, 3) expands to this

function power(5, 3) {
    // exponent 3 is not 0

    // return 5 * power(5, 3-1)
    return 5 * function power(5, 2) {
        // exponent 2 is not 0

        // return 5 * power(5, 2-1)
        return 5 * function power(5, 1) {
            //exponent 1 is not 0

            // return 5 * power(5, 1-1)
            return 5 * function power(5, 0){
                //exponent 0 is 0
                return 1;
            }
        }
    }
}

Now the picture is clear. It all becomes like below..

// 1
function power(5, 3){
    return 5 * function power(5, 2){
        return 5 * function power(5, 1){
            return 5 * ( function power(5, 0){
                return 1;
            } )
        }
    }
}

// 2
function power(5, 3){
    return 5 * function power(5, 2){
        return 5 * ( function power(5, 1){
            return 5 * 1;
        } )
    }
}

// 3
function power(5, 3){
    return 5 * ( function power(5, 2){
        return 5 * 5 * 1;
    } )
}

// 4
function power(5, 3){
    return ( 5 * 5 * 5 * 1 );
}

// 5
5 * 5 * 5 * 1;

Answer 5

This line and its resolution really trips me up:

return base * power(base, exponent - 1)

I get that the exponent is decremented until it meets the base case, but when you mulitply the base times the recursive function call, I keep thinking "how does the function mulitply the base by itself(the base arguement)?", where is it doing that exactly, because calling base * power(base, exponent - 1) doesn't look like the standard loop contruction. How can it be calling a function with two arguements, how does it know to skip the exponent arguement and multiply the base by the base?

Answer 6

From a mathematical perspective:

let x = base, let n = exponent

x*x^(n-1) = x^n

because

x^1*x^n-1=x^n (exponents of like term adds together)

It is the same as:

base * base*exponent-1.

Answer 7

As with any recursive function, the return from a particular "instance" happens when the return value has been calculated. This means that the recursed versions will then have been calculated.

So if you pass in an exponent of 4, there will be at some point 4 copies of the function being executed at one time.