Recursive algorithim...returns a 0, whats wrong with the formula???

hotdogs113 (14)


I'm writing a 3 function program for homework. The first and third functions seem to work fine, but the second does not.

The function is a recursive function that should do x to n power. It works for whatever x is, and only up to the power of 5. After that, it always returns a 0.

Here's the code...any advice would be appreciated.

Function in questions starts at line 18.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# include <iostream>


using namespace std;



//void loop (int x,int n)
//{

	//int Bosco=1;
	//for (int i=1;i<n;i++)
	//	Bosco=Bosco*x;
//cout<<Bosco<<endl;

//}

int rec(int x,int n)
{
	
	if (n==0)
	{return (1);}
	else if (n==1){ return (x);}
	else if (n)
	{return rec ((x*x),n-1);}
	}

float power (int x,int n)
{
	if (n==0){return 1;}
	else if (n==1) {return x;}
	else if (n)
		return power (x*x,n/2);
	else return power (x*x,n/2)*x;
}

int main ()

{ 
	int x;
	int n;
	int a,b;
	
	cout<<"Enter a number"<<endl;
cin>>x;
cout<<"Enter a number"<<endl;
cin>>n;

//loop (x,n);
rec(x,n);
power (x,n);
a=rec (x,n);
b=power (x,n);
cout<<a<<"and"<<b<<endl;

	cout<<"Thanks"<<endl;
}
Last edited on
hamsterman (4538)
Only your first function is good.
What the second one does is not xn, but x2^n (^ is exponentiation. Apparently you can't have nested sup tags here..), so when n=5, 25=32 and for any x!=1, x32 is more than fits in an integer.
The correct way is return rec(x, n-1)*x;
I assume the purpose of the third one is a faster algorithm where x4 is (x2)2, and this should work fine. However, what if you have x6? Then it should be ((x2)*x))2. I suppose that's the purpose of line 34, but it will never be reached, since (n) evaluates to true when n != 0. Did you mean (n%2 == 0)?
Last edited on
hotdogs113 (14)


Hamsterman....odd question here...I put in your recommended change and it worked. I then took the // away and ran the full three functions. Function 1 and 2 were supposed to give the same output.

I then went into function 1 and changed the int i = 1 to i=0, and now they both give the same output. I then double checked and they are giving the correct answer.

Thanks!

The third function....I took it verbatim out of my class notes the professor provided.....and when I put in the test numbers the output seems correct.

When I looked at it again, you are right, the (n) was wrong, it needed the n%==2.

Thanks again...

Last edited on
hotdogs113 (14)


Well interesting development....

When I ran the program with the given input, the last was x=2, n=50.

It goes nuts.......

hamsterman (4538)
integer is 32 bits. 1 for sign (sort of), 31 for the number, so the maximum value you can calculate with these functions is 231. If you feel that you need more, see http://gmplib.org/
hotdogs113 (14)


So do you think my professor is being tricky here?
hamsterman (4538)
You could use long long int to increase the limit to 264..
hotdogs113 (14)


Hm tried that and some other changes, still coming off as 0....
hamsterman (4538)
x also has to be long long int. That's because C++ operators preserve type. int*int will always return int, even if you assign it to long long int. For operator * to return long long int, at least one of it's arguments has to be one too.
hotdogs113 (14)
It works! Thanks alot!
Topic archived. No new replies allowed.