#include <iostream>
using namespace std;
unsigned long int Recursive(int, int);
int main()
{
int number;
int power;
unsigned long int answer;
cout << "Enter a number: ";
cin >> number;
cout << "\n\nEnter a power to that number: ";
cin >> power;
cout << "\n\nCalculating...\n";
answer = Recursive(number, power);
cout << "Your answer is: " << answer << "\n";
return 0;
}
unsigned long int Recursive(int number, int power)
{
if (power <= 1)
{
return number*number;
}
else
{
return (Recursive(number, power-1) + Recursive(number, power-2));
}
}
Recursion Trouble..
Author
ok, well I decided to give recursion a shot, and decided to make the user enter a number and a power, and use recursion to solve it...
Ok, I think I'm having a brain fart because i get the recursion part going, but the code to multiply (number * number) x amount of times is messin me up...
Here's the code:
unsigned long int Recursive(int number, int power){ if (power <= 0)return 1; return number*Recursive(number,power-1);}
Author
How does that work? :|
edit: confused how it can return number*function, when function doesnt return anything but 1 or another function.
edit: confused how it can return number*function, when function doesnt return anything but 1 or another function.
The key in designing a recursive algorithm is determining what the stop condition is.
Let's examine the call chain generated by pow_rec(5,3).
The first call, p > 1, so we return 5 * pow_rec(5,2).
When pow_rec(5,2) is called, p > 1, so we return 5 * pow_rec(5,1).
When pow_rec(5,1) is called, p == 1, so we return 5.
We now regress up the call chain back into pow_rec(5,2). It then returns 5 * pow_rec(5,1) = 5 * 5 = 25.
Now we regress again up to pow(5,3). It returns 5 * pow(5,2) = 5 * 25 = 125, which is the correct answer.
void pow_rec(int n, int p){ // if p is one, we return n, because any number to the first // power is of course itself if (p == 1) return n; else { // we do not have the stop condition, so lets do something // which will get us closer to it. // I will use the identity: // n^p = n^(p-1) * n // therefore, return n * pow(n, p - 1); }}Let's examine the call chain generated by pow_rec(5,3).
The first call, p > 1, so we return 5 * pow_rec(5,2).
When pow_rec(5,2) is called, p > 1, so we return 5 * pow_rec(5,1).
When pow_rec(5,1) is called, p == 1, so we return 5.
We now regress up the call chain back into pow_rec(5,2). It then returns 5 * pow_rec(5,1) = 5 * 5 = 25.
Now we regress again up to pow(5,3). It returns 5 * pow(5,2) = 5 * 25 = 125, which is the correct answer.
Try it out on paper with a small power.
When you get down to the bottom level, it returns 1, then it returns 1 * number one level up. Then that result (1 * number) is multiplied by number again = 1 * number * number. Then that goes up a level again, 1 * number * number * number, etc.
number = 2... power = 3
2 * Recurse(2, 3)
2 * Recurse(2, 2)
2 * Recurse(2, 1)
1
= (((1 * 2) * 2) * 2) = 8 = correct
Hopefully that clears it up?
When you get down to the bottom level, it returns 1, then it returns 1 * number one level up. Then that result (1 * number) is multiplied by number again = 1 * number * number. Then that goes up a level again, 1 * number * number * number, etc.
number = 2... power = 3
2 * Recurse(2, 3)
2 * Recurse(2, 2)
2 * Recurse(2, 1)
1
= (((1 * 2) * 2) * 2) = 8 = correct
Hopefully that clears it up?
The return 1 stops the recursion. The function returns number to the power. So number*function(number,power-1) is the same as function(number,power). If that doesn't make sense then you should practice some algebra.
Another example:
int sum(int x)
{
if(x==0)return 0;
return 1+sum(x-1);
}
This works like this
sum(3) returns 1+sum(2)
sum(2) returns 1+sum(1)
sum(1) returns 1+sum(0)
sum(0) = 0
sum(0)+1+1+1 = 3
Another example:
int sum(int x)
{
if(x==0)return 0;
return 1+sum(x-1);
}
This works like this
sum(3) returns 1+sum(2)
sum(2) returns 1+sum(1)
sum(1) returns 1+sum(0)
sum(0) = 0
sum(0)+1+1+1 = 3
Author
gotcha, thanks... just a minor brain fart.
Right when you mentioned algebra it all made sense (I was so involved in getting the right syntax and everything I forgot I needed some math)
Thanks.
Right when you mentioned algebra it all made sense (I was so involved in getting the right syntax and everything I forgot I needed some math)
Thanks.
From the mathematics you get that for x positive, you get:
-> x^0 = 1
-> x^n = x*x**x...x -> n times.(therefor x^1 = x)
From that definition you get some properties:
-> x^a * x^b = x^a+b
from that you can get:
-> x^1 * x^(n-1) = x^n
So with x^0=1, x^1=x and x^n = x^1 * x^(n-1) you have pretty much the recursion you want
-> x^0 = 1
-> x^n = x*x**x...x -> n times.(therefor x^1 = x)
From that definition you get some properties:
-> x^a * x^b = x^a+b
from that you can get:
-> x^1 * x^(n-1) = x^n
So with x^0=1, x^1=x and x^n = x^1 * x^(n-1) you have pretty much the recursion you want
The two important things to do when designing recursive algorithms:
- Determine the stop condition, and what to return when it is reached.
- If the function is called, and it doesn't have the stop condition, determine what can be done to get it closer to having the stop condition.
If you follow these two steps, and make sure you do it correctly, it will almost always naturally work out.
For example, with the power function:
- Any number n to the first power is n. Therefore, if p is 1, we simply return n.
- Observe that n^p = n^(p-1)*n, as vininim pointed out. What is happening in this identity? Well, the result is staying unchanged, but p is approaching 1, which is the stop condition. So if we keep doing this identity, it's inevitable that p will eventually equal 1, which stops the recursion and causes everything to get multiplied together.
- Determine the stop condition, and what to return when it is reached.
- If the function is called, and it doesn't have the stop condition, determine what can be done to get it closer to having the stop condition.
If you follow these two steps, and make sure you do it correctly, it will almost always naturally work out.
For example, with the power function:
- Any number n to the first power is n. Therefore, if p is 1, we simply return n.
- Observe that n^p = n^(p-1)*n, as vininim pointed out. What is happening in this identity? Well, the result is staying unchanged, but p is approaching 1, which is the stop condition. So if we keep doing this identity, it's inevitable that p will eventually equal 1, which stops the recursion and causes everything to get multiplied together.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
