The Fibonacci sequence is a well-known series of numbers where the first two numbers are 0 and 1 and every other term after that is a sum of the previous two numbers.
Fibonacci Sequence: 0, 1, 1, 2, 3 ,5 , 8, 13, 21, 34 …
Below is the code and analysis for the Fibonacci recursion in python:
# Code for finding the nth term in the Fibonacci sequence def fibonacci(n): # Parameter: n is the position of the number in the Fibonacci sequence. # Output: The nth number of the Fibonacci sequence will be outputted. # fibonacci(5) means we are finding the 5th fibonacci number # in the fiboacci sequence going from the left if n < 0: # Base Case 1: out of bounds return "Does not exist" elif n == 1: # Base Case 2: first number is 0 return 0 elif n == 2: # Base Case 3: second number is 1 return 1 else: # Recursive Case: return fibonacci(n - 1) + fibonacci(n - 2) print(fibonacci(5))
View code on GitHub.
In the code we see above we see that we must first define a few exceptions (or base cases) in this code first. By defining these exceptions, we give the function a stopping point, so it doesn’t call itself indefinitely. Once the exceptions are handled we move on to the recursive step (recursive case) of the Fibonacci sequence that adds the previous two terms. One thing to note about this is that there isn’t any set value for any nth term. This is what recursion is meant for. To be specific, a function calls itself over and over again with decreasing input. What this also means is that if you were to choose a value of 5 for n,
fibonacci(5) would split into
fibonacci(4), and so on and so forth until it reaches the base cases of