CODEWITHSUNDEEP
javamethodsrecursion
Matt Andrzejczuk
Matt Andrzejczuk

Reputation: 2066

"return 1" somehow gives me a solution in a Recursive Method

 {
System.out.println (base + " to the " + i + " power =  " + 
                          power(base, i));   
}

    public static double power(double baseNum, int exp) 
    {
        if (exp == 0)
            return 1;
        else
            return baseNum * power(baseNum, --exp); 
    }

Quick question, the method above called "power" somehow returns the solution to an answer when it returns "1". So if I passed the parameters to calculate 2 ^ 5, RETURN 1 somehow turns into 32.0. What exactly is going on here? how does "1" become 32.0?

Upvotes: 0

Views: 129

Answers (7)

Brian L
Brian L

Reputation: 3251

Consider how you would specify the outputs of the function power(base, exp).

For a base b, we specify the following:

power(b, 0) = b^0 = 1
power(b, 1) = b^1 = b
power(b, 2) = b^2 = b * b
power(b, 3) = b^3 = b * b * b
...
power(b, n) = b^n = b * b * ... * b  (n times)

Take note that each time we increase the exponent by one, we multiply the result by b to get the new result. In general, we could generate the entire sequence using these two rules:

  1. b^0 = 1 for all b
  2. b^n = b^(n-1) * b for all positive integers n

These two rules translate directly to the function definition you provide.

public static double power(double baseNum, int exp) 
{
    if (exp == 0)  /* when the exponent is zero, the result is always 1. */
        return 1;
    else           /* otherwise, the power is equal to b^(n-1) * b. */
        return baseNum * power(baseNum, --exp); 
}

When you start with a positive integer exponent, we use rule 2 to calculate the result based on a smaller exponent, until we get to exponent zero - when we know the result should always be 1 (using rule 1).

Finally, a few notes.

  1. In the else clause it would be clearer to simply show a subtraction rather than using a preincrement. That is, consider using:

    return baseNum * power(baseNum, exp - 1); /* exp - 1 instead of --exp */

  2. If exp passed to your function is negative, it will probably crash after recursively calling itself too many times and running out of memory.

  3. If you wanted the function to account for negative indexes, you could still use a recursive call, except reverse our recursion rule so that the exponent moves towards zero:

    public static double power(double base, int exp)
{
    if (exp == 0)
        return 1;
    else if (exp < 0)
        return power(base, exp + 1) / base;
    else
        return power(base, exp - 1) * base;
}

Upvotes: 0

dreamcrash
dreamcrash

Reputation: 51443

Since you already have the answer. See this to learn more about recursion Position 01:47

Upvotes: 1

Hong Zhou
Hong Zhou

Reputation: 649

In recursion, there is one important thing to remember, which is the base case. Every recursion is required to stop at some point of time. It cannot goes on forever.

Thus in the power function, this is the base case.

if (exp == 0)
    return 1;

when exp is 0, it stops. Without it, it will gives stackoverflow!

Upvotes: 0

tckmn
tckmn

Reputation: 59283

else
    return baseNum * power(baseNum, --exp);

That code right there. When one of the power functions is returning 1, it actually was called by this. So it's going to be like:

return baseNum * power(baseNum, --exp);

And the power returned 1, so:

return baseNum * 1;

And baseNum would be 32.0 in that case.

Recursion.

Better explanation: http://pastebin.com/raw.php?i=dHTnSPuY (my comment begin with an @ sign)

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234797

This is, if you'll pardon the pun, the power of recursion. It works like this:

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

Upvotes: 1

Jo&#227;o Silva
Jo&#227;o Silva

Reputation: 91319

Recursion:

power(2, 5)
= 2 * power(2, 4)
== 2 * 2 * power(2, 3)
=== 2 * 2 * 2 * power(2, 2)
==== 2 * 2 * 2 * 2 * power(2, 1)
===== 2 * 2 * 2 * 2 * 2 * power(2, 0)
====== 2 * 2 * 2 * 2 * 2 * 1 (exp == 0)
===== 2 * 2 * 2 * 2 * 2
==== 2 * 2 * 2 * 4
=== 2 * 2 * 8
== 2 * 16
= 32

Upvotes: 3

Matt
Matt

Reputation: 6050

power(2, 5)->2*power(2,4)->2*2*power(2,3)->2*2*2*power(2,2)->2*2*2*2*power(2,1)->2*2*2*2*2*power(2,0)->32.

Upvotes: 1

Related Questions