12.4 More math recursion

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 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:

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 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:

Note

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.

x = int(input())
y = int(input())

# TODO: power() function definition

print(power(x, y))

Note

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.

x = int(input())
y = int(input())

# TODO: rec_pow() function definition

print(rec_pow(x, y))