Results 1 to 11 of 11
Thread: Fibonacci sequece
 12022010, 05:37 PM #1Senior Member
 Join Date
 Oct 2010
 Location
 Newark,nj
 Posts
 111
 Rep Power
 0
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(n1)+FibSeq(n2); } }
i know i would have to check to make sure the number is even maybe something likeJava Code:if (n % 2 == 0) int sum += n;
GUIDANCE PLEASE:):)
 12022010, 08:28 PM #2Member
 Join Date
 Sep 2010
 Location
 Oregon, usa
 Posts
 69
 Rep Power
 0
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; 12022010 at 08:59 PM. Reason: misunderstood question...
:cool: It's all here: http://download.oracle.com/javase/6/docs/api/
 12022010, 08:40 PM #3Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,708
 Rep Power
 13
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 nth fibonacci number, but then why the sum variable?
 12022010, 11:56 PM #4Member
 Join Date
 Dec 2010
 Posts
 19
 Rep Power
 0
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; 12032010 at 03:38 PM.
 12032010, 02:57 AM #5Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,708
 Rep Power
 13
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.
 12032010, 03:30 PM #6Member
 Join Date
 Dec 2010
 Posts
 19
 Rep Power
 0
 12032010, 06:04 PM #7Senior Member
 Join Date
 Oct 2010
 Location
 Newark,nj
 Posts
 111
 Rep Power
 0
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(n1)+FibSeq(n2); } }
Last edited by Bgreen7887; 12032010 at 06:06 PM.
 12032010, 06:42 PM #8Member
 Join Date
 Sep 2010
 Location
 Oregon, usa
 Posts
 69
 Rep Power
 0
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:cool: It's all here: http://download.oracle.com/javase/6/docs/api/
 12032010, 07:09 PM #9Senior Member
 Join Date
 Oct 2010
 Location
 Newark,nj
 Posts
 111
 Rep Power
 0
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(n1)+FibSeq(n2); } }
 12032010, 08:23 PM #10Member
 Join Date
 Sep 2010
 Location
 Oregon, usa
 Posts
 69
 Rep Power
 0
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
BigO 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; 12032010 at 08:38 PM. Reason: Added another link... a GOOD ONE!
:cool: It's all here: http://download.oracle.com/javase/6/docs/api/
 12032010, 08:27 PM #11
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,004
 Blog Entries
 7
 Rep Power
 23
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,
JosI have the stamina of a seal; I lie on the beach instead of running on it.
Similar Threads

Fibonacci sequence
By ŖàΫ ỏƒ Ңόρę in forum New To JavaReplies: 6Last Post: 03252010, 07:59 AM 
help with fibonacci
By likemine in forum New To JavaReplies: 8Last Post: 01072010, 03:32 AM 
help with fibonacci problem
By thekrazykid in forum New To JavaReplies: 4Last Post: 12122008, 11:41 PM 
A Fibonacci printing program
By Java Tip in forum Java TipReplies: 0Last Post: 03282008, 08:26 PM 
Fibonacci Algorithm
By susan in forum New To JavaReplies: 1Last Post: 08072007, 04:25 AM
Bookmarks