Skip to content

Exercises · Recursion

Exercises · Chapter 14 · each solution opens with a click · Chapter 14: Recursion · Exercises, volume 5 (PDF)

In the exercises of this chapter the steps of a recursive algorithm are counted with the conventions of the chapters «Running time» and «Recursion», and the recurrences are solved by simple unrolling.

  • Every execution of a numbered line of pseudo-code is one step; a line that contains a recursive call counts as one step plus all the steps executed by that call.

  • \(C(n)\) denotes the number of calls (nodes of the tree of recursive calls) and \(S(n)\) the number of steps; the depth of the recursion is the maximum number of nodes on a path from the root to a leaf of the tree, i.e., the maximum number of stack frames simultaneously in memory.

  • Strong induction: if \(P(n_0)\) is true and, for every \(n>n_0\), the truth of \(P(k)\) for every \(k\) with \(n_0\le k<n\) implies the truth of \(P(n)\), then \(P(n)\) is true for every \(n\ge n_0\).

  • Unrolling a recurrence \(S(n)=S(n-1)+c\) with constant \(c\):

    \[ S(n)=S(n-1)+c=S(n-2)+2c=\cdots=S(n-k)+k\,c, \]

    and the base case is reached for the value of \(k\) that makes \(n-k\) a base case.

Exercise 14.1: Recursion (E1)

Consider the following recursive algorithm.

Algorithm: Mystery

Input: A natural number \(n \ge 1\)
Output: A natural number
1function Mystery(n)
2if \(n = 1\) then
3return \(1\)
4end
5return Mystery\((\lfloor n/2 \rfloor)\) \(+\) Mystery\((\lceil n/2 \rceil)\)
6end

Questions

  1. Draw the tree of recursive calls of Mystery\((6)\), writing next to each call the value it returns.

  2. What does the algorithm compute? Prove your claim by strong induction on \(n\).

  3. Let \(C(n)\) be the number of calls executed by Mystery\((n)\). Write a recurrence for \(C(n)\) and prove that \(C(n) = 2n - 1\) for every \(n \ge 1\). Check the formula on the tree of question 1.

  4. What is the depth of the recursion of Mystery\((6)\), i.e., the maximum number of stack frames simultaneously in memory?

Solution

  1. We have \(\lfloor 6/2 \rfloor = \lceil 6/2 \rceil = 3\), \(\lfloor 3/2 \rfloor = 1\), \(\lceil 3/2 \rceil = 2\) and \(\lfloor 2/2 \rfloor = \lceil 2/2 \rceil = 1\). The tree of recursive calls (returned values in red) is:

    Figure 1

    Mystery\((2)\) returns \(1+1 = 2\), Mystery\((3)\) returns \(1 + 2 = 3\) and Mystery\((6)\) returns \(3 + 3 = 6\).

  2. The algorithm returns \(n\) itself (it computes \(n\) as a sum of \(n\) ones).

    Proof by strong induction on \(n \ge 1\).

    • Base case (\(n=1\)): the algorithm returns \(1\) at line 3.

    • Inductive step (\(n \ge 2\)): assume that Mystery\((k)\) returns \(k\) for every \(1 \le k < n\). For \(n \ge 2\) we have \(1 \le \lfloor n/2 \rfloor \le \lceil n/2 \rceil < n\), so by the inductive hypothesis line 5 returns

      \[ \lfloor n/2 \rfloor + \lceil n/2 \rceil = n. \]

    Strong induction is necessary because the recursive calls are on \(\lfloor n/2 \rfloor\) and \(\lceil n/2 \rceil\), not on \(n-1\).

  3. Each call with \(n \ge 2\) makes two recursive calls, hence

    \[ C(n) = \begin{cases} 1 & \text{if } n = 1 \\ 1 + C(\lfloor n/2 \rfloor) + C(\lceil n/2 \rceil) & \text{if } n \ge 2 \end{cases} \]

    Proof of \(C(n) = 2n - 1\) by strong induction on \(n\).

    • Base case (\(n=1\)): \(C(1) = 1 = 2 \cdot 1 - 1\).

    • Inductive step (\(n \ge 2\)): by the inductive hypothesis,

      \[ C(n) = 1 + \big(2\lfloor n/2 \rfloor - 1\big) + \big(2\lceil n/2 \rceil - 1\big) = 2\big(\lfloor n/2 \rfloor + \lceil n/2 \rceil\big) - 1 = 2n - 1. \]

    For \(n = 6\): \(C(6) = 11\), and indeed the tree of question 1 has \(11\) nodes. (The tree has \(n = 6\) leaves, one for each \(1\) in the sum, and \(n - 1 = 5\) internal nodes, one for each addition.)

  4. The longest paths from the root to a leaf are, e.g., Mystery\((6)\), Mystery\((3)\), Mystery\((2)\), Mystery\((1)\). Hence the depth of the recursion is \(4\): at most \(4\) stack frames are simultaneously in memory, although \(11\) calls are executed. (In general the depth is \(\lceil \log_2 n \rceil + 1\).)

Exercise 14.2: Recursion (E2)

Given an array \(a[1..n]\) of \(n\) integer numbers, consider the problems of computing

  • the sum \(a[1] + a[2] + \dots + a[n]\) (equal to \(0\) if \(n = 0\));

  • the maximum value \(\max\{a[1], a[2], \dots, a[n]\}\) (for \(n \ge 1\)).

Use the array \(a = [3, 8, 1, 6]\) for the numerical questions.

Questions

  1. Write a recursive algorithm RecSum\((a, n)\) that computes the sum of \(a[1..n]\) by reducing the problem to the sub-array \(a[1..n-1]\) (decrease by one).

  2. Write a recursive algorithm RecMax\((a, n)\) that computes the maximum of \(a[1..n]\) by reducing the problem to the sub-array \(a[1..n-1]\).

  3. Show the sequence of calls and returns of RecSum\((a, 4)\) and of RecMax\((a, 4)\) for \(a = [3, 8, 1, 6]\).

  4. Prove the correctness of RecMax by induction on \(n\).

  5. Write the recurrences of the number of steps \(S(n)\) of the two algorithms, solve them by unrolling, and give the depth of the recursion.

Solution

  1. The sum of \(a[1..n]\) is the sum of \(a[1..n-1]\) plus \(a[n]\), and the sum of an empty array is \(0\):

    Algorithm: RecSum

    Input: An array \(a[1..n]\) of \(n \ge 0\) integer numbers
    Output: The sum \(a[1] + \dots + a[n]\)
    1function RecSum(a, n)
    2if \(n = 0\) then
    3return \(0\)
    4end
    5return RecSum\((a, n-1) + a[n]\)
    6end

  2. The maximum of \(a[1..n]\) is the larger between the maximum of \(a[1..n-1]\) and \(a[n]\); the maximum of a single element \(a[1]\) is \(a[1]\):

    Algorithm: RecMax

    Input: An array \(a[1..n]\) of \(n \ge 1\) integer numbers
    Output: The maximum value in \(a[1..n]\)
    1function RecMax(a, n)
    2if \(n = 1\) then
    3return \(a[1]\)
    4end
    5\(m :=\) RecMax\((a, n-1)\)
    6if \(a[n] > m\) then
    7return \(a[n]\)
    8end
    9return \(m\)
    10end

  3. For \(a = [3, 8, 1, 6]\):

    RecSum\((a,4)\): calls

    \[ \texttt{RecSum}(a,4) \to \texttt{RecSum}(a,3) \to \texttt{RecSum}(a,2) \to \texttt{RecSum}(a,1) \to \texttt{RecSum}(a,0), \]

    then the returns:

    call returns
    RecSum\((a,0)\) \(0\) (base case)
    RecSum\((a,1)\) \(0 + a[1] = 0 + 3 = 3\)
    RecSum\((a,2)\) \(3 + a[2] = 3 + 8 = 11\)
    RecSum\((a,3)\) \(11 + a[3] = 11 + 1 = 12\)
    RecSum\((a,4)\) \(12 + a[4] = 12 + 6 = 18\)

    RecMax\((a,4)\): calls RecMax\((a,4) \to\) RecMax\((a,3) \to\) RecMax\((a,2) \to\) RecMax\((a,1)\), then the returns:

    call comparison returns
    RecMax\((a,1)\) – (base case) \(a[1] = 3\)
    RecMax\((a,2)\) \(m = 3\), \(a[2] = 8 > 3\) \(8\)
    RecMax\((a,3)\) \(m = 8\), \(a[3] = 1 \le 8\) \(8\)
    RecMax\((a,4)\) \(m = 8\), \(a[4] = 6 \le 8\) \(8\)

    The sum is \(18\) and the maximum is \(8\).

  4. Claim: for every \(n \ge 1\), RecMax\((a,n)\) returns \(\max\{a[1], \dots, a[n]\}\).

    • Base case (\(n=1\)): the algorithm returns \(a[1] = \max\{a[1]\}\) at line 3.

    • Inductive step (\(n \ge 2\)): by the inductive hypothesis, line 5 assigns

      \[ m = \max\{a[1],\dots,a[n-1]\}. \]

      If \(a[n] > m\), then \(a[n]\) is larger than all the elements of \(a[1..n-1]\) and the algorithm returns \(a[n] = \max\{a[1],\dots,a[n]\}\) (line 7). Otherwise \(a[n] \le m\) and the algorithm returns \(m = \max\{a[1],\dots,a[n]\}\) (line 9).

  5. RecSum. \(S(0) = 2\) (lines 2–3) and, for \(n \ge 1\), lines 2 and 5 plus the recursive call:

    \[ S(n) = S(n-1) + 2 = S(n-2) + 2 \cdot 2 = \dots = S(0) + 2n = 2n + 2 = \Theta(n). \]

    RecMax. \(S(1) = 2\) (lines 2–3) and, for \(n \ge 2\), lines 2, 5, 6 and one of the lines 7, 9, plus the recursive call:

    \[ S(n) = S(n-1) + 4 = S(n-2) + 2 \cdot 4 = \dots = S(1) + 4(n-1) = 4n - 2 = \Theta(n). \]

    For \(n = 4\): \(S(4) = 10\) for RecSum and \(S(4) = 14\) for RecMax.

    The depth of the recursion is \(n+1\) for RecSum (calls on \(n, n-1, \dots, 0\)) and \(n\) for RecMax (calls on \(n, \dots, 1\)): both use \(\Theta(n)\) memory for the call stack, while the iterative versions (as FindMaximum in the chapter «Running time») use constant memory.

    If all the entries use a constant number of bits (\(|I| = \Theta(n)\)), the worst-case running time of both RecSum and RecMax is \(T(|I|) = \Theta(|I|)\).

Exercise 14.3: Recursion (E3)

An array \(a[1..n]\) is a palindrome if it reads the same from left to right and from right to left, i.e., \(a[i] = a[n+1-i]\) for every \(i \in \{1, 2, \dots, n\}\). Consider the following recursive algorithm, called on the whole array as IsPalindrome\((a, 1, n)\).

Algorithm: IsPalindrome

Input: An array \(a\) and two indices \(l, r\)
Output: true if the sub-array \(a[l..r]\) is a palindrome, false otherwise
1function IsPalindrome(a, l, r)
2if \(l \ge r\) then
3return true
4end
5if \(a[l] \ne a[r]\) then
6return false
7end
8return IsPalindrome\((a, l+1, r-1)\)
9end

Questions

  1. Show the sequence of calls of IsPalindrome\((a,1,5)\) for the arrays \(a = [1, 2, 3, 2, 1]\) and \(a = [1, 2, 3, 3, 1]\).

  2. Prove by induction on the length \(k = r - l + 1\) of the sub-array that the algorithm is correct.

  3. Determine the worst-case number of steps \(S(n)\) of IsPalindrome\((a,1,n)\) and its depth of recursion.

  4. Is the algorithm tail recursive? If yes, write the equivalent iterative algorithm.

  5. Write a recursive algorithm Reverse\((a, l, r)\) that reverses the sub-array \(a[l..r]\) in place, and show its execution on \(a = [5, 7, 2, 9, 4, 6]\) with \(l = 1\), \(r = 6\).

Solution

  1. For \(a = [1, 2, 3, 2, 1]\):

    call \(a[l]\) \(a[r]\) action
    IsPalindrome\((a,1,5)\) \(1\) \(1\) equal \(\Rightarrow\) calls IsPalindrome\((a,2,4)\)
    IsPalindrome\((a,2,4)\) \(2\) \(2\) equal \(\Rightarrow\) calls IsPalindrome\((a,3,3)\)
    IsPalindrome\((a,3,3)\) – – \(l \ge r\) \(\Rightarrow\) returns true

    The value true is returned unchanged by all the calls (\(3\) calls).

    For \(a = [1, 2, 3, 3, 1]\):

    call \(a[l]\) \(a[r]\) action
    IsPalindrome\((a,1,5)\) \(1\) \(1\) equal \(\Rightarrow\) calls IsPalindrome\((a,2,4)\)
    IsPalindrome\((a,2,4)\) \(2\) \(3\) different \(\Rightarrow\) returns false

    The value false is returned (\(2\) calls).

  2. Let \(k = r - l + 1\) be the length of \(a[l..r]\) (\(k \le 0\) means an empty sub-array). We prove by strong induction on \(k\) that the algorithm returns true if and only if \(a[l..r]\) is a palindrome.

    • Base cases (\(k \le 1\), i.e., \(l \ge r\)): an empty array or an array with one element is a palindrome, and the algorithm returns true at line 3.

    • Inductive step (\(k \ge 2\)): \(a[l..r]\) is a palindrome if and only if \(a[l] = a[r]\) and the inner sub-array \(a[l+1..r-1]\) is a palindrome. If \(a[l] \ne a[r]\), the algorithm correctly returns false (line 6). Otherwise it returns the result of the call on \(a[l+1..r-1]\), whose length \(k-2 < k\); by the inductive hypothesis, this result is true if and only if \(a[l+1..r-1]\) is a palindrome, hence if and only if \(a[l..r]\) is a palindrome.

    The length decreases by \(2\) at each call, which is why both \(k=0\) and \(k=1\) must be base cases.

  3. The worst case is when the array is a palindrome (the recursion is never stopped at line 6). Every call with \(l < r\) executes lines 2, 5 and 8 (\(3\) steps), and the final call executes lines 2–3 (\(2\) steps). In terms of the length \(k\):

    \[ S(k) = S(k-2) + 3 \quad (k \ge 2), \qquad S(0) = S(1) = 2. \]

    Unrolling, after \(\lfloor k/2 \rfloor\) steps we reach \(S(0)\) or \(S(1)\):

    \[ S(n) = 3\lfloor n/2 \rfloor + 2 = \Theta(n). \]

    The algorithm makes \(\lfloor n/2 \rfloor + 1\) calls, which is also the depth of the recursion (the tree is a path). For \(n = 5\): \(3\) calls, as in question 1, and \(S(5) = 8\).

  4. Yes: the recursive call at line 8 is the last operation and its result is returned unchanged. Replacing the tail call by the update \((l, r) \leftarrow (l+1, r-1)\) we obtain:

    Algorithm: IterativeIsPalindrome

    Input: An array \(a[1..n]\)
    Output: true if \(a\) is a palindrome, false otherwise
    1function IterativeIsPalindrome(a, n)
    2\(l := 1\)
    3\(r := n\)
    4while \(l < r\) do
    5if \(a[l] \ne a[r]\) then
    6return false
    7end
    8\(l \leftarrow l + 1\)
    9\(r \leftarrow r - 1\)
    10end
    11return true
    12end

    It uses constant memory instead of a stack of depth \(\lfloor n/2 \rfloor + 1\).

  5. To reverse \(a[l..r]\): swap the two extreme elements, then reverse the inner sub-array \(a[l+1..r-1]\). A sub-array with at most one element is already reversed (base case, nothing to do).

    Algorithm: Reverse

    Input: An array \(a\) and two indices \(l, r\)
    Output: The sub-array \(a[l..r]\) reversed in place
    1function Reverse(a, l, r)
    2if \(l < r\) then
    3swap \(a[l]\) and \(a[r]\)
    4Reverse\((a, l+1, r-1)\)
    5end
    6end

    Execution on \(a = [5, 7, 2, 9, 4, 6]\):

    call action array after the call's swap
    Reverse\((a,1,6)\) swap \(a[1]=5\), \(a[6]=6\) \([6, 7, 2, 9, 4, 5]\)
    Reverse\((a,2,5)\) swap \(a[2]=7\), \(a[5]=4\) \([6, 4, 2, 9, 7, 5]\)
    Reverse\((a,3,4)\) swap \(a[3]=2\), \(a[4]=9\) \([6, 4, 9, 2, 7, 5]\)
    Reverse\((a,4,3)\) \(l \ge r\): base case, nothing to do \([6, 4, 9, 2, 7, 5]\)

    The final array is \([6, 4, 9, 2, 7, 5]\), after \(\lfloor 6/2 \rfloor + 1 = 4\) calls and \(3\) swaps. The correctness follows by induction on \(k = r - l + 1\) exactly as in question 2.

Exercise 14.4: Recursion (E4)

Consider the naive recursive algorithm for the Fibonacci numbers (\(F(0) = 0\), \(F(1) = 1\), \(F(n) = F(n-1) + F(n-2)\) for \(n \ge 2\)).

Algorithm: Fib

Input: A natural number \(n\)
Output: The Fibonacci number \(F(n)\)
1function Fib(n)
2if \(n \le 1\) then
3return \(n\)
4end
5return Fib\((n-1)\) \(+\) Fib\((n-2)\)
6end

Questions

  1. Draw the tree of recursive calls of Fib\((6)\) and compute the value returned.

  2. Count the number of calls \(C(6)\) and check the formula \(C(n) = 2F(n+1) - 1\).

  3. How many times is Fib\((k)\) called, for each \(k = 0, 1, \dots, 6\), during the computation of Fib\((6)\)? What do you observe?

  4. Compare the number of steps of Fib (\(S(n) = 4F(n+1) - 2\)) with the number of steps of IterativeFib (\(S(n) = 5n + 1\)) for \(n = 6\) and for \(n = 20\).

  5. What is the depth of the recursion of Fib\((6)\)?

Solution

  1. The tree of recursive calls of Fib\((6)\) (we write F\(k\) for Fib\((k)\)):

    Figure 2

    Returning from the leaves to the root: Fib\((2) = 1 + 0 = 1\), Fib\((3) = 1 + 1 = 2\), Fib\((4) = 2 + 1 = 3\), Fib\((5) = 3 + 2 = 5\), Fib\((6) = 5 + 3 = 8\). Hence \(F(6) = 8\).

  2. Counting the nodes of the tree level by level: \(1 + 2 + 4 + 8 + 8 + 2 = 25\). The formula gives

    \[ C(6) = 2F(7) - 1 = 2 \cdot 13 - 1 = 25. \]

    Equivalently, from the recurrence \(C(n) = C(n-1) + C(n-2) + 1\) with \(C(0) = C(1) = 1\): \(C(2) = 3\), \(C(3) = 5\), \(C(4) = 9\), \(C(5) = 15\), \(C(6) = 15 + 9 + 1 = 25\).

  3. Counting the nodes with the same label:

    \(k\) 6 5 4 3 2 1 0 total
    number of calls Fib\((k)\) 1 1 2 3 5 8 5 25

    The numbers of calls are themselves Fibonacci numbers: Fib\((k)\) is called \(F(7-k)\) times for \(k \ge 1\) (and Fib\((0)\) is called \(F(5)\) times, once for each call Fib\((2)\)). The same subproblems are solved again and again: for example \(F(2)\) is computed \(5\) times, while it would be enough to compute it once and store it. This is the motivation of Dynamic Programming.

  4. The number of calls and of steps of the two algorithms are:

    \(n\) calls \(C(n) = 2F(n+1)-1\) steps of Fib: \(4F(n+1) - 2\) steps of IterativeFib: \(5n+1\)
    \(6\) \(2 \cdot 13 - 1 = 25\) \(4 \cdot 13 - 2 = 50\) \(31\)
    \(20\) \(2 \cdot 10946 - 1 = 21891\) \(4 \cdot 10946 - 2 = 43782\) \(101\)

    For \(n = 6\) the two algorithms are comparable, but for \(n = 20\) the naive algorithm executes more than \(400\) times the number of steps of the iterative one: the first grows exponentially, the second linearly.

  5. The longest path from the root to a leaf is Fib\((6)\), Fib\((5)\), Fib\((4)\), Fib\((3)\), Fib\((2)\), Fib\((1)\): the depth of the recursion is \(6\). Although \(25\) calls are executed, at most \(6\) stack frames are simultaneously in memory.

Exercise 14.5: Recursion (E5)

Consider the Towers of Hanoi with \(n = 4\) disks, numbered \(1, 2, 3, 4\) from the smallest to the largest, initially on peg \(A\), to be moved to peg \(C\) using peg \(B\) as auxiliary peg, with the recursive algorithm:

Algorithm: Hanoi

Input: The number of disks \(n \ge 1\), the pegs \(from\), \(to\), \(aux\)
Output: The sequence of moves that transfers disks \(1,2,\dots,n\) from \(from\) to \(to\)
1function Hanoi(n, from, to, aux)
2if \(n = 1\) then
3move disk \(1\) from \(from\) to \(to\)
4else
5Hanoi\((n-1, from, aux, to)\)
6move disk \(n\) from \(from\) to \(to\)
7Hanoi\((n-1, aux, to, from)\)
8end
9end

Questions

  1. List all the moves executed by Hanoi\((4, A, C, B)\), in order.

  2. Check that the number of moves is \(M(4) = 2^4 - 1\).

  3. How many times is each disk moved? Prove that, with \(n\) disks, disk \(k\) is moved exactly \(2^{n-k}\) times (\(\forall k \in \{1, 2, \dots, n\}\)), and check that \(\sum_{k=1}^{n} 2^{n-k} = 2^n - 1\).

  4. How many calls of Hanoi are executed for \(n = 4\), and what is the depth of the recursion?

  5. According to the legend, \(n = 64\) golden disks are moved at a speed of one move per second. How long does it take?

Solution

  1. Hanoi\((4, A, C, B)\) executes Hanoi\((3, A, B, C)\), then moves disk \(4\) from \(A\) to \(C\), then executes Hanoi\((3, B, C, A)\). Each call with \(n = 3\) moves \(7\) disks (in the same pattern as Hanoi\((3, A, C, B)\) in the chapter, with the pegs renamed):

    move disk from to move disk from to
    1 1 A B 9 1 B C
    2 2 A C 10 2 B A
    3 1 B C 11 1 C A
    4 3 A B 12 3 B C
    5 1 C A 13 1 A B
    6 2 C B 14 2 A C
    7 1 A B 15 1 B C
    8 4 A C

    Moves \(1\)–\(7\) transfer disks \(1,2,3\) from \(A\) to \(B\) (call Hanoi\((3,A,B,C)\)), move \(8\) moves the largest disk, and moves \(9\)–\(15\) transfer disks \(1,2,3\) from \(B\) to \(C\) (call Hanoi\((3,B,C,A)\)).

  2. There are \(15\) moves and \(2^4 - 1 = 15\). Equivalently, \(M(1) = 1\), \(M(2) = 2 \cdot 1 + 1 = 3\), \(M(3) = 2 \cdot 3 + 1 = 7\), \(M(4) = 2 \cdot 7 + 1 = 15\).

  3. From the table: disk \(1\) is moved \(8\) times, disk \(2\) is moved \(4\) times, disk \(3\) is moved \(2\) times and disk \(4\) is moved once; these are \(2^{4-1}, 2^{4-2}, 2^{4-3}, 2^{4-4}\).

    Proof by induction on \(n\) that, in Hanoi\((n, \cdot, \cdot, \cdot)\), disk \(k\) is moved \(2^{n-k}\) times for every \(k \in \{1, 2, \dots, n\}\).

    • Base case (\(n = 1\)): disk \(1\) is moved once \(= 2^{1-1}\).

    • Inductive step (\(n \ge 2\)): disk \(n\) is moved only by the call itself, once \(= 2^{n-n}\). A disk \(k \le n-1\) is moved only inside the two recursive calls with \(n-1\) disks, and by the inductive hypothesis it is moved \(2^{(n-1)-k}\) times in each of them: in total \(2 \cdot 2^{n-1-k} = 2^{n-k}\) times.

    Summing over all the disks (geometric sum),

    \[ \sum_{k=1}^{n} 2^{n-k} = 2^{n-1} + 2^{n-2} + \dots + 2 + 1 = 2^n - 1 = M(n). \]

    For \(n=4\): \(8 + 4 + 2 + 1 = 15\).

  4. Every call executes exactly one move (the base case moves disk \(1\), the other calls move disk \(n\)), hence the number of calls is equal to the number of moves: \(15\) calls. The tree of recursive calls is a complete binary tree with \(4\) levels (\(1 + 2 + 4 + 8 = 15\) nodes), so the depth of the recursion is \(4\).

  5. \(M(64) = 2^{64} - 1 = 18\,446\,744\,073\,709\,551\,615\) moves, i.e., the same number of seconds. One year has about \(365.25 \cdot 24 \cdot 3600 = 31\,557\,600\) seconds, so the time is

    \[ \frac{2^{64}-1}{31\,557\,600} \approx 5.85 \cdot 10^{11} \text{ years}, \]

    about \(585\) billion years (more than \(40\) times the age of the universe). Since the number of moves of Hanoi is optimal, no algorithm can do better.

Exercise 14.6: Recursion (E6)

Consider the following two recursive algorithms: FastPower computes \(x^n\) by squaring, ToBinary prints the binary representation of a natural number \(n\).

Algorithm

Algorithm: FastPower
Input: A number \(x\) and a natural number \(n\)
Output: The power \(x^n\)
1function FastPower(x, n)
2if \(n = 0\) then
3return \(1\)
4end
5\(y :=\) FastPower\((x, \lfloor n/2 \rfloor)\)
6if \(n \bmod 2 = 0\) then
7return \(y \cdot y\)
8else
9return \(x \cdot y \cdot y\)
10end
11end

Algorithm: ToBinary
Input: A natural number \(n\)
Output: The binary digits of \(n\), printed from the most significant one
1function ToBinary(n)
2if \(n \le 1\) then
3print \(n\)
4else
5ToBinary\((\lfloor n/2 \rfloor)\)
6print \(n \bmod 2\)
7end
8end

Questions

  1. Show the sequence of calls of FastPower\((x, 25)\) and count the number of multiplications. Compare with the naive algorithm, which executes \(n\) multiplications.

  2. Compute the number of multiplications and the number of steps \(S(n) = 4\lfloor \log_2 n \rfloor + 6\) of FastPower for \(n = 31\), \(n = 32\) and \(n = 100\).

  3. A student replaces the line \(y :=\) FastPower\((x, \lfloor n/2 \rfloor)\) and the following lines by

    \[ \textbf{return } \texttt{FastPower}(x, \lfloor n/2 \rfloor) \cdot \texttt{FastPower}(x, \lfloor n/2 \rfloor) \quad (\text{times } x \text{ if } n \text{ is odd}). \]

    Write the recurrence of the number of calls \(C(n)\) of this version, compute \(C(13)\) and \(C(16)\), and show that \(C(n) = \Theta(n)\).

  4. Show the execution of ToBinary\((37)\): calls, printed digits, and number of calls. Why are the digits printed in the correct order, while the algorithm ChangeOfBase (chapter «Numerical algorithms») produces them from the least significant one?

  5. Prove by strong induction that ToBinary\((n)\) prints the binary representation of \(n\), and that it executes \(\lfloor \log_2 n \rfloor + 1\) calls for \(n \ge 1\).

Solution

  1. The exponents of the calls are \(25, 12, 6, 3, 1, 0\). Going back from the base case:

    call \(y\) returns multiplications
    FastPower\((x, 0)\) – \(1\) (base case) \(0\)
    FastPower\((x, 1)\) \(1\) \(x \cdot 1 \cdot 1 = x\) (odd) \(2\)
    FastPower\((x, 3)\) \(x\) \(x \cdot x \cdot x = x^3\) (odd) \(2\)
    FastPower\((x, 6)\) \(x^3\) \(x^3 \cdot x^3 = x^6\) (even) \(1\)
    FastPower\((x, 12)\) \(x^6\) \(x^6 \cdot x^6 = x^{12}\) (even) \(1\)
    FastPower\((x, 25)\) \(x^{12}\) \(x \cdot x^{12} \cdot x^{12} = x^{25}\) (odd) \(2\)

    In total \(2 + 2 + 1 + 1 + 2 = 8\) multiplications, against \(25\) for the naive algorithm. Note that \(25 = (11001)_2\): \(5\) binary digits, three of which equal to \(1\), and \(5 + 3 = 8\).

  2. The number of multiplications is the number of binary digits of \(n\) plus the number of digits equal to \(1\) (each call with \(n \ge 1\) executes \(1\) multiplication if \(n\) is even, \(2\) if \(n\) is odd, and the parity of the successive exponents gives the binary digits of \(n\)):

    \(n\) binary multiplications \(S(n) = 4\lfloor \log_2 n \rfloor + 6\) naive
    \(31\) \(11111\) \(5 + 5 = 10\) \(4 \cdot 4 + 6 = 22\) \(31\)
    \(32\) \(100000\) \(6 + 1 = 7\) \(4 \cdot 5 + 6 = 26\) \(32\)
    \(100\) \(1100100\) \(7 + 3 = 10\) \(4 \cdot 6 + 6 = 30\) \(100\)

    Note that \(x^{32}\) requires fewer multiplications than \(x^{31}\), although \(32 > 31\).

  3. Each call with \(n \ge 1\) now makes two recursive calls on \(\lfloor n/2 \rfloor\):

    \[ C(n) = 2C(\lfloor n/2 \rfloor) + 1 \quad (n \ge 1), \qquad C(0) = 1. \]

    Hence \(C(1) = 3\), \(C(3) = 7\), \(C(6) = 15\), \(C(13) = 31\), and \(C(2) = 7\), \(C(4) = 15\), \(C(8) = 31\), \(C(16) = 63\).

    The tree of recursive calls is now a complete binary tree. Its levels correspond to the exponents \(n, \lfloor n/2 \rfloor, \dots, 1, 0\), i.e., there are \(L = \lfloor \log_2 n \rfloor + 2\) levels, with \(1, 2, 4, \dots, 2^{L-1}\) nodes. Therefore

    \[ C(n) = 1 + 2 + \dots + 2^{L-1} = 2^{L} - 1 = 4 \cdot 2^{\lfloor \log_2 n \rfloor} - 1. \]

    (Check: \(C(13) = 4 \cdot 8 - 1 = 31\), \(C(16) = 4 \cdot 16 - 1 = 63\).) Since \(n/2 < 2^{\lfloor \log_2 n \rfloor} \le n\), we get \(2n - 1 < C(n) \le 4n - 1\), i.e., \(C(n) = \Theta(n)\): the version with two identical recursive calls is no better than the naive algorithm. Computing the value once and storing it in \(y\) is essential.

  4. Execution of ToBinary\((37)\):

    Calls:

    ToBinary\((37) \to\) ToBinary\((18) \to\) ToBinary\((9) \to\)
    ToBinary\((4) \to\) ToBinary\((2) \to\) ToBinary\((1)\)

    Prints (in the order in which the calls end):

    call action printed so far
    ToBinary\((1)\) base case, prints \(1\) \(1\)
    ToBinary\((2)\) prints \(2 \bmod 2 = 0\) \(10\)
    ToBinary\((4)\) prints \(4 \bmod 2 = 0\) \(100\)
    ToBinary\((9)\) prints \(9 \bmod 2 = 1\) \(1001\)
    ToBinary\((18)\) prints \(18 \bmod 2 = 0\) \(10010\)
    ToBinary\((37)\) prints \(37 \bmod 2 = 1\) \(100101\)

    Hence \(37 = (100101)_2\) (indeed \(32 + 4 + 1 = 37\)), with \(6\) calls.

    The remainders \(n \bmod 2\) are computed in the same order as in ChangeOfBase (repeated division: \(1, 0, 1, 0, 0, 1\), from the least significant digit). However, each call prints its remainder after its recursive call has returned, i.e., after all the more significant digits have been printed: the call stack reverses the order of the digits, and no array is needed.

  5. Correctness, by strong induction on \(n\).

    • Base cases (\(n \in \{0,1\}\)): the binary representation of \(n\) is the single digit \(n\), which is printed.

    • Inductive step (\(n \ge 2\)): we have \(n = 2\lfloor n/2 \rfloor + (n \bmod 2)\) with \(1 \le \lfloor n/2 \rfloor < n\). If \(\lfloor n/2 \rfloor = (d_{k-1} \dots d_0)_2\), then

      \[ n = 2\sum_{i=0}^{k-1} d_i 2^i + (n \bmod 2) = (d_{k-1} \dots d_0 \; (n \bmod 2))_2, \]

      i.e., the binary representation of \(n\) is that of \(\lfloor n/2 \rfloor\) followed by the digit \(n \bmod 2\). By the inductive hypothesis the recursive call prints \(d_{k-1} \dots d_0\), and then the algorithm prints \(n \bmod 2\).

    Number of calls. Let \(C(n)\) be the number of calls for \(n \ge 1\): \(C(1) = 1\) and \(C(n) = C(\lfloor n/2 \rfloor) + 1\) for \(n \ge 2\). We prove \(C(n) = \lfloor \log_2 n \rfloor + 1\) by strong induction: \(C(1) = 1 = \lfloor \log_2 1 \rfloor + 1\); for \(n \ge 2\), using \(\lfloor \log_2 \lfloor n/2 \rfloor \rfloor = \lfloor \log_2 n \rfloor - 1\),

    \[ C(n) = \big(\lfloor \log_2 n \rfloor - 1 + 1\big) + 1 = \lfloor \log_2 n \rfloor + 1. \]

    This is the number of binary digits of \(n\) (one digit printed per call). For \(n = 37\): \(\lfloor \log_2 37 \rfloor + 1 = 5 + 1 = 6\).