5.5. Recursion#

Recursion is a way of solving problems where the solution depends on breaking down the problem into smaller subproblems. This requires functions to include a function call to themselves. For example, consider the calculation of a factorial.

\[\begin{split} \begin{align*} n! &= n \times (n - 1)! \\ &= n \times (n-1) \times (n - 2)! \\ & \quad \vdots \\ &= n \times(n-1) \times (n-2) \times \cdots \times 4 \times 3! \\ &= n \times (n-1) \times (n-2) \times \cdots \times 4 \times 3 \times 2. \end{align*} \end{split}\]

So to calculate \(n!\) we need the value of \((n-1)!\) which in turn needs the value of \((n-2)!\) and so on. So we could calculate \(n!\) by splitting the problem down into subproblems and solving each on of those in turn. Lets write a function called factorial() and uses recursion. Enter the following code into your program

# Recursion
def factorial(n):
    if n == 0 or n == 1:
        return 1
    else: 
        return n * factorial(n - 1)
    
 
print()
print(f"6! = {factorial(6)}")

Run your program and you should see the following added to the console

6! = 720

Lets step through this function for an input of n = 3.

  • factorial(3): n=3 which isn’t 0 or 1 so we need to calculate 3 * factorial(2)

  • factorial(2): n=2 which isn’t 0 or 1 so we need to calculate 2 * factorial(1)

  • factorial(1): n=1 which is 1 so we return 1 and return to factorial(2)

  • factorial(2): n=2 which isn’t 0 or 1 so we return 2 * 1 = 2 and return to factorial(3)

  • factorial(3): n=3 which isn’t 0 or 1 so we return 3 * 2 = 6

A recursive function requires a base case and recursive case

  • Base case: the condition under which the function stops calling itself and returns a value. In our factorial() function this was when n == 0 or n == 1 so we returned 1 since \(0! = 1! = 1\).

  • Recursive case: the condition under which the function needs to call itself. Each recursive call should move the function closer to the base case so that the recursion eventually terminates. In our factorial() function this was when n is greater than 1. Some recursive functions will have more than one recursive case.

Warning

Recursion offers an elegant way of solving some problems but can require lots of function calls and memory when the levels of recursion gets large resulting in longer run times. Recursion should only really be used where absolutely necessary.

5.5.1. Exercises#

Exercise 5.10

Write a function called fibonacci() that computes the \(n\)th Fibonacci number using recursion. Use your function to compute:

  1. the 10th Fibonacci number

  2. the 20th Fibonacci number

  3. the 40th Fibonacci number (warning, this may take a few seconds to calculate)

Exercise 5.11

The determinant of an \(n\times n\) square matrix can be calculated using

\[ \begin{align*} \det(A) = \sum_{i=1}^n (-1)^{(i + 1)} a_{1i} \det(A_i), \end{align*} \]

where \(A_i\) is the matrix formed by removing row 1 and column \(i\) from \(A\) and the determinant of a \(2\times 2\) matrix is

\[\begin{split}\det \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} = a_{11} a_{22} - a_{12} a_{21}. \end{split}\]

Write a function called det() that computes the determinant of a square matrix using recursion. Use your function to compute the determinants of following matrices:

  1. \(A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}\)

  2. \(B = \begin{pmatrix} -3 & -3 & 4 \\ 6 & -1 & 3 \\ -2 & 6 & 0 \end{pmatrix}\)

  3. \(C = \begin{pmatrix} 5 & 2 & -2 & 6 \\ -1 & -1 & 3 & -1 \\ 5 & -1 & 0 & 1 \\0 & -3 & 5 & 2 \end{pmatrix}\)