Fibonacci sequece

[Bgreen7887]

Hey guys just learning recursion!! I have coded that part as follows

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

 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:):)

[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...

[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?

[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 ^^

[pbrockway2]

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.

[SmilingKey]

2%2 = 0. See mindprod.com.

right, thanks

[Bgreen7887]

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

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);
}


}

[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

[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??

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);
	}
	}

[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:
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!

[JosAH]

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