Let's generate the Fibonacci series to the fifth term:
1 1 2 3 5
A recursive-style program to generate the sequence would be as follows:
def fib(n): if n <= 2: return 1 else: return fib(n-1) + fib(n-2)
The code is very simple, but a little tricky to read because of the recursive calls being made that end up solving the problem.
When the base case is met, the fib() function returns 1. If n is equal to or less than 2, the base case is met.
If the base case is not met, we will call the fib() function again, and this time supply the first call with n-1, and the second with n-2:
return fib(n-1) + fib(n-2)
The layout of the strategy to solve the ith term in the Fibonacci sequence is as follows:
Careful observation ...
