Results 1 to 11 of 11
  1. #1
    Bgreen7887 is offline Senior Member
    Join Date
    Oct 2010
    Location
    Newark,nj
    Posts
    111
    Rep Power
    0

    Default Fibonacci sequece

    Hey guys just learning recursion!! I have coded that part as follows
    Java Code:
    public class FibonacciSequence {
    	public static void main(String[] args){
    	int sum = 0;
    	int n = 0;
    	
    	System.out.println(FibSeq(5));
    
    
    	}
    	
    	public static long FibSeq( int n){
    		int sum = 0;
    
    if(n < 2){
    	
    		return n;
    		
    		  } else 
    		  
    			return FibSeq(n-1)+FibSeq(n-2);
    			}	
    	}
    now i want to add up the even numbers up to a specific number.
    i know i would have to check to make sure the number is even maybe something like
    Java Code:
     if (n % 2 == 0)
    int sum += n;
    The problem is i dont no if i should add that within the Main or within the method itself.
    GUIDANCE PLEASE:):)

  2. #2
    tashimoto is offline Member
    Join Date
    Sep 2010
    Location
    Oregon, usa
    Posts
    69
    Rep Power
    0

    Default

    This is a good read and might have some clues in it for you: Recursion - Wikipedia, the free encyclopedia

    Hope this helps.
    Chris

    I just looked through your program and ran it. My apologies, I misunderstood what you were asking.

    I would think you would want to put your check within your FibSeq method. Are you adding the even values of each Fibonacci number or the even fib(n)'s??
    Example: fib(n)=value fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8, fib(7)=13, fib(8)=21....
    are you looking for even "n" or an even "value"?? For even n's : the sum would be 1+3+8+21... For even values the sum would be 2+8...
    Last edited by tashimoto; 12-02-2010 at 07:59 PM. Reason: misunderstood question...

  3. #3
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    Do you have to use recursion for this? The question came up the other day and the most straight foward approach is to generate the fib numbers from the start in a for loop and keep a running total of the even ones.

    ---------

    n%2 is how you check for evenness. But it doesn't make sense to redeclare sum the way you do in the snippet posted.

    ---------

    What is the FibSeq() method supposed to do? (better named as fibSeq or something more descriptive). It looks like it is returning the n-th fibonacci number, but then why the sum variable?

  4. #4
    SmilingKey is offline Member
    Join Date
    Dec 2010
    Posts
    19
    Rep Power
    0

    Default

    i think you should use:

    if(n < 2)
    int sum += n;

    into method FibSeq( int n){}


    Also I think you should define sum before main:

    public class FibonacciSequence {
    int sum = 0;
    public static void main(String[] args){

    and delete it from FibSeq(int n) method because every time you enter in this method sum will be reseted (sum=0)

    Something like this. Try it and tell us ^^
    Last edited by SmilingKey; 12-03-2010 at 02:38 PM.

  5. #5
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    i think condition
    if (n % 2 == 0)
    is similar like
    if(n < 2)

    cus 3%2 = 1 -> 2%2 = 1 -> 1%2 = 0
    for values less than 2 this code will enter into if condition.

    2%2 = 0. See mindprod.com.

  6. #6
    SmilingKey is offline Member
    Join Date
    Dec 2010
    Posts
    19
    Rep Power
    0

    Default

    Quote Originally Posted by pbrockway2 View Post
    2%2 = 0. See mindprod.com.
    right, thanks

  7. #7
    Bgreen7887 is offline Senior Member
    Join Date
    Oct 2010
    Location
    Newark,nj
    Posts
    111
    Rep Power
    0

    Default

    ok here's updated code. I still having problem with the adding even numbers.

    Java Code:
    public class FibonacciSequence {
    	static int sum = 0;
    	public static void main(String[] args){
    	int n = 0;
    	int i = 0;
    
        System.out.println(sum);
    
    }
    	public static long FibSeq( int n){
    		 
    		if(n < 2 && n %2==0 ){ // not sure if condition is correct.
    		 	sum += n;
    		 	return n;
    			} else
    		  		return FibSeq(n-1)+FibSeq(n-2);
    }
    
    
    }
    Last edited by Bgreen7887; 12-03-2010 at 05:06 PM.

  8. #8
    tashimoto is offline Member
    Join Date
    Sep 2010
    Location
    Oregon, usa
    Posts
    69
    Rep Power
    0

    Default

    Walk through your code and write on paper the values of your variables and your method calls... (it might help to visualize your method calls as a tree structure)

    For example:

    FibSeq(3)
    n=3
    returns FibSeq(2) + FibSeq(1)

    FibSeq(2)
    n=2
    returns ( FibSeq(1) + FibSeq(0) ) but you still have + FibSeq(1) from previous return when n=3

    now you have 3 calls to FibSeq :
    FibSeq(1) + FibSeq(0) + FibSeq(1)
    where n=1, n=0, n=1
    in your if statement you are returning (and summing) the values of n only when it is less than 2 and divisible by 2 (can you divide 0/2 ?)

    In your current program: For any FibSeq(#), you will always end up with some combination of FibSeq(1)'s and FibSeq(0)'s where n (1 or 0) is returned and/or summed.

    Hope this helps.
    Chris

  9. #9
    Bgreen7887 is offline Senior Member
    Join Date
    Oct 2010
    Location
    Newark,nj
    Posts
    111
    Rep Power
    0

    Default

    Thanks chris your a Kitchen Sink full of Knowledge.. i correct my error on the if statement and it seems to work now..The crazy thing is i guess the numbers get so big say past FibSeq(50) that the cpu just "hangs" after the compile when i try and run it.. I believe furabable gave me a site Project eurler and thats where this comes from. The problem is all the even numbers up to 4MILLION..is that possible for my CPU to handle??

    Java Code:
    public class FibonacciSequence {
    	static long sum = 0;
    	public static void main(String[] args){
    	int n = 0;
    	long i = 0;
    	
    	System.out.println(FibSeq(50));
    	System.out.println(sum);
    }
    	public static long FibSeq( int n){
    		 
    		if(n < 2 ){
    		 return n;
    			} if (n>2 && n % 2 ==0)
    		 	sum += n;
    		  		return FibSeq(n-1)+FibSeq(n-2);
    	}
    	}

  10. #10
    tashimoto is offline Member
    Join Date
    Sep 2010
    Location
    Oregon, usa
    Posts
    69
    Rep Power
    0

    Default

    We did a similar program in Analysis of Algorithms (at OSU its CS325), and we found that as n gets larger the runtime of the program gets larger but at an extremely high rate. Honestly, I can't remember the specifics (I just remember that for whatever formula we coded, the highest input was around 32). What you are seeing is that algorithms that require recursive calls can take a long time to run since the program must first break it down to it's smallest form (in this case Fib(0) + Fib(1) + Fib(0) +... ) and then start summing to up (in this case a whole bunch of 1's and 0's )

    Here's a few of sites that I used when I stumbled (literally!) my way through the Algorithms class:
    Introduction to Complexity Theory/Big O Algorithm Analysis - Wikiversity
    Big O notation - Wikipedia, the free encyclopedia
    Big-O Notation and Algorithm Analysis

    Much Luck! :)
    Chris

    EDIT:
    I just found a really good link that might help you find a solution to your problem: http://www.ics.uci.edu/~eppstein/161/960109.html
    It explains recursion using the Fibonacci Sequence, and also gives ideas of other possible solutions!
    Last edited by tashimoto; 12-03-2010 at 07:38 PM. Reason: Added another link... a GOOD ONE!

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

    Default

    Quote Originally Posted by Bgreen7887 View Post
    Thanks chris your a Kitchen Sink full of Knowledge.. i correct my error on the if statement and it seems to work now..The crazy thing is i guess the numbers get so big say past FibSeq(50) that the cpu just "hangs" after the compile when i try and run it.. I believe furabable gave me a site Project eurler and thats where this comes from. The problem is all the even numbers up to 4MILLION..is that possible for my CPU to handle??
    A recursive evaluation of fib(50) will take ages to complete. Put a System.out.println("in fib"); statement just after the entry of that method and see it run and run and run ... that's one of the reasons for the iterative version or, a bit more advanced, a memoization mechanism to avoid all those multiple calls to the fib method with the same parameter value. Best is to use a closed form formula for this nasty little function.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Fibonacci sequence
    By ŖΫ ỏ Ңόρę in forum New To Java
    Replies: 6
    Last Post: 03-25-2010, 06:59 AM
  2. help with fibonacci
    By likemine in forum New To Java
    Replies: 8
    Last Post: 01-07-2010, 02:32 AM
  3. help with fibonacci problem
    By thekrazykid in forum New To Java
    Replies: 4
    Last Post: 12-12-2008, 10:41 PM
  4. A Fibonacci printing program
    By Java Tip in forum Java Tip
    Replies: 0
    Last Post: 03-28-2008, 07:26 PM
  5. Fibonacci Algorithm
    By susan in forum New To Java
    Replies: 1
    Last Post: 08-07-2007, 04:25 AM

Posting Permissions

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