Studyon Minte9.com
Algorithms (Codingbat)




Fibonacci sequence



The fibonacci sequence is a famous bit of mathematics. The first two values in the sequence are 0 and 1 
(essentially 2 base cases). 

Each subsequent value is the sum of the previous two values, so the whole sequence is: 
0, 1, 1, 2, 3, 5, 8, 13, 21 and so on. 

Define a recursive fibonacci(n) method that returns the nth fibonacci number, with n=0 representing the start 
of the sequence. 

	%java
		package testexample2;

		import org.junit.Assert.*;
		import junit.framework.*;
			
		public class Test extends TestCase {
		    
		    public static void main(String[] args) {
			
			// 0,1,1,2,3,5,8,13,21 ...
		    
			assertEquals(0, fibonacci(0));
			assertEquals(1, fibonacci(1));
			assertEquals(1, fibonacci(2));
			assertEquals(2, fibonacci(3));
			assertEquals(3, fibonacci(4));
		    }
		    
		    public static int fibonacci(int n) {
			
			if (n == 0) return 0;
			if (n == 1) return 1;
			
			return fibonacci(n-1) + fibonacci(n-2);
		    }
		}