Tutorial: Recursive Algorithms
2025-07-09
1 A Mystery Algorithm
1.1
What does the following function do?
Precondition: \(x \in \mathbb{N}\).
Try finding the value of \(\texttt{mystery}(7)\), \(\texttt{mystery}(12)\)...
Solution
Converts a number to a binary representation!
Formally, we return a string \(s\) such that \(\sum_{i = 0}^{\mathrm{len}(s)-1} s[i] \cdot 2^{\mathrm{len}(s) - i - 1} = x\).1.2
Come up with a precondition and postcondition for this function, and prove correctness.
Solution
Precondition: \(x \in \mathbb{N}\). Postcondition: The return value is a string representation of the binary representation of \(x\).
Let \(P(n)\) be the predicate that the function returns a string representation of the binary representation of \(n\).
We’ll prove \(\forall n \in \mathbb{N}. P(n)\) by induction on \(n\).
Base case. For \(n = 0\), the function returns “0”, which is the correct binary representation of \(0\). So \(P(0)\) holds.
Inductive step. Let \(k \in \mathbb{N}\) and assume \(P(i)\) holds for all \(i < k\). We’ll show \(P(k)\) holds. Note that since \(k > 0\), we are in the the else case. By the inductive hypothesis, \(\texttt{mystery}(k // 2)\) returns a string representation of the binary representation of \(k // 2\). Then, we return \(s = \texttt{mystery}(k // 2) + str(k \mod 2)\).
Here’s the intuition. Start with \(\texttt{mystery}(k // 2)\), which gives you the binary representation of \(k // 2\). Appending \(str(k \mod 2)\) to the end of the string shifts all the digits to the left by one position, effectively multiplying the value by \(2\) and then adding \(str(k \mod 2)\). The value of the string is \(\lfloor k/2\rfloor \cdot 2 + (k \mod 2)\). You can check that this is equal to \(k\) (i.e. by cases on if \(k\) is odd or even).
Here’s the formal proof. To make life easier, let’s define \(t = \texttt{mystery}(k // 2)\). \[ \begin{align*} \sum_{i = 0}^{\mathrm{len}(s) - 1} s[i] \cdot 2^{\mathrm{len}(s) - i - 1} &= \left(\sum_{i = 0}^{\mathrm{len}(s) - 2} t[i] \cdot 2^{\mathrm{len}(s) - i - 1}\right) + (k \mod 2)\\ &= \left(\sum_{i = 0}^{\mathrm{len}(t) - 1} t[i] \cdot 2^{\mathrm{len}(t) - i - 1}\right) \cdot 2 + (k \mod 2) & [\mathrm{len}(t) = \mathrm{len}(s) - 1] \\ &= 2 \lfloor k/2\rfloor + (k \mod 2) & [IH]\\ &= k\\ \end{align*} \]1.3
Prove the runtime of the algorithm is \(O(\log n)\).Solution
The recurrence is \(T(n) = T(n/2) + O(1)\). We can solve this using the master theorem or note that it’s the same recurrence as binary search, which is \(O(\log n)\).
2 Towers of Hanoi
Go to this website and try the game.
If you can do it with 3 disks, try it with 4!
Let \(\texttt{tower\_of\_hanoi}(n, a, b, c)\) be a function that moves the top \(n\) disks from peg \(a\) to peg \(c\) using peg \(b\) as an auxiliary disk. Note that this function should move the disks in a way that respects the game’s rules. I.e., larger disks cannot be placed on smaller disks.
Here’s the recursive insight.
- To move \(n\) disks from \(a\) to \(c\), I move \(n-1\) disks from \(a\) to \(b\), then move the largest disk from \(a\) to \(c\) and then move the \(n-1\) disks from \(b\) to \(c\).
Here is that insight summarized in an algorithm
def tower_of_hanoi(n, a, b, c):
if n > 0:
tower_of_hanoi(n - 1, a, c, b) # Move n-1 disks from a to b
c.append(a.pop()) # Move the largest disk from a to c
tower_of_hanoi(n - 1, b, a, c) # Move n-1 disks from b to c
Let’s check that it works!
2.1
What is a recurrence for the runtime of this algorithm?
Solution
The recurrence is \(T(n) = 2T(n-1) + 1\)2.2
Prove \(T(n) = \Theta(2^n)\) using the substitution method.
If you get stuck, try utilizing lower order term!
Solution
Claim \(T(n) \leq c2^n + d\). Use the substitution method.
\[ \begin{align*} T(n) &= 2T(n - 1) + 1\\ &\leq 2(c2^{n-1} + d) + 1\\ &\leq c2^{n} + 2d + 1 \end{align*} \]
This is at most \(c2^{n} + d\) when \(d \leq -1\).
Claim \(T(n) \geq c2^n\). Use the substitution method.
\[ \begin{align*} T(n) &= 2T(n - 1) + 1\\ &\geq 2(c2^{n-1}) + 1\\ &\geq c2^{n} \end{align*} \]
Thus, \(T(n) = \Omega(2^n)\).Isn’t this a little strange?
\(T(n) \leq c2^{n-1} - 1\) but \(T(n) \geq c2^{n-1}\)!
Subtracting a lower order term helps the inductive step go through in the Big-O proof. This is counter-intuitive!
Remember that the constants are different, so there’s no contradiction.
To be extra sure, write a full proof by induction for both inequalities with the base case \(T(0) = 1\).
2.3
Prove correctness of the algorithm.Solution
\(P(n).\) If \(a\), \(b\), and \(c\) contain a valid ordering of pegs and the number of disks on \(a\) is at most \(n\), \(\texttt{tower\_of\_hanoi}(n, a, b, c)\) moves the top \(n\) disks from \(a\) to \(c\) while respecting the rules of the game.
Base case. For \(n = 0\), there are no disks to move, so we are done.
Inductive step. Let \(k \in \mathbb{N}\) and assume \(P(k)\). We’ll show \(P(k+1)\). Let \(a, b, c\) be any valid configuration of pegs. Consider the execution of \(\texttt{tower\_of\_hanoi}(k+1, a, b, c)\).
By the inductive hypothesis, the first call to \(\texttt{tower\_of\_hanoi}\) moves the top \(k\) disks from \(a\) to \(b\).
The next line the moves the \(k+1\)th disk from \(a\) to \(c\).
By the inductive hypothesis, the last line moves the \(k\) disks moved to \(b\) in the first recursive call to \(c\).
There’s a lot more interesting facts about the Towers of Hanoi problem which you can read about in the wikipedia article