Categories: MSDN / DotNet / Java / Scripts / Linux / PHP Ask - La ask - La Answer

recursive method to comput psF(n)

can someone explain to me how recursive methods work
we went over it in class but i was not listening and now i'am to scared to tell the teacher. :) can't focus for more than 50 mins at a time
how can you use a method within it self

static int psF(int n) {
if(n<2)
return n;
else
return 2*psF(n-1)+psF(n-2);
}

how can he use a method call with in a method
[427 byte] By [Mcody2] at [2007-11-11 9:56:34]
# 1 Re: recursive method to comput psF(n)
Here your fibonacci program
import javax.swing.*;
public class Fibo
{

static long fibo(int n) {
if(n==0) //Stop
return n;
else if (n==1)
return 1;
else
return fibo(n-1)+fibo(n-2);

}
public static void main(String[] args)
{
String stNo=JOptionPane.showInputDialog("Enter n>0: ");
int n=Integer.parseInt(stNo);
JOptionPane.showMessageDialog(null,"Fibonacci number at n "+n+" is "+fibo(n));
}

}
vanduc at 2007-11-11 22:32:12 >
# 2 Re: recursive method to comput psF(n)
can someone explain to me how recursive methods work
we went over it in class but i was not listening and now i'am to scared to tell the teacher. :) can't focus for more than 50 mins at a time
how can you use a method within it self

static int psF(int n) {
if(n<2)
return n;
else
return 2*psF(n-1)+psF(n-2);
}

how can he use a method call with in a method

If you don't understand some code, try putting some System.out.println() statements in it to see what's happening to the variables in your code.
The previous' posters code can even be shortened with only one if-statement:
public class Fibo {

public static int fibonacci(int n) {
System.out.println("********************************************");
System.out.println("Begin of the method, n = "+n);
if(n < 2) {
System.out.println(" - returning: "+n);
return n;
} else {
System.out.println(" - calling fibonacci("+n+"-1)+fibonacci("+n+"-2)");
return fibonacci(n-1)+fibonacci(n-2);
}
}

public static void main(String[] args) {
int N = 4;
System.out.println("\n\nAnswer fibonacci("+N+") = "+fibonacci(N));
}
}
When you run the code the following will be printed:
********************************************
Begin of the method, n = 4,
- calling fibonacci(4-1)+fibonacci(4-2) [1]-+
******************************************** |
Begin of the method, n = 3, |
- calling fibonacci(3-1)+fibonacci(3-2) <--+ [2]-+
******************************************** | |
Begin of the method, n = 2, | |
- calling fibonacci(2-1)+fibonacci(2-2) | <--+ [3]-+
******************************************** | | |
Begin of the method, n = 1, | | |
- returning: 1 | | <--+
******************************************** | | |
Begin of the method, n = 0, | | |
- returning: 0 | | <--+
******************************************** | |
Begin of the method, n = 1, | |
- returning: 1 | <--+
******************************************** |
Begin of the method, n = 2, |
- calling fibonacci(2-1)+fibonacci(2-2) <--+ [4]-+
******************************************** |
Begin of the method, n = 1, |
- returning: 1 <--+
******************************************** |
Begin of the method, n = 0, |
- returning: 0 <--+

Answer fibonacci(4) = 3
I've drawn some arrows to show how the flow of the recursive calls work. As you can see, the number 1 gets returned three times, which is the answer.
Hope it's clear to you now.

Good luck.
prometheuzz at 2007-11-11 22:33:17 >
# 3 Re: recursive method to comput psF(n)
...
The previous' posters code can even be shortened with only one if-statement:
...
If you really want to shorten it, you can even put it all in one line:
public static int fib(int n) {
return n < 2 ? n : fib(n-1)+fib(n-2);
}
; )
prometheuzz at 2007-11-11 22:34:15 >
# 4 Re: recursive method to comput psF(n)
thanks prometheuzz that helped alot, also good advice about inserting print lines i remember reading that in my text somewere thought it was a waste of time lol now i see it is good programming practice.
Mcody2 at 2007-11-11 22:35:14 >