12.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)! \\ &\vdots \\ &= n \times(n-1) \times (n-2) \cdots 4 \times 3! \\ &= n \times (n-1) \times (n-2) \cdots 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!\) be splitting the problem down into subproblems and solving those. Lets write a function called factorial() and uses recursion. Enter the following code into your program

% -------------------------------------------------------------------------
function y = my_factorial(n)

if n == 0 || n == 1
    y = n;
else
    y = n * my_factorial(n - 1);
end

end

and make a call to this function by entering the following code before the function declarations.

% Recursion
fprintf("\n6! = %d\n", my_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.

  1. my_factorial(3): n=3 so we need to calculate my_factorial(2)

  2. my_factorial(2): n=2 so we need to calculate my_factorial(1)

  3. my_factorial(1): n=1 so we return 1 and return to my_factorial(2)

  4. my_factorial(2): n=2 so we return 2 * 1 = 2

  5. my_factorial(3): n=3 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 my_factorial() function this was when n == 0 or n == 1 so we returned 0 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 my_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.

12.5.1. Exercises#

Exercise 12.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 12.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 my_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}\)