Java Recursive method fibonacci problem?

Question

Write a recursive, public static method called fibonacci that will return the nth fibonacci number. n is the parameter. The return type should be int. The fibonacci numbers are famous mathematical seequence defined by the following rules.

first write teh error case for n<0, the mthod should return 0.
next there are two base cases:
f(0) = 0
f(1)=1
Last, write the recursive step. The recursive step defines the nth fibonacci number in terms of two fibonacci numbers that recede it
f(n) = f(n-1) + f(n-2)

Answer 1

Anytime you want to write a recursive function in any language think about two things:



1) Base case (could be base cases)

2) Recurrence relation.



You in your question have both of these. Your base cases are:

f(0) = 0 & f(1) = 1



Your recurrence relation is:

f(n) = f(n-1) + f(n-2)



Now, let's construct our recursive function. Here are the steps:



1) Name your function & figure out the return type & the input parameters.



public static int fibonacci(int n)

{

}



2) Write your base cases as if-else statements



if(n == 0)

return 0;

else if(n == 1)

return 1;



3) Write your recurrence relation as a recursive call to your function as follows:



return fibonacci(n-1) + fibonacci(n-2);



4) Add any other conditions you want to the top of your function. In your case you want to return 0 if n < 0 (negative). Here is how you do that:



if (n < 0)

return 0;



Now, let's write the complete function:



public static int fibonacci(int n)

{

if (n < 0)

return 0;

else if(n == 0)

return 0;

else if(n == 1)

return 1;

else

return fibonacci(n-1) + fibonacci(n-2);

}





I hope this helps you understand how to write recursive functions yourself in the future. Good luck!!

Answer 2

The only problem with this type of recursive code is that if you try to compute larger numbers... lets say the 9th fib number, the program will have to make 34 recursive calls, and it gets worse, 13 runs the recursive call 233 times!!!

The better way to approach it, something for you to think on, is how the recursive call is making multiple calculations for the same number... inefficient! Think about how to store fib numbers already calculated.

Answer 3

// take a number n -- return calculated fibonacci number

public static int Fibonacci(int n)

{



// set return fibonacci number to zero

int fibonacciNumber = 0;



// if given number n is not less than 0 -- do calc

if (!n < 0)

{



for (int i = n; i > 0; i--)

{



fibonacciNumber = fibonacciNumber + (n - i);

}



}



return fibonacciNumber; // return number

}



###########################



If the given number n is less than zero no calculation is done and the set fibonacciNumber value of 0 will be returned.



I think this will do it but check the results as I've not checked it in an IDE or run it.

Answer 4

Clearly, this must be a homework problem. Why do you ask how to do your homework on the internet? What's going to happen when you get out into the real world, and you need to do this? Will you come to Yahoo Answers? I think you need to figure this out on your own, it's quite simple and you'll benefit from it.