Exercises¶
Problem 1
The factorial of a nonnegative integer \(n\) is defined by
In other words, if \(f(n) = n!\), then
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
for some number \(\alpha\). This iteration produces a continued fraction, for example,
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 aforloop.Write a function named
continued_fraction_recursive()that accepts a number \(\alpha\) and a nonnegative integer \(N\). Compute \(x^{(N)}\) without aforloop 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
Write a function named fib_pair() that accepts a nonnegative integer \(n\) and computes \(F_n\) and \(F_{n+1}\) as follows.
If \(n = 0\), this is the base case: return \(F_0 = 0\) and \(F_1 = 1\).
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\).Use the formulas above to compute \(F_{2k}\) and \(F_{2k+1}\).
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
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\),
Problem 5
Write a function named det() that accepts an \(n \times n\) matrix \(A\). Compute \(\det(A)\) recursively using the formula
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