Recursion Functions

[Dean007]

#include<iostream>//Writing a recursive function that takes the number to the power.

using namespace std;

typedef unsigned short int ushort;
typedef unsigned long int ulong;

ulong exponent(ushort,ushort);

int main()
{

ushort number,power;
ulong result;

cout<<"Enter Base Number: ";
cin>>number;

cout<<"Enter the Power: ";
cin>>power;

result=exponent(number,power);

cout<<result;

char response;
cin>>response;

return 0;
}

ulong exponent(ushort number,ushort power)
{
if (power==1)

return number;

else

return (number*exponent(number,power-1));
}


Hi folks, If u pass in 2 for number and 4 for exponent, you will get 2*exponent(2,3) and u get 2 * 2^3 = 16. But I am pretty sure this is not how the program gets to the answer. Recursion is working behind the scenes here because the exponent function has not been taught to do 2^3 which is 8. So it keeps calling the function and does something but it is not clear to me on what is going on. As the recursion process proceeds, what is happening? I broke my head over this for hours. Glad I found this forum. Thanks a lot.

[Faldrax]

OK, recursion is one of those things that can easily confuse:-)

If you call exponent(2,1) it will see power ==1 and return 2 - simple.
A call to exponent(2,2) will have power >2, so will return 2*exponent(2,(2-1)), so the function exponent calls itself (this is recusion) and calculates exponent(2,1) = 2. The first instance of exponent then returns 2*2 = 4.
As you increse the value of power, the number if times exponent is called increases.
One thing you could do, which might help see what it is doing, is to change exponent as follows to see the sequence of calls.

ulong exponent(ushort number,ushort power)
{
   ulong result; 
   cout << "Enter Power : " << power << endl;
   if (power==1)
      result = number;
   else
      result = (number*exponent(number,power-1));
   cout << "Exit Power : " << power << endl;
   return result;
}

By using a local varaible for the result you can put a cout after the recusion, and should see something like
Enter 3
Enter 2
Enter 1
Exit 1
Exit 2
Exit 3

Note: Recusion is a way to code some problems very 'neatly', but can eat up memory very quickly if you are not careful.
In the modified version of exponent, for example, it has to hold a ulong for each 'level' of recusion - so if power = 3, it needs to store 3 ulongs when calculating the result. If power = 100, that's 100 ulongs.
If the recusive function is more complex, requires more local variables, etc, you can eat memory very quickly!

[Dean007]

Yes I agree about the memory. like u said perfectly, its only for some problems. What I dont understand is how the exponent function calculates anything without a formula? For example, when u pass in 2 for number and 4 for power. It goes to the function definition and accesses the formula and gets 2*exponent(2,3)....What happens at this point? What is the result of exponent(2,3) ? Is it being passed back to main as number = 2 and power =3? If you can write out the process of what is happening, it wud be very helpful.

Thank u so much for your time. I sure will make a contribution to this site someday in return.

[int main]

Just imagene a black box that you call ulong exponen(...)t.

Main throws two arguments through the top. Say 2 and 3.

Now the black box ulong exponen(...) determines whether the power is 1 or not. Three is obviously not 1.

So your black box ulong exponen(...) calculates two times the result of another instance of the same black box (it has nothing to do with clasees but the term seems to explain it quite well). So through the top of the second black box ulong exponen(...) falls 2 and 2. So the second black box calculates 2 times something from a third black box called ulong exponen(...). Again an instance of exponent.
Here, 2 and 1 are dropped in!

Since 1 equals 1 (first condition) the third black box returns 2 to the second black box.

The second black box was waiting for this result from the third black box to finish its 2 times something from that black box. So now we have 2 * 2 = 4.
The second black box returns 4 to the first black box ulong exponen(...) one which in turn calculates 2 *4 = 8 and returns that value to main.

You see, the function creates itself within itself time afte time until the first condition is true.

I hope, that was at least a bit understandable.

int main

[Faldrax]

To write it out another way

exponent(2,4) = 2* exponent (2 ,3)
exponent(2,4) = 2* (2 * exponent (2,2)) //expand call to exponent(2,3)
exponent(2,4) = 2* (2 * (2* exponent(2,1)) //expand call to exponent(2,2)
exponent(2,4) = 2* (2* (2* 2) //exponent(2,1) =2
exponent(2,4) = 16

[z05DSL3A]

As Recursion seems to pop-up every now and then I have started to write an Article on it (I will hopefully have it ready in a few days, time permitting). If anyone wants to suggest any particular aspect of or information about recursion to include please PM me.

[Dean007]

Hi Int Main, Nice nickname!

I drew up your explanation, It worked out!

thanks for the nice explanation

[Dean007]

Faldrax,

Thank you very much. I understand this clearly now. So in a sense the function ulong exponent() keeps calling itself until the first condition (power==1) is met as int main has said. Once that condition is met, all the numbers are multiplied together and returned to main().

So doing int main's example now we get:

Call to exponent(2,3) = 2* exponent (2 ,2)
Call to exponent(2,2) = 2* (2 * exponent (2,1))
Call to exponent(2,1) = 2* (2 * (2) )

Call to exponent(2,3) = 8

Thank you so much everyone!