Saturday, June 4, 2011

Fib Sequence with Method

Problem: "The Fibonacci sequence, in which each new term is the sum of the preceding two, was introduced in Ch4, exercise 9. Rewrite the program requested in that exercise, changing the implementation so that your program calls a method "fibonacci(n) to calculate the nth Fibonacci number. In terms of the number of mathematical calculations required, is your new implementation more or less efficient than the one you used in Ch 4?" (Roberts Ch 5, problem 2).

What it looks like when you run:




Here is the code:

/*

/*
* File: FibSequenceMethods.java
* Name: Renee
* Section Leader: 
* -----------------
* The Fibonacci sequence is defined as a sequence of numbers where each integer is the sum of *the two previous integers in the sequence.
* 
* This program prompts the user for an integer N and calls the private, recursive method fib(n) 
* to print out the first "n" digits of the Fibonacci Sequence. 
*/

package ch6_practice;
import acm.program.*;

public class FibSequenceMethods extends ConsoleProgram {
    public void run() {
    println("This program prints the first 'n' digits of the Fibbonacci Sequence.");
         int n = readInt("How many digits do you want to print?");         
         for (int i = 0; i < n; i++) {
          println("Fib of " + i + " is " + fib(i) + ".");
         }
         

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


Here is the old version (not using a private method):
/*
public class FibSequence extends ConsoleProgram {
    public void run() {
        //Getting the first two in the sequence started...
        int n0 = 0;
        int n1 = 1;
        println(n0);
        println(n1);

        //Now kicking off the fun part by changing moving down the variable values; n1 becomes
//n0, n2 becomes n1, and a new n2 value is created.

        for (int i = 2; i < END; i++) {
            int n2 = n1 + n0;
            println(n2);
            n0=n1;
            n1=n2;
        }
    }

    //Private constant; "End" is the the nth number in the Fib sequence displayed.
    private static final double END = 15;
}

In the new version of the program, because the part that actually calculates each entry in the sequence is a separate method call, you can use a recursive method. In other words, when you're trying to find fib(6), you have at your disposal the ability to calculate fib(5) and fib(4) whereas you didn't before. The new version of the program is easier to write because the code looks like the way we coloquially define the fib sequence. However, it is not actually more efficient (there aren't fewer operations) than the old version because to arrive at any integer in the sequence, you have to calculate *all* the previous integers before it. I drew out the operations to calculate fib(6) using both programs, below. New Version:
Old Version:

10 comments:

  1. Recursion is often avoided when the function call queue grows in this tree structure you found out. Even for something linear (like in a factorial), recursion is still a problem. You can, however, encapsulate your for loop inside the private function, which is probably what you'd do for a production code.

    ReplyDelete
  2. So fib() calls itself twice for each of the n calls -- that means that the total number of operations (or time it takes to execute) is on the order of 2^n. That's known as "exponential time" in CS-speak. On top of that, in the run() method, fib() is itself being called n times: so n*2^n execution time, whereas the first version only took something on the order of n operations ("linear time"). So not only is this recursion not more efficient, it is actually decidedly much, much less efficient!

    Challenge(!): How can we fix this without reverting to the old way? One way to make this better is to try to avoid repeating operations you've already done.. here's a hint:
    http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming

    Also, you might want to learn about arrays... :D

    ReplyDelete
  3. Perhaps a better link (same article):
    http://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence

    Enjoy!

    ReplyDelete
  4. One thing you can do to speed up execution and limit recursion depth is to hard code the first 32 Fibonacci numbers. This speeds up the process dramatically!

    ReplyDelete
  5. this link might help you to get an idea of Recursion.

    it explains the relationship of the goldren rule with the fibonacci sequence which helps to program this sequence, using lesser mathematical calculations.

    ReplyDelete
  6. i forgot the link: http://introcs.cs.princeton.edu/java/23recursion/

    this course turns out to be quite the challenge. have fun ;)

    ReplyDelete
  7. Write more, thats all I have to say. Literally, it seems as though you relied on the video
    to make your point. You obviously know what youre talking about, why waste your intelligence on just posting
    videos to your weblog when you could be giving us something informative to read?



    Also visit my web page: honda s2000 for sale company

    ReplyDelete
  8. Sweet blog! I found it while surfing around on Yahoo
    News. Do you have any tips on how to get listed in Yahoo News?
    I've been trying for a while but I never seem to get there! Thanks

    my website; new balance life trnr

    ReplyDelete
  9. Do you mind if I quote a couple of your articles as
    long as I provide credit and sources back to your weblog?
    My website is in the very same niche as yours and my users would really benefit from
    a lot of the information you provide here. Please let me know if this okay with you.
    Many thanks!

    Have a look at my website: stability ball

    ReplyDelete
  10. If you are going for most excellent contents like I do, simply visit this web page daily since it presents
    quality contents, thanks

    Also visit my homepage mazda rx7 for sale cheap

    ReplyDelete