Recursion, computing a number raised to power

Question

public int pow( int x, int y)
{
if(y==0)
return 1;
else
return x*pow(x, y-1);

} can someone please explain how this is raising something to the power?? Sorry I’m a bit confused here 🤦🏻‍♀️

Answer 1

Here's a cleaner version of the code for clarity:

public int pow(int x, int y)
{
if (y == 0)
{
return 1;
}
else
{
return x * pow(x, y - 1);
}
}

Let's call pow() with the arguments 5 and 3, and let's keep following the function, and recursing back, until the exit condition (if (y == 0) ---> return 1) is executed.

pow(x = 5, y = 3)
==> return 5 * pow(5, 2);
pow(x = 5, y = 2)
==> return 5 * pow(5, 1);
pow(x = 5, y = 1)
==> return 5 * pow(5, 0);
return 1

Then it backtracks, working from the callstack bottom to top!
The pow(5, 0) evaluates to 1 (note the return 1) etc

This gives eventually gives:

return 5 * 5 * 5 * 1 = 125 i.e. 5 cubed!

Let me know if you require any further help!

Answer 2

Thank you sooo much! That was very helpful @xan