# Need Help on how to write this recursive code

• shermaine80
In summary: The simplifying expression is n * factorial(n - 1). Does that make sense?In summary, to write a recursive code for the integer function power(x,n), you need to check for a stopping condition where n equals 1, and if it is, return x. Otherwise, use a simplifying expression where if n is even, the function calls itself with n/2 and squares the result, and if n is odd, the function calls itself with n-1 and multiplies the result by x. Recursion works by breaking down a problem into smaller, simpler versions of itself until it reaches the stopping condition. To use this recursive function to calculate y(x,n) = x^n + x^(n-1)
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.

Thanks.

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

Last edited:
recursion

shermaine80 said:
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.

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.

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?

shermaine80 said:
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?

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.

## 1. What is recursion and how does it work?

Recursion is a programming technique where a function calls itself repeatedly until a base case is reached. This allows for solving complex problems by breaking them down into smaller, simpler problems.

## 2. Can you give an example of a recursive function?

Sure, here is an example of a recursive function to calculate the factorial of a number:

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

## 3. What are the advantages of using recursion?

Recursion allows for solving complex problems in a simple and elegant manner. It also helps in reducing the amount of code needed and can make code more efficient.

## 4. Are there any disadvantages to using recursion?

One disadvantage of recursion is that it can be memory intensive, as each recursive function call creates a new stack frame. This can lead to stack overflow errors if the recursion is not properly managed.

## 5. How do you know when to use recursion?

Recursion is best suited for problems that can be broken down into smaller, similar problems. It is often used for tasks such as tree traversal, searching and sorting algorithms, and mathematical operations.

• Programming and Computer Science
Replies
11
Views
830
• Programming and Computer Science
Replies
5
Views
1K
• Programming and Computer Science
Replies
2
Views
918
• Programming and Computer Science
Replies
2
Views
1K
• Programming and Computer Science
Replies
53
Views
3K
• Programming and Computer Science
Replies
2
Views
802
• Programming and Computer Science
Replies
5
Views
1K
• Programming and Computer Science
Replies
39
Views
3K
• Programming and Computer Science
Replies
4
Views
915
• Programming and Computer Science
Replies
8
Views
2K