# recursive calls count

• 06-05-2011, 08:04 PM
emosms
recursive calls count
Hi, i have the following code and I cannot understand how exactly it works:
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:
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
• 06-05-2011, 08:21 PM
JosAH
Quote:

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
• 06-05-2011, 09:11 PM
emosms
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
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:
Code:

```4.call: fib(0) returns 1 5.call: fib(2) returns 1 7.call: fib(2) returns 1```
Best Regards
• 06-05-2011, 10:08 PM
Skiller
Quote:

Originally Posted by emosms
also, cannot understand how
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:
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 :)
• 06-07-2011, 10:07 AM
emosms
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
• 06-07-2011, 10:56 AM
Skiller
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.

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 :)
• 06-07-2011, 11:00 AM
JosAH
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
• 06-07-2011, 10:54 PM
emosms
thx
Thanks for the suggestions!
Didn't altered the code to get a detailed output, just relaxed 'n sat with a sheet of paper:
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```
:(hi):
p.s. it was not easy to post it formatted as I wanted..
Best Regards