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 f₀ =0 and f₁=1

The Java Code

Download the Java Code

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

Download the Python Code

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.