hi!
How this recursive method works?
ex: F(3) : out put is 1
F(6): out put is 7
class Recursion
{
int F(int n){
if ( n <= 1 )
{
return 0;
}
elseif ( n == 2 )
{
return 1;
}
else
{
return F(n-1) + F(n-2)+ F(n - 3);
}
}
publicstaticvoid main(String[]args)
{
Recursion r=new Recursion();
System.out.println("Rec: "+r.F(6));
}
}
> My question is how the mothod calls itself:
> if you can please explain step by step
Here you go:
F(6) =
6
/|\
/ | \
/ | \
/|\
/|\
/|\
/|\
/|\
/|\
/ | \
/ | \
/|\
/|\
/ | \
/ | \
/|\
/|\
543
/|\/|\/|\
/ | \ / | \ 2 1 0
/ | \/ | \|
/|\ 321 (+1)
/|\/|\\
/|\2 1 0 (+1)
/|\|
/|\ (+1)
432
/|\/|\|
/ | \2 1 0(+1)
/ | \\
321(+1)
/|\\
2 1 0 (+1)
|
(+1)
= +1 +1 +1 +1 +1 +1 +1
= 7
And don't ask for the tree where n > 6!
; )
> thank you very much for your help.
You're welcome.
When code is a bit confusing for you, try to add some System.out.println's in it to see what is being called and returned.
Running your code like this:
class Recursion {
int counter = 1;
int F(int n) {
System.out.print("\nRecursive call ("+(counter++)+") --> n="+n);
if(n <= 1 ) {
System.out.print("\treturn 0");
return 0;
} else if(n == 2) {
System.out.print("\treturn 1");
return 1;
} else {
System.out.print("\tcalling: F("+(n-1)+") + F("+(n-2)+")+ F("+(n-3)+")");
return F(n-1) + F(n-2) + F(n-3);
}
}
public static void main(String[]args) {
Recursion r= new Recursion();
System.out.println("\nRec: "+r.F(6));
}
}
produces the followinf output:Recursive call (1) --> n=6calling: F(5) + F(4)+ F(3)
Recursive call (2) --> n=5calling: F(4) + F(3)+ F(2)
Recursive call (3) --> n=4calling: F(3) + F(2)+ F(1)
Recursive call (4) --> n=3calling: F(2) + F(1)+ F(0)
Recursive call (5) --> n=2return 1
Recursive call (6) --> n=1return 0
Recursive call (7) --> n=0return 0
Recursive call (8) --> n=2return 1
Recursive call (9) --> n=1return 0
Recursive call (10) --> n=3calling: F(2) + F(1)+ F(0)
Recursive call (11) --> n=2return 1
Recursive call (12) --> n=1return 0
Recursive call (13) --> n=0return 0
Recursive call (14) --> n=2return 1
Recursive call (15) --> n=4calling: F(3) + F(2)+ F(1)
Recursive call (16) --> n=3calling: F(2) + F(1)+ F(0)
Recursive call (17) --> n=2return 1
Recursive call (18) --> n=1return 0
Recursive call (19) --> n=0return 0
Recursive call (20) --> n=2return 1
Recursive call (21) --> n=1return 0
Recursive call (22) --> n=3calling: F(2) + F(1)+ F(0)
Recursive call (23) --> n=2return 1
Recursive call (24) --> n=1return 0
Recursive call (25) --> n=0return 0
Rec: 7
Good luck.
