A Fibonacci Sequence is a sequence of numbers in which the first and second numbers in the sequence are 0 and 1 respectively, and additional numbers in the sequence are calculated by adding the previous two.

The first few numbers in the Fibonacci Sequence look like this:

`0, 1, 1, 2, 3, 5, 8, 13, 21...`

Often in technical interviews a person will be asked to “**create a function that returns the nth value in a Fibonacci Sequence**“. A recursive algorithm can solve this problem in a few simple steps as described below.

1. The first and second numbers in the sequence will always be 0 and 1 respectively. In this example we are assuming that n=0 represents the first number in the series. If 0 or 1 is passed to our function, then no calculation is needed. Simply return the value of n.

2. If n is greater than 1, recursively call function(n-1) + function(n-2).

While this algorithm is clean and simple, it has a relatively expensive time complexity, which in the worst case is approximately exponential. There are a variety of other simple but more efficient algorithms that can be used to solve this problem as well.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
package com.bigdatums.interview; public class FibonacciRecursive { public static int fibonacciRecursive(int n) { if(n == 0) return 0; else if (n == 1) return 1; else return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2); } public static void main(String[] args) { System.out.println(fibonacciRecursive(0)); System.out.println(fibonacciRecursive(1)); System.out.println(fibonacciRecursive(2)); System.out.println(fibonacciRecursive(3)); System.out.println(fibonacciRecursive(4)); System.out.println(fibonacciRecursive(5)); System.out.println(fibonacciRecursive(6)); System.out.println(fibonacciRecursive(7)); System.out.println(fibonacciRecursive(8)); System.out.println(fibonacciRecursive(9)); System.out.println(fibonacciRecursive(10)); } } |