Results 1 to 4 of 4
  1. #1
    johnmerlino is offline Member
    Join Date
    May 2014
    Posts
    56
    Rep Power
    0

    Default recursion example using fibonacci

    I'm having some difficulty understanding recursion. Example is below:

    Java Code:
    public class Fibonacci {
    
    	private int fibonacci(int n){
    		return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
    	}
    	
    	private void test(){
    		
    		for(int i=0;i<=4; i++){
    			System.out.println(i + " : " + fibonacci(i));
    		}
    		
    	}
    	
    	public static void main(String[] args) {
    		Fibonacci test = new Fibonacci();
    		test.test();
    
    	}
    
            // output
           0 : 0
           1 : 1
           2 : 1 
           3 : 2
           4 : 3
    }
    when i is 4, I don't understand how it produces 3. In my head, it should be producing 1. When fibonacci is called with 4, fibonacci(4 - 1) runs, which calls fibonacci(3), fibonacci(3-1) runs, which calls fibonacci(2), fibonacci(2-1) runs, which calls fibonacci(1), which returns value of 1. In other words, fibonacci(4 - 1) returns 1. Then we evaluate fibonacci(4 - 2), which calls fibonacci(2), fibonacci(2-2) runs, which calls fibonacci(0), which returns 0. So fibonacci(4-2) returns 0. Thus, 1-0=1. Yet the program returns 3. What am I missing about recursion?

  2. #2
    FlipPoker@gmail.com is offline Senior Member
    Join Date
    Mar 2011
    Posts
    103
    Rep Power
    0

    Default Re: recursion example using fibonacci

    You are missing some calls. There are potentially two recursive calls at each step. For example, when fibonacci(3) runs, it calls fibonacci(3-1) + fibonacci(3-2).

  3. #3
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    4,036
    Rep Power
    6

    Default Re: recursion example using fibonacci

    Quote Originally Posted by johnmerlino View Post
    which calls fibonacci(1), which returns value of 1. In other words, fibonacci(4 - 1) returns 1.
    Well, it leads to 1 returning eventually, but remember that there are other calls in the call stack that also need returning. So fibonacci (4-1) is
    really fibonacci(3) which ultimately returns 2. Fibonacci(4-2) is really fibonacci(2) which ultimately returns 1. 2 + 1 = 3.
    So fibonacci (4) = 3.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  4. #4
    johnmerlino is offline Member
    Join Date
    May 2014
    Posts
    56
    Rep Power
    0

Similar Threads

  1. fibonacci
    By rish in forum New To Java
    Replies: 10
    Last Post: 06-18-2014, 03:50 AM
  2. Recursion: Fibonacci Number Question
    By judemartin99 in forum New To Java
    Replies: 10
    Last Post: 10-06-2013, 06:36 PM
  3. Fibonacci using recursion
    By rootsoftheking in forum New To Java
    Replies: 1
    Last Post: 03-02-2011, 08:08 PM
  4. help with fibonacci
    By likemine in forum New To Java
    Replies: 8
    Last Post: 01-07-2010, 03:32 AM
  5. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 07:26 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
  •