Exercises

Problem 1

The factorial of a nonnegative integer \(n\) is defined by

\[\begin{split} n! = \begin{cases} 1 & \text{if}~n = 0, \\ n \cdot (n-1)! & \text{if}~n \geq 1. \end{cases} \end{split}\]

In other words, if \(f(n) = n!\), then

\[\begin{split} f(n) = \begin{cases} 1 & \text{if}~n = 0, \\ n \cdot f(n-1) & \text{if}~n \geq 1. \end{cases} \end{split}\]

Write a function named factorial() that accepts a nonnegative integer \(n\) and computes \(n!\) recursively, using the definition above.

Test Cases

print(factorial(0))
print(factorial(7))
print(factorial(30))
1
5040
265252859812191058636308480000000

Problem 2

Consider the iteration

\[ x^{(k+1)} = \frac{1}{1 + x^{(k)}}, \qquad x^{(0)} = \alpha \]

for some number \(\alpha\). This iteration produces a continued fraction, for example,

\[ x^{(3)} = \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \alpha}}}. \]

The value \(x^{(n)}\) can be computed iteratively or recursively.

  • Write a function named continued_fraction_iterative() that accepts a number \(\alpha\) and a nonnegative integer \(N\). Compute \(x^{(N)}\) using a for loop.

  • Write a function named continued_fraction_recursive() that accepts a number \(\alpha\) and a nonnegative integer \(N\). Compute \(x^{(N)}\) without a for loop by using recursion.

Both functions should return \(x^{(N)}\).

Test Cases

As \(k\) increases, the iterates approach \((\sqrt{5} - 1)/2 \approx 0.618\).

print(continued_fraction_iterative(1, 0))
print(continued_fraction_iterative(1, 1))
print(continued_fraction_iterative(1, 2))
print(continued_fraction_iterative(1, 10))
1
0.5
0.6666666666666666
0.6180555555555556
print(continued_fraction_recursive(1, 0))
print(continued_fraction_recursive(1, 1))
print(continued_fraction_recursive(1, 2))
print(continued_fraction_recursive(1, 10))
1
0.5
0.6666666666666666
0.6180555555555556
print(continued_fraction_iterative(10, 27))
print(continued_fraction_recursive(10, 27))
0.6180339887405341
0.6180339887405341

Problem 3

The Fibonacci numbers satisfy the doubling identities

\[\begin{split} F_n = \begin{cases} 0 & \text{if}~n = 0, \\ F_k\left(2F_{k+1} - F_k\right) & \text{if}~n = 2k > 0~\text{is even}, \\ F_k^2 + F_{k+1}^2 & \text{if}~n = 2k + 1~\text{is odd}. \end{cases} \end{split}\]

Write a function named fib_pair() that accepts a nonnegative integer \(n\) and computes \(F_n\) and \(F_{n+1}\) as follows.

  1. If \(n = 0\), this is the base case: return \(F_0 = 0\) and \(F_1 = 1\).

  2. Otherwise, let \(k = \lfloor n/2 \rfloor\) and call fib_pair() once to get \(F_k\) and \(F_{k+1}\).
    Here, \(k = \lfloor n/2 \rfloor\) (integer division) when \(n = 2k\) or \(n = 2k + 1\).

  3. Use the formulas above to compute \(F_{2k}\) and \(F_{2k+1}\).

  4. If \(n\) is even, then \(F_n = F_{2k}\) and \(F_{n+1} = F_{2k+1}\).
    If \(n\) is odd, then \(F_n = F_{2k+1}\) and \(F_{n+1} = F_{2k} + F_{2k+1}\).

Return \(F_n\) and \(F_{n+1}\).

Test Cases

When implemented correctly, fib_pair(200) makes 9 calls, while fib(200) would require about \(9 \times 10^{41}\) calls.

print(fib_pair(0))
print(fib_pair(1))
print(fib_pair(10))
print(fib_pair(200))
(0, 1)
(1, 1)
(55, 89)
(280571172992510140037611932413038677189525, 453973694165307953197296969697410619233826)

Problem 4

The matrix power \(A^n = AA\cdots A\) (\(n\) times) of a square matrix \(A\) satisfies

\[\begin{split} A^n = \begin{cases} I & \text{if}~n = 0, \\ \left(A^{n/2}\right)^2 & \text{if}~n > 0~\text{is even}, \\ \left(A^{(n-1)/2}\right)^2 A & \text{if}~n~\text{is odd}, \end{cases} \end{split}\]

where \(I\) is the identity matrix.

Write a function named matrix_power() that accepts a square NumPy array \(A\) and a nonnegative integer \(n\). Compute \(A^n\) recursively using the formulas above.

Reminder: np.eye(m) creates the \(m \times m\) identity matrix.

Test Cases

import numpy as np

B = np.array([
    [1, 1],
    [1, 0],
])
print(matrix_power(B, 0))
print(matrix_power(B, 1))
print(matrix_power(B, 10))
print(matrix_power(B, 200))
[[1. 0.]
 [0. 1.]]
[[1. 1.]
 [1. 0.]]
[[89. 55.]
 [55. 34.]]
[[4.53973694e+41 2.80571173e+41]
 [2.80571173e+41 1.73402521e+41]]

Fun fact: the powers of \(B = \left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right]\) contain Fibonacci numbers! For \(n \ge 1\),

\[\begin{split} B^n = \left[\begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array}\right]. \end{split}\]

Problem 5

Write a function named det() that accepts an \(n \times n\) matrix \(A\). Compute \(\det(A)\) recursively using the formula

\[\begin{split} \begin{aligned} \det(A) &= \sum_{j=1}^{n} (-1)^{1+j} a_{1j} \det(A_{1j}) \\ &= a_{11}\det(A_{11}) - a_{12}\det(A_{12}) + \cdots + (-1)^{1+n} a_{1n}\det(A_{1n}), \end{aligned} \end{split}\]

where \(A_{ij}\) is the \((n - 1) \times (n - 1)\) matrix obtained by removing row \(i\) and column \(j\) from \(A\).

Test Cases

# 1 x 1 matrix.
A = np.array([
    [18],
])
print(det(A))

# 2 x 2 matrix.
A = np.array([
    [3, 1],
    [4, 2],
])
print(det(A))

# 3 x 3 matrix.
A = np.array([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 10],
])
print(det(A))

# 4 x 4 matrix.
A = np.array([
    [2, 0, 1, 3],
    [1, 4, -1, 0],
    [0, 2, 5, 1],
    [3, 1, 0, 2],
])
print(det(A))
18
2
-3
-82