Results 1 to 8 of 8
  1. #1
    emosms is offline Member
    Join Date
    May 2010
    Posts
    29
    Rep Power
    0

    Default 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

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by emosms View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    emosms is offline Member
    Join Date
    May 2010
    Posts
    29
    Rep Power
    0

    Default

    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 10:14 PM.

  4. #4
    Skiller is offline Member
    Join Date
    Jan 2011
    Posts
    67
    Rep Power
    0

    Default

    Quote Originally Posted by emosms View Post
    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 11:12 PM.
    Currently developing Cave Dwellers, a Dwarf Fortress/Minecraft style game for Android.

  5. #5
    emosms is offline Member
    Join Date
    May 2010
    Posts
    29
    Rep Power
    0

    Default 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 11:09 AM.

  6. #6
    Skiller is offline Member
    Join Date
    Jan 2011
    Posts
    67
    Rep Power
    0

    Default

    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 :)
    Currently developing Cave Dwellers, a Dwarf Fortress/Minecraft style game for Android.

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    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
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    emosms is offline Member
    Join Date
    May 2010
    Posts
    29
    Rep Power
    0

    Default 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

Similar Threads

  1. Recursive and Non-Recursive powersets?
    By csisdifficult in forum New To Java
    Replies: 5
    Last Post: 04-20-2011, 03:45 AM
  2. Making calls from pc
    By ilyaufo in forum Sun Java Wireless Toolkit
    Replies: 1
    Last Post: 05-17-2010, 05:38 PM
  3. Java System Calls
    By jonnytabpni in forum Advanced Java
    Replies: 3
    Last Post: 03-03-2010, 08:04 PM
  4. Controlling method calls
    By bugger in forum New To Java
    Replies: 2
    Last Post: 01-04-2008, 02:14 PM

Posting Permissions

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