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.

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.

• javascript
• recursion

7 Answers 7

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

You need a base case in recursion so that it stops calling itself. In this case, the power function is called forever (well, until the javascript interpreter gives up) as the exponent goes to negative infinity.

A recursive function calls itself. So you need some mechanism to tell it to stop or you will be in an infinite loop. In your case you always return and provide no means for exiting the loop. Hence the RangeError.

Notice that the function is calling itself. In your first example, the function calls itself, and then the newly called function calls itself and so on. Internally, your computer is storing these function calls in a memory structure called a stack. When there is no more memory for storing function calls, you have exceeded the call stack size.

In the second example, you have a way of escaping this vicious circle. The base case lets the function return, and so you "pop" the method calls off the stack.

Note that in your second example, you can start with alert(power(4, -1)) and you will again experience the same problem, because now your function will subtract one from -1, giving you -2, and so on. You could fortify the code by using

if (exponent <= 0 ) 

... instead.

You have to give it some corner conditions because otherwise it will keep calling itself over and over. Because stack size is limited, it will reach end of stack memory, and then an error will be thrown.

Recursion is actually calling function within its own function body again & again until you get your desired result.

public int FactorialOfNumber(int k) {

    if (k==1)
        return 1;
    else
        return k * FactorialOfNumber(k-1);  //Function called within Function.
}

What happens that Recursion uses stack to operate?

Suppose if k=1, returns 1.

If k=4, control goes to else, returns (4*FactorialOfNumber(3)). since you doesn't know , FactorialOfNumber(3). it stores at top of stack.

now, k=3, control goes to else, it returns (3*FactorialOfNumber(2)). nw this goes to top of stack.

now k=2, returns (2*FactorialOfNumber(1)), top of stack.

Finally it calls i.e pops from stack, finally (4*FactorialOfNumber(3)) is called.

If a recursive method never reaches a base case, The stack will never stop growing. The computer, however, limits the stack to a particular height, so that no program eats up too much memory. If a program's stack exceeds this size, the computer initiates an exception, which typically would crash the program. The exception is labeled a StackOverflowError.

The if creates a check to stop the recursion when the exponent reaches zero. Without it, it will continue with negative values and never stops.