Learning objectives
By the end of this section you should be able to
- Define a recursive function to generate Fibonacci numbers.
Fibonacci sequence using recursion
The Fibonacci sequence is a sequence in which each number in the sequence is the sum of the previous two numbers in the sequence. The first two numbers are 0 and 1. Thus, starting from 0 and 1, the third number is 0 + 1 = 1, and the next number is 1 + 1 = 2. The sequence of numbers is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... .
Recursion can be used to calculate the nth Fibonacci number. The base cases are 0 and 1. Thereafter, the nth number is given by adding the (n - 1)th and (n - 2)th number. Thus, fib(n) = fib(n - 1) + fib(n - 2), which is a recursive definition ending with base cases f(0) = 0, and f(1) = 1.
For a recursion that calls multiple functions in the recursive case, tracing how the recursion proceeds is useful. A structure used to trace the calls made by a recursive function is called a recursion tree. The animation below traces the recursion tree for a call to a recursive function to calculate the Fibonacci number for n = 5.
Example 12.1
Finding the nth Fibonacci number
The Fibonacci function recursion is more complex with the value at n depending on two function calls with smaller values.
""" Recursive Fibonacci function """
def fib(n):
# Base case
if n == 0 or n == 1:
return n
# Recursive case
elif n > 1:
return fib(n - 1) + fib(n - 2)
# Error case
else:
print("Fibonacci numbers begin at 0.")
return
# Test code
print(fib(7))
The above code's output is:
13
Concepts in Practice
Fibonacci numbers
Greatest common divisor (GCD)
The greatest common divisor (GCD) of two positive integers is an integer that is a divisor for both integers. Ex: The GCD of 6 and 9 is 3 because 3 x 2 = 6, and 3 x 3 = 9.
The GCD is found easily using Euclid's method. Euclid's method recursively subtracts the smaller integer from the larger integer until a base case with equal integers is reached. The greatest common divisor is the integer value when the base case is reached.
Example 12.2
Finding the GCD
""" Find GCD using recursive implementation of Euclid's method """
def gcd(a, b):
if a == b: # Base case
return a
elif a < b: # Recursive case
return gcd(a, b - a)
else:
return gcd(a - b, a)
# Test code
print(gcd(24, 30))
The above code's output is:
6
Concepts in Practice
GCD
Try It
Recursive power
Write a recursive power() function, such that given an integer x and a positive integer y, power(x, y) returns x raised to y.
Ex: power(3, 4) returns 81.
Try It
Recursive power (with any integer power)
Write a recursive rec_pow() function such that given two integers, x and y, it returns x raised to y.
(Note: this is an extension of the above problem but now works for any integer value of y, positive or negative. How should the recursive function change to deal with a negative value of y?)
Ex: rec_pow(2, -4) returns 0.0625.