Jump to content
  • Advertisement
Sign in to follow this  
TommySauder

Recursion Trouble..

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

If you intended to correct an error in the post then please contact us.

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;
	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));
	}
}

Share this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
To test your understanding:

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?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!