Trying to learn recursive functions, but can't wrap my head round it

Question

I'm trying to learn how to use recursive functions, but am not understanding what is happening at all.

function power(base, exponent) {
    return base * power(base, exponent - 1);
};

alert(power(4,4));

I'm getting:

RangeError: Maximum call stack size exceeded.

From the example that I'm going off of, it has:

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

alert(power(4,4));

Could someone explain to me why the if statement is needed? I suspect that I'm missing something.

Answer 1

A recursive function calls itself. That's the definition of it.

This brings a problem: it will indefinitely call itself. So it will go forever which is why you're getting stack overflows.

Instead, you should stop at a certain point. This is where the if clause comes in. When exponent == 0, you don't call the function, but stop the process.

So when executing power(3, 3) it will go like:

   power(3, 3) is equal to:

   3 * power(3, 2)
or 3 * 3 * power(3, 1)
or 3 * 3 * 3 * power(3, 0)
or 3 * 3 * 3 * 1            // no additional calls anymore; can be calculated now

---

Seen from a little different angle:

• power(4, 4) is defined as 4 * power(4, 3) by the function.
• power(4, 3) is defined as 4 * power(4, 2) by the function.
• power(4, 2) is defined as 4 * power(4, 1) by the function.
• power(4, 1) is defined as 4 * power(4, 0) by the function.
• power(4, 0) is defined as 1 by the function.

If you substitute everything into each previous one, you'll obtain:

                         power(4, 4)
equals               4 * power(4, 3)
equals           4 * 4 * power(4, 2)
equals       4 * 4 * 4 * power(4, 1)
equals   4 * 4 * 4 * 4 * power(4, 0)
equals   4 * 4 * 4 * 4 *      1   
equals   256