Public Group

Recursion Trouble..

This topic is 4796 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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:
#include <iostream>

using namespace std;

unsigned long int Recursive(int, int);

int main()
{

int number;
int power;

cout << "Enter a number: ";
cin >> number;
cout << "\n\nEnter a power to that number: ";
cin >> power;
cout << "\n\nCalculating...\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));
}
}



Share on other sites
unsigned long int Recursive(int number, int power){		if (power <= 0)return 1;	return number*Recursive(number,power-1);}

Share on other sites
How does that work? :|

edit: confused how it can return number*function, when function doesnt return anything but 1 or another function.

Share on other sites
The key in designing a recursive algorithm is determining what the stop condition is.

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.

Share on other sites
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?

Share on other sites
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

Share on other sites
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.

Share on other sites
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

Share on other sites
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.

Share on other sites

Write a function which recursively calculates the factorial of a number.

Remember:

What is the stop condition?
If we don't have it, what can we do to get closer to it?
When we do have it, what do we return?

1. 1
Rutin
44
2. 2
3. 3
4. 4
5. 5

• 10
• 9
• 12
• 10
• 13
• Forum Statistics

• Total Topics
632983
• Total Posts
3009707
• Who's Online (See full list)

There are no registered users currently online

×