# Fibonacci sequece

• 12-02-2010, 05:37 PM
Bgreen7887
Fibonacci sequece
Hey guys just learning recursion!! I have coded that part as follows
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
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.
• 12-02-2010, 08:28 PM
tashimoto
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...
• 12-02-2010, 08:40 PM
pbrockway2
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?
• 12-02-2010, 11:56 PM
SmilingKey
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 ^^
• 12-03-2010, 02:57 AM
pbrockway2
Quote:

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.
• 12-03-2010, 03:30 PM
SmilingKey
Quote:

Originally Posted by pbrockway2
2%2 = 0. See mindprod.com.

right, thanks
• 12-03-2010, 06:04 PM
Bgreen7887
ok here's updated code. I still having problem with the adding even numbers.

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); } }```
• 12-03-2010, 06:42 PM
tashimoto
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
• 12-03-2010, 07:09 PM
Bgreen7887
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??

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);         }         }```
• 12-03-2010, 08:23 PM
tashimoto
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: