Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: programming the Fibonacci number

  1. #1
    Junior Member
    Join Date
    Jul 2012
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default programming the Fibonacci number

    the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.

    So I would expect output like this:

    0,1,1,2,3,5...

      private static int fib(int k) {
            if (k < 2) {
                return k;
            }
            return fib(k-1) + fib(k-2);
        }

    If k is equal to 2, fib(k-1) returns 1 and fib(k-2)returns -1 (because after first recursion call, k will equal 1 and 1-2=-1). So when we add 1 + -1, we get 0. Obviously, Im not following something here because what we should have is 1 + 2 to get 3.

    thanks for explanation.


  2. #2
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: programming the Fibonacci number

    Quote Originally Posted by johnmerlino View Post
    ...
    So I would expect output like this:

    0,1,1,2,3,5...
    Well, isn't that what happens when you call the function with values of 0, 1, 2, 3, 4, 5, ...

    (Did you try it?)


    Quote Originally Posted by johnmerlino
    ...If k is equal to 2, fib(k-1) returns 1
    OK! I'm with you so far.

    Quote Originally Posted by johnmerlino
    and fib(k-2)returns -1
    No. According to the code, for k = 1, since that is less than 2, the function returns the value of its argument (returns 1).
    Quote Originally Posted by johnmerlino
    (because after first recursion call, k will equal 1
    Not true. When you call a function (recursively or not) with an int argument, changes the function makes internally with the parameter do not cause changes of the argument back in the calling function. That's fundamental. The calling function is not "sending it k to work with," it is sending it the value of k. The function works on its own copy of the parameter.

    If you have trouble following the code "in your head," try it with pencil and paper. Step through it for k = 2.

    Sometimes it is helpful to make the program tell you what it is working with at each step:
        private static int fib(int k)
        {
            System.out.println("Into fib with k = " + k);
     
            if (k < 2) {
                System.out.println("  fib(" + k + ") returning " + k);
                return k;
            }
     
            System.out.println("In fib(" + k + ") calling fib(" + (k-1) + ")");
            int i1 = fib(k-1);
            System.out.println("  After calling fib(" + (k-1) + ") return value = " +
                    i1 + ", k = " + k);
     
            System.out.println("In fib(" + k + ") calling fib(" + (k-2) + ")");
            int i2 = fib(k-2);
            System.out.println("  After calling fib(" + (k-2) + ") return value = " +
                    i2 + ", k = " + k);
            return i1+i2;
        }

    If you call this with k = 2, you should see
    Into fib with k = 2
    In fib(2) calling fib(1)
    Into fib with k = 1
      fib(1) returning 1
      After calling fib(1) return value = 1, k = 2
    In fib(2) calling fib(0)
    Into fib with k = 0
      fib(0) returning 0
      After calling fib(0) return value = 0, k = 2
    fib(2) = 1


    (Note that I separated the two recursive calls so that I could show the results separately. In java, putting the two calls in a single expression gives the same result that I showed as the expression is evaluated left-to-right.


    Cheers!


    Z
    Last edited by Zaphod_b; July 15th, 2012 at 12:35 AM.

  3. #3
    Junior Member
    Join Date
    Jul 2012
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: programming the Fibonacci number

    Quote Originally Posted by Zaphod_b View Post
    Well, isn't that what happens when you call the function with values of 0, 1, 2, 3, 4, 5, ...

    (Did you try it?)



    OK! I'm with you so far.


    No. According to the code, for k = 1, since that is less than 2, the function returns the value of its argument (returns 1).

    Not true. When you call a function (recursively or not) with an int argument, changes the function makes internally with the parameter do not cause changes of the argument back in the calling function. That's fundamental. The calling function is not "sending it k to work with," it is sending it the value of k. The function works on its own copy of the parameter.

    If you have trouble following the code "in your head," try it with pencil and paper. Step through it for k = 2.

    Sometimes it is helpful to make the program tell you what it is working with at each step:
        private static int fib(int k)
        {
            System.out.println("Into fib with k = " + k);
     
            if (k < 2) {
                System.out.println("  fib(" + k + ") returning " + k);
                return k;
            }
     
            System.out.println("In fib(" + k + ") calling fib(" + (k-1) + ")");
            int i1 = fib(k-1);
            System.out.println("  After calling fib(" + (k-1) + ") return value = " +
                    i1 + ", k = " + k);
     
            System.out.println("In fib(" + k + ") calling fib(" + (k-2) + ")");
            int i2 = fib(k-2);
            System.out.println("  After calling fib(" + (k-2) + ") return value = " +
                    i2 + ", k = " + k);
            return i1+i2;
        }

    If you call this with k = 2, you should see
    Into fib with k = 2
    In fib(2) calling fib(1)
    Into fib with k = 1
      fib(1) returning 1
      After calling fib(1) return value = 1, k = 2
    In fib(2) calling fib(0)
    Into fib with k = 0
      fib(0) returning 0
      After calling fib(0) return value = 0, k = 2
    fib(2) = 1


    (Note that I separated the two recursive calls so that I could show the results separately. In java, putting the two calls in a single expression gives the same result that I showed as the expression is evaluated left-to-right.


    Cheers!


    Z
    thanks for response

  4. #4
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: programming the Fibonacci number

    One thing to mention, calculating terms in the Fibonacci sequence recursively is a bad idea, the resulting program uses too much memory and eventually takes a very long time to run.

    Test class code:

    package algorithms;
     
    import java.math.BigInteger;
     
    public class FibonacciSequence {
     
    	public FibonacciSequence()
    	{}
     
    	public static BigInteger recFibSeq(int num)
    	{
    		if(num <= 2)
    		{
    			return BigInteger.ONE;
    		}
    		else
    		{
    			return recFibSeq(num-1).add(recFibSeq(num-2));
    		}
    	}
     
    	public static BigInteger loopFibSeq(int num)
    	{
     
    		// Declare BigInteger variables for sum, nminus1 and nminus2
    		BigInteger sum = BigInteger.ZERO;
    		// Initialize sum to zero and the others to 1
    		BigInteger minus1 = BigInteger.ONE, minus2 = BigInteger.ONE;
     
    		if( num <= 2)
    		{
    			return BigInteger.ONE;
    		} // x <= 2
    		else
    		{
    			for (int i = 3; i <= num; i++)
    			{
    				// Set sum equal to nminus1 + nminus2
    				sum = minus1.add(minus2);
    				// Set nminus2 equal to nminus1
    				minus2 = minus1;
    				// Set nminus1 equal to sum
    				minus1 = sum;
    			} // for
    		} // else
    		return sum;
    	}
     
     
    	public static void main(String[] args)
    	{
    		int num = 40;
     
    		System.out.println("Shows difference in time between calculating a term in the Fibonacci sequence recursively and with a loop. Calculates the 40th term in the sequence.\n");
     
    		long start = System.currentTimeMillis();
    		System.out.println("Recursive: " + recFibSeq(num));
    		long end = System.currentTimeMillis();
    		System.out.println("Elapsed time: " + (end-start) + "ms.\n");
     
    		start = System.currentTimeMillis();
    		System.out.println("Looped: " + loopFibSeq(num));
    		end = System.currentTimeMillis();
    		System.out.println("Elapsed time: " + (end-start) + "ms.");
    	}
    }

    Output:

    Shows difference in time between calculating a term in the Fibonacci sequence recursively and with a loop. Calculates the 40th term in the sequence.
     
    Recursive: 102334155
    Elapsed time: 8849ms.
     
    Looped: 102334155
    Elapsed time: 0ms.

Similar Threads

  1. The Fibonacci sequence
    By Ryuk_93 in forum Android Development
    Replies: 1
    Last Post: March 26th, 2012, 12:56 PM
  2. Fibonacci series
    By seanman in forum Algorithms & Recursion
    Replies: 4
    Last Post: September 11th, 2011, 01:32 PM
  3. problem to get Fibonacci series- please help.
    By zoala001 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: January 3rd, 2011, 01:10 AM
  4. Fibonacci Spiral Help?
    By cmh0114 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: January 12th, 2010, 09:21 PM
  5. [SOLVED] Problem in generating Fibonacci sequence in java
    By big_c in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 24th, 2009, 09:52 AM

Tags for this Thread