Tutorial: Recursive Algorithms

2025-07-09

1 A Mystery Algorithm

1.1

What does the following function do?

Precondition: \(x \in \mathbb{N}\).

def mystery(x):
    if x == 0:
        return "0"
    else:
        return mystery(x // 2) + str(x % 2)

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!

link to code

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)\).
Note

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\).

What does ‘valid’ mean? Some (not super interesting) technical details are swept under the rug here, but you should try to work them out if you want!

There’s a lot more interesting facts about the Towers of Hanoi problem which you can read about in the wikipedia article