The Fibonacci Sequence is one of the classic recursive algorithms that you learn in computer science.
Mathematically, the fibonacci sequence looks like this
f(x) = f(x-1) + f(x-2) and base values of either f0 =0 and f1=1
The Java Code
|
1 2 3 4 5 6 7 8 9 10 11 |
public class Recursion{ public static int FibonacciNumber(int number){ if(number == 1 || number == 2){ return 1; } return FibonacciNumber(number-1) + FibonacciNumber(number -2); //tail recursion } } |
The Python Code
|
1 2 3 4 5 |
def fibonacci( n ) : if n is 1 or n is 2 : return 1 return fibonacci(n-1) + fibonacci( n-2) |
Fibonnacci Recursion Animation
Want to Practice your skills with the Fibonacci Sequence?
Try these problems at the following coding practice sites
- Codingbat’s Fibonacci Sequence problem : This problem requires you to use Java
- ProjectEuler’s Fibonacci Sequence Problem ( Asks you to find the sum of the even Fibonacci Numbers less than 4 million) . In case you have never used ProjectEuler, you can make use of any programming language that you want, you just have to find the correct answer. Once you’ve done that, you gain access to thread showing the various solutions/codes that other programmers used.
