1. Senior 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(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.

2. Member
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; 12-02-2010 at 07:59 PM. Reason: misunderstood question...

3. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,561
Rep Power
11
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. Member
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; 12-03-2010 at 02:38 PM.

5. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,561
Rep Power
11
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. Member
Join Date
Dec 2010
Posts
19
Rep Power
0
Originally Posted by pbrockway2
2%2 = 0. See mindprod.com.
right, thanks

7. Senior 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(n-1)+FibSeq(n-2);
}

}```
Last edited by Bgreen7887; 12-03-2010 at 05:06 PM.

8. Member
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

9. Senior 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(n-1)+FibSeq(n-2);
}
}```

10. Member
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
Big-O Notation and Algorithm Analysis

Much Luck! :)
Chris

EDIT:
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. Originally Posted by 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??
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

#### Posting Permissions

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