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

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

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

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 :)

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

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 :)

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

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