Recursion with exponents

Question

I am trying to learn recursion through refactoring some simple problems using recursion (rather than traditional loops). I struggled with exponents. I cannot wrap my head around how this works. As far as I can tell no mathematical operation has been defined for what "pow" should do with its parameters. So... how does it "know" what to do with its parameters, mathematically? Can someone help me understand this please? Why does this compute correctly and not end with "return base * ?what-do-I-do-here?"

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

pow(2, 3); //-> 8

Answer 1

All recursion starts at the end, with a “stopper” to keep us from looping forever. In this case, it’s the zero test:

if (exponent === 0) {
    return 1;
}

Well, as we keep recursing by subtracting 1 from the current exponent, which is positive, that condition will eventually be true:

return base * pow(base, exponent - 1);

So, are you satisfied we won’t loop forever? Eventually the exponent will be zero, and we will return 1 and the recursion will stop.

Okay, so now start from that final call and work backwards, reversing the order of operations in your mind:

• We will end when the exponent is 0 by returning 1, so start with 1.

• Go back one recursion. The exponent will then be 1, and the result is base times 1, which is base. Hey, that’s the right answer!

• Okay, go back one more recursion. The exponent will then be 2, and the result will be base times base times 1, or base squared. Hey, that’s the right answer again!

• And I do believe I detect a pattern here: the result is always base multiplied by itself (and also by 1), the same number of times as the value of the exponent, whatever it may be.

And that is indeed what exponentiation means.

Answer 2

There is a little saying that goes

To understand recursion, one must understand recursion.

I would also add that in order to understand recursion, you need to start seeing recursive function calls as a function call, and not a black box of nothingness.

Every good recursive function has a base case, (not to be confused with the parameter base in your function), and this base case is the recursion you must understand, i.e understand how to arrive at the base case.

if (exponent === 0) {
    return 1;
}

The above forms the basis of the function's ability to compute the power.

---

Process of evaluation

• To arrive at the base case, every time the JavaScript runtime encounters a function call, it temporarily places everything its doing on a stack-like data structure, and starts evaluating the function/expression i.e. calls the function.

See What is the difference between an expression and a statement in Python?

• It will repeat this process until it encounters a function call which evaluates to a value in which case it will begin to undo the process.

• It starts with the last thing it placed on the stack, and replace the function call in that thing, with the value it got from calling the function, then once again evaluates this expression down to a value using the process I listed above.

Notice how this process is recursive? I hope you are now beginning to understand

---

The reason your recursive function works is because every time your runtime encounters a recursive function call, it recursively evaluates the function until it reaches the base case, and hopefully the base case is being good and does not recurse anymore, therefore allowing the function to return to the caller.