The Fibonacci sequence is a series of numbers where the next number in the sequence is the sum of the previous 2 numbers.
The first two numbers in the sequence are
The sequence starts with:
1, 1, 2, 3, 5, 8...
We would like to write a simple recursive solution that returns the nth Fibonacci number.
fibonacci(4) would return
fibonacci(6) would return
Here is the pseudocode for the simple recursive solution:
fibonacci(n): if n is 1 or 2: return 1 return fibonacci(n-1) + fibonacci(n-2)