Need Help on how to write this recursive code

[shermaine80]

write recursive code for the following integer function:

power(x,n) is the exponential or power function x^n, where n is the exponent

For example: power(3,4) evaluates 3^4 which is 3 x 3 x 3 x 3 = 81

Expect the integer result to be large(ie in the millions)

explain how recursive code works.

Please help me how to write this code.
Thanks.

 

[haki]

well recusion is a very simple thing - the whole point is that you will be calling the same function again but:
- the function has a condition at which it will not call itself but return
- by each call the paramter should get closer to the condition.

Example: You can define the Factorial function recursively
btw n!=1*2*...(n-1)*(n)
e.g. 3!=1*2*3=6

Now you can get n! = (n-1)!*n

that is 4! = 3! * 4 = 6*4 = 24

ok, soo to calculate n! we would call (n-1)! and multiply with n. But there must also be a stopping condition. That will be 0! = 1, the condition at which the method should return 1, other it should call itself with (n-1) parameter. Enough talk, the function would look like this

Java code:

public long factorial(long n){

if(n == 0){
return 1;
}else{
return factorial(n-1)*n;
}

}

now if you call factorial(3) what whould happen

factorial(3) calls
factotrial(2) calls
factorial(1) calls
factorial(0) returns 1
factorial(1) returns 1*1=1
factorial(2) returns 1*2=2
factorial(3) returns 2*3=6

hope this clears things up, if you understand the following method then you know recursion. For more you can take a look a wikipedia.

http://en.wikipedia.org/wiki/Recursion

 

[Energex42]

recursion

write recursive code for the following integer function:

power(x,n) is the exponential or power function x^n, where n is the exponent

For example: power(3,4) evaluates 3^4 which is 3 x 3 x 3 x 3 = 81

Expect the integer result to be large(ie in the millions)

explain how recursive code works.

Please help me how to write this code.
Thanks.

power(x, 1) is x, which is your "stopping" condition, and it needs to be checked first.

If n is an even number, power(x, n) is equal to power(x, n/2) squared. Otherwise power(x, n) is equal to x times power(x, n - 1).

A recursive function has two sections. The first section contains your "stopping" checks where the function just returns a result without calling itself. The second section contains decomposition code where a simplifying recursive expression is used, eventually reaching the stopping condition.

 

[shermaine80]

Hi Guys,

Thanks a lot! I got another question:

using recursive power function to calculate the equation

y(x,n) = x^n + x^n-1+x^n-2+x^n-3+...x^1 for n>=0

So the program will be something like

int x
long int factorial(int n)
{
if (n >=0)
return(1);
else
return(x * factorial (n-1));
}

may i know what does return (1) actually means?
Please advise. Thanks.

 

[Energex42]

Hi Guys,

Thanks a lot! I got another question:

using recursive power function to calculate the equation

y(x,n) = x^n + x^n-1+x^n-2+x^n-3+...x^1 for n>=0

So the program will be something like

int x
long int factorial(int n)
{
if (n >=0)
return(1);
else
return(x * factorial (n-1));
}

may i know what does return (1) actually means?
Please advise. Thanks.

To compute y(x, n) you just need to figure out the "stopping" condition, and the simplifying expression. The stopping condition is fairly easy, that y(x, 1) is just equal to x. Now for the simplifying expression you can figure that out by yourself.

int factorial(int n) {
if (n == 1) return(1);
else return(n * factorial(n -1));
}

Returning 1 just means that factorial(1) should be 1.