CODEWITHSUNDEEP
javascriptrecursion
David G
David G

Reputation: 96835

Can someone please explain this recursive JS code to calculate exponents?

I can't understand this recursion even though it's a really simple example. When it goes to power(base, exponent - 1); what is that supposed to do? How are things being multiplied when power keeps getting invoked until exponent equals 0? 

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

Upvotes: 3

Views: 3760

Answers (6)

Tim
Tim

Reputation: 2450

Let's try to explain this with some maths.

f(x,y) = x^y                     # (1) function definition
       = x * x * x * ... * x     # (2) multiply x with itself y times
       = x * (x * x * ... * x)   # (3) rewrite using parentheses for clarity
       = x * (x^(y-1))           # (4) replace the second part by (1) notation
       = x * f(x, y-1)           # (5) replace again by using f(x,y) notation according to (1)

f(x,0) = 1                       # base case: x^0 = 1

Following this you can see that f(x,y) = x * f(x, y-1).

You can also see where

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

comes from, namely the base case that something to the 0th power always equals 1: f(x,0) = 1.

That's how this recursion was derived.

Upvotes: 0

user1106925
user1106925

Reputation:

Assuming the initial call is power(10, 3)...

  v-----first power() call returns base * (result of next power() call)
        v-----second power() call returns base * (result of next power() call)
              v-----third power() call returns base * (result of last power() call)
                   v------result of last power() call returns 1
(10 * (10 * (10 * (1))))
                   ^-----return 1
              ^-----return base * 1 (10)
        ^-----return base * 10 (100)
  ^-----return base * 100 (1000)

Or go down the left, and up the right. Each line is a subsequent call to power() starting with power(10, 3)...

return base * power(base, 2);  // return base * 100 (1000)
return base * power(base, 1);  // return base * 10   (100)
return base * power(base, 0);  // return base * 1     (10)
return 1;                      // return 1             (1)

Upvotes: 2

cHao
cHao

Reputation: 86535

Let's start from the beginning.

Let's say you call power(base, 0). Since exponent is 0, the function returns 1.

Now, let's say you call power(base, 1). Since exponent isn't 0 this time, the function calls power(base, exponent - 1) and multiplies it by base. (That's the key here...it takes the result from the recursive call, and adds its own twist.) Since exponent - 1 = 0, and power(base, 0) is 1, the result is effectively base * 1. Read: base.

Now on to power(base, 2). That ends up being base * power(base, 1). And power(base, 1) is base * power(base, 0). End result: base * (base * 1). Read: base squared.

And so on.

In case it wasn't obvious, by the way, this function will only work with non-negative integer exponents. If exponent is negative, or is even the tiniest bit more or less than a whole number, the function will run "forever". (In reality, you'll more than likely cause a stack overflow, once recursion eats up all of your stack.)

You could fix the function for negative powers with some code like

if (exponent < 0) return 1 / power(base, -exponent);

As for non-integers...there's no good way to solve that other than throwing an exception. Raising a number to a non-integer power makes sense, so you don't want to just truncate the exponent or otherwise pretend they didn't try to do it -- you'd end up returning the wrong answer.

Upvotes: 5

Bojangles
Bojangles

Reputation: 101513

This is similar to Math.pow(); it raises the base argument to the exponent argument.

For example, 2 ^ 4 is 16, so power(2, 4) would return 16. The if() statement checks to see whether the exponent (power) is zero and returns 1 if it is - any number raised to the power 0 equals 1.

The last line

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

Is a recursive function that calls power() from within itself however many times specified by the value in exponent.

I'll try to explain recursion from the bottom up, or "from the middle" shall we say; it's probably easier to understand.

The bottom most call of power() takes 2 and 1 as it's arguments, and will return 1. This return value is then used in the second up call of power(), so this time the arguments passed are 2 and 2, which outputs 4, and so on until the top-most call to power() is passed 2 and 4 which returns 16.

Upvotes: 5

pete
pete

Reputation: 25091

Using a 2^3 example:

power(2, 3);

calls:

function power(2, 3) {
    if (3 === 0) {
        return 1;
    } else {
        return 2 * power(2, 2); //called
    }
}

which leads to:

function power(2, 2) {
    if (2 === 0) {
        return 1;
    } else {
        return 2 * power(2, 1); //called
    }
}

which leads to:

function power(2, 1) {
    if (1 === 0) {
        return 1;
    } else {
        return 2 * power(2, 0); //called
    }
}

which leads to:

function power(2, 0) {
    if (1 === 0) {
        return 1; //returned
    } else {
        return 2 * power(2, -1);
    }
}

which leads to:

function power(2, 1) {
    if (1 === 0) {
        return 1;
    } else {
        return 2 * 1; //returned
    }
}

which leads to:

function power(2, 2) {
    if (2 === 0) {
        return 1;
    } else {
        return 2 * 2; //returned
    }
}

which leads to:

function power(2, 3) {
    if (3 === 0) {
        return 1;
    } else {
        return 2 * 4; //returned
    }
}

which ultimately returns 8, which is 2^3.

Upvotes: 3

dkretz
dkretz

Reputation: 37655

base = 10 power = 3

10 * power(10,2)

10 * 10 * power(10,1)

10 * 10 * 10

maybe ok for positive integers...

Upvotes: 0

Related Questions