Thread: recursive calls count

1. Member Join Date
May 2010
Posts
30
Rep Power
0 recursive calls count

Hi, i have the following code and I cannot understand how exactly it works:
Java Code:
public static int fibb(int x) {
fibb_calls++;
System.out.println(fibb_calls + ".call: fib(" + x + ")");
if (x < 3) {
System.out.println("returns 1");
return 1;
} else {
System.out.println("value of 'x' at recursive call: " + x);
return fibb(x - 2) + fibb(x - 3);
}
}
have put print output at each line, trying to get what is going on.
The function is first called with a value of 7 and then there are 8 recursive calls.
Here is the output:
Java Code:
0.call: fib(7)
value of 'x' at recursive call: 7
1.call: fib(5)
value of 'x' at recursive call: 5
2.call: fib(3)
value of 'x' at recursive call: 3
3.call: fib(1)
returns 1
4.call: fib(0)
returns 1
5.call: fib(2)
returns 1
6.call: fib(4)
value of 'x' at recursive call: 4
7.call: fib(2)
returns 1
8.call: fib(1)
returns 1
So, after call 3 I have no idea where the zero comes from in 4.call: fib(0)
7-2=5; 5-2=3; 3-2=1; call: fib(1) //1<3, returns 1
I thought it executes in parralel and finaly returns when both calls are exhausted  Reply With Quote

2.  Originally Posted by emosms So, after call 3 I have no idea where the zero comes from in 4.call: fib(0)
Suppose x == 3 in a call to that method; the method calls itself with the value x-3 == 0.

kind regards,

Jos  Reply With Quote

3. Member Join Date
May 2010
Posts
30
Rep Power
0 Ok, but in call 3 the value of 1 is passed (3-2)
call 3 is fibb(1)
then it returns 1 cause 1<3 if statement.
actually have no idea why it becomes 0 then 2, 4, 2, 1
also, cannot understand how
Java Code:
return fibb(x-2) + fibb(x-3);
is evaluated.
It starts calling itself in fibb(x-2), but what the addition of the 2 function calls mean?
It is a tricky test question, from a test preparation samples and I cannot get it.
My guess: // total of 5 calls only
1. fibb(7-2) = 5
2. fibb(5-2) = 3
3. fibb(3-2) = 1, 1<3, return 1;
// does it start to evaluate fibb(x-3) now?
.....
6. fibb(7-3) = 4
....
8. fibb(4-3) = 1, 1<3, return 1;
But there are some strange extra calls:
Java Code:
4.call: fib(0)
returns 1
5.call: fib(2)
returns 1
7.call: fib(2)
returns 1
Best Regards
Last edited by emosms; 06-05-2011 at 09:14 PM.  Reply With Quote

4. Member Join Date
Jan 2011
Posts
67
Rep Power
0  Originally Posted by emosms also, cannot understand how
Java Code:
return fibb(x-2) + fibb(x-3);
is evaluated.
It starts calling itself in fibb(x-2), but what the addition of the 2 function calls mean?
It is a tricky test question, from a test preparation samples and I cannot get it.
My guess: // total of 5 calls only
1. fibb(7-2) = 5
2. fibb(5-2) = 3
3. fibb(3-2) = 1, 1<3, return 1;
// does it start to evaluate fibb(x-3) now?
.....
6. fibb(7-3) = 4
....
8. fibb(4-3) = 1, 1<3, return 1;
But there are some strange extra calls:
Java Code:
4.call: fib(0)
returns 1
5.call: fib(2)
returns 1
7.call: fib(2)
returns 1
I believe those strange extra calls will be coming from the "+ fibb(x - 3)" code in the following calls to fibb:
1. fibb(7-2) = 5
(results in "5.call: fib(2)" fibb(5-3))
2. fibb(5-2) = 3
(results in "4.call: fib(0)" fibb(3-3))

and the last one from the fibb(x - 2) part:
7.call: fib(2)
(from "6.call: fib(4)" fibb(4 - 2))

Hope that helps :)
Last edited by Skiller; 06-05-2011 at 10:12 PM.  Reply With Quote

5. Member Join Date
May 2010
Posts
30
Rep Power
0 alternation

Thx
Seems that A.fibb(x-2) and B.fibb(x-3) kind of alternate:
when A.(5-2) = 3<2; A returns
last value of x is x = 3
- then B.(3-3) = 0 < 2; B returns - call4
But why it doesn't stop then????????????????????

Then somehow again x is x = 5
- B.fib(5-3) = fib(2) - call5
Then somehow x = 7
- B.fib(7-3) = fib(4) - call6
Suddenly lets go back to A.fib(x-2)
- A.fib(4-2) = fib(2) - call7
- A.fib(2-2) or B.fib(2-3), who knows, it just decided to stop - call(8)... I got a similar one on the exam yesterday, I just made some "educated" guess
Last edited by emosms; 06-07-2011 at 10:09 AM.  Reply With Quote

6. Member Join Date
Jan 2011
Posts
67
Rep Power
0 If you are still having trouble understanding what exactly is happening with the recursion it might help to see more information on where/when each instance of fibb is called and ends, if you change the function to something like the following it should give you a better understanding of how it does things.

Java Code:
public static int fibb(int x) {
fibb_calls++;

int fibb_call_ID = fibb_calls;
int return_value = 0;

System.out.println("fibb call " + fibb_call_ID + ": Called with x being " + x);
if (x < 3) {
System.out.println("fibb call " + fibb_call_ID + ": x is less than 3, will return 1");
returnValue = 1;
} else {
System.out.println("fibb call " + fibb_call_ID + ": Calling fibb(" + x + " - 2)");
return_value = fibb(x - 2);
System.out.println("fibb call " + fibb_call_ID + ": Calling fibb(" + x + " - 3)");
return_value += fibb(x - 3);
}

System.out.println("fibb call " + fibb_call_ID + ": Call ending, returning " + return_value);
return return_value;
}
Hope that helps :)  Reply With Quote

7. Expand all function calls on paper:

f(7) == f(5)+f(4) == f(3)+f(2)+f(4) == f(1)+f(0)+f(2)+f(4) == 1+1+1+f(4) ==3+f(2)+f(1) == 3+1+1 == 5

(I hope I got that correct by head)

kind regards,

Jos  Reply With Quote

8. Member Join Date
May 2010
Posts
30
Rep Power
0 thx

Thanks for the suggestions!
Didn't altered the code to get a detailed output, just relaxed 'n sat with a sheet of paper:
Java Code:
0.fib(7)==1.fib(7-2=5)==2.fib(5-2=3)==3.fib(3-2=1<3)==return 1
+ 4.fib(3-3=0<3)==return 1
+ 5.fib(5-3=2<3)              ==return 1
+ 6.fib(7-2=4)==7.fib(4-2=2<3)              ==return 1
+ 8.fib(4-3=1<3)              ==return 1
==       5
###
passed values: 7,5,3,1,0,2,4,2,1,return 5
recursive calls: 8 p.s. it was not easy to post it formatted as I wanted..
Best Regards  Reply With Quote Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•