Skip to content

Exercises · Recursive versus iterative algorithms

Exercises · Chapter 18 · each solution opens with a click · Chapter 18: Recursive versus iterative algorithms · Exercises, volume 5 (PDF)

Exercise 18.1: Recursive versus iterative algorithms (E1)

Consider the following two recursive algorithms.

Algorithm: GCDRec
Input: Two natural numbers \(a\) and \(b\), not both equal to \(0\)
Output: The greatest common divisor of \(a\) and \(b\)
1function GCDRec(a, b)
2if \(b = 0\) then
3return \(a\)
4end
5return \(\texttt{GCDRec}(b,~ a \bmod b)\)
6end

Algorithm: RecBinarySearch
Input: A sorted sub-array \(a[l..r]\) and a target value \(m\)
Output: An index of \(m\) in \(a[l..r]\), or \(-1\) if \(m\) is not present
1function RecBS(a, l, r, m)
2if \(l > r\) then
3return \(-1\)
4end
5\(mid := l + \lfloor (r-l)/2 \rfloor\)
6if \(a[mid] = m\) then
7return \(mid\)
8end
9if \(a[mid] < m\) then
10return \(\texttt{RecBS}(a, mid+1, r, m)\)
11else
12return \(\texttt{RecBS}(a, l, mid-1, m)\)
13end
14end

Questions

  1. Are GCDRec and RecBS tail recursive? Justify the answer.

  2. Transform GCDRec into an equivalent iterative algorithm GCDIt, applying the mechanical elimination of the tail recursion step by step. Then execute both algorithms with \((a,b)=(1071,462)\), listing the values of the parameters in each call and in each iteration.

  3. Transform RecBS into an equivalent iterative algorithm ItBS. Then execute both algorithms on the array \(a=[2,5,8,12,16,23,38,56,72,91]\) (with \(l=1\), \(r=10\)) for \(m=23\) and for \(m=4\).

  4. Compare the recursive and the iterative versions of the two algorithms in terms of time and space. In particular, determine the depth of the recursion of GCDRec\((89,55)\) and the maximum depth of the recursion of RecBS on an array of \(n=10^6\) elements.

Solution

  1. Both algorithms are tail recursive.

    • In GCDRec the only recursive call is at line 5: its result is returned as it is, without any further operation.

    • In RecBS the recursive calls are at lines 10 and 12: in both cases the result of the call is returned as it is.

    Hence, after each recursive call, nothing remains to be done in the calling function: its frame is not needed anymore, and the call can be replaced by an update of the parameters.

  2. We apply the three rules of the mechanical elimination of tail recursion.

    • The base-case condition is \(b=0\) (line 2): the loop condition is \(b\neq 0\).

    • The tail call \(\texttt{GCDRec}(b,\, a\bmod b)\) becomes
      the simultaneous assignment \((a,b)\leftarrow(b, a\bmod b)\). Since the new value of \(b\) must be computed with the old value of \(a\), we use a temporary variable \(r\).

    • The return of the base case (return \(a\), line 3) is moved after the loop.

    Algorithm: GCDIt

    1function GCDIt(a, b)
    2while \(b \neq 0\) do
    3\(r := a \bmod b\)
    4\(a \leftarrow b\)
    5\(b \leftarrow r\)
    6end
    7return \(a\)
    8end

    Execution with \((a,b)=(1071,462)\):

    GCDRec GCDIt
    call \(a\) \(b\) \(a \bmod b\) iteration \(a\) \(b\) \(r\)
    1 1071 462 147 1 1071 462 147
    2 462 147 21 2 462 147 21
    3 147 21 0 3 147 21 0
    4 21 0 – end 21 0 –

    Both algorithms go through the same pairs \((1071,462)\), \((462,147)\), \((147,21)\), \((21,0)\) and return \(21\). GCDRec executes \(4\) calls (all active at the same time when the base case is reached); GCDIt executes \(3\) iterations.

  3. The base-case condition \(l>r\) becomes the loop condition \(l\le r\); the second base case (\(a[mid]=m\)) stays inside the loop as a return; the tail call at line 10 becomes \(l\leftarrow mid+1\) and the tail call at line 12 becomes \(r\leftarrow mid-1\) (the parameters \(a\) and \(m\) do not change); the return of \(-1\) is moved after the loop.

    Algorithm: ItBinarySearch

    1function ItBS(a, l, r, m)
    2while \(l \le r\) do
    3\(mid := l + \lfloor (r-l)/2 \rfloor\)
    4if \(a[mid] = m\) then
    5return \(mid\)
    6end
    7if \(a[mid] < m\) then
    8\(l \leftarrow mid+1\)
    9else
    10\(r \leftarrow mid-1\)
    11end
    12end
    13return \(-1\)
    14end

    The two algorithms go through the same values of \((l,r)\); for RecBS each row is a call, for ItBS each row is an iteration (the last row with \(l>r\) is the final test of the loop).

    • \(m=23\):

      call / iteration \(l\) \(r\) \(mid\) \(a[mid]\)
      1 1 10 5 \(16<23\) \(\Rightarrow\) \(l=6\)
      2 6 10 8 \(56>23\) \(\Rightarrow\) \(r=7\)
      3 6 7 6 \(23=m\) \(\Rightarrow\) return \(6\)

    • \(m=4\):

      call / iteration \(l\) \(r\) \(mid\) \(a[mid]\)
      1 1 10 5 \(16>4\) \(\Rightarrow\) \(r=4\)
      2 1 4 2 \(5>4\) \(\Rightarrow\) \(r=1\)
      3 1 1 1 \(2<4\) \(\Rightarrow\) \(l=2\)
      4 2 1 – \(l>r\) \(\Rightarrow\) return \(-1\)

    For \(m=23\) RecBS executes \(3\) calls and ItBS \(3\) iterations; for \(m=4\) RecBS executes \(4\) calls and ItBS \(3\) iterations plus the final test.

  4. Time. The iterative versions go through exactly the same values of the parameters as the recursive ones, with a constant number of steps for each call / iteration. Hence the number of steps has the same order of growth: \(\Theta(\log\min(a,b))\) in the worst case for the GCD and \(\Theta(\log_2 n)\) in the worst case for the binary search. The recursive versions only pay the (constant) overhead of the calls.

    Space. The iterative versions use \(\Theta(1)\) extra memory (the parameters and the variables \(r\) or \(mid\)). In the recursive versions all the calls stay active until the base case is reached, so the stack contains as many frames as the depth of the recursion.

    • GCDRec\((89,55)\) goes through the pairs

      \[ (89,55),(55,34),(34,21),(21,13),(13,8),(8,5),(5,3),(3,2),(2,1),(1,0), \]

      so the depth of the recursion is \(10\). Consecutive Fibonacci numbers are the worst case of Euclid's algorithm: the depth is \(\Theta(\log\min(a,b))\).

    • For RecBS on \(n\) elements the maximum depth is \(\lfloor\log_2 n\rfloor+2\) (the sizes of the sub-arrays are at most \(n,\lfloor n/2\rfloor,\dots,1\), plus the final call on the empty sub-array). For \(n=10^6\): \(\lfloor\log_2 10^6\rfloor+2=19+2=21\).

    For both algorithms, recursion gives no gain in time and a (small, logarithmic) loss in space. Since they are tail recursive, the recursion can be eliminated mechanically, obtaining loops with \(\Theta(1)\) extra memory.

Exercise 18.2: Recursive versus iterative algorithms (E2)

Consider the following recursive algorithms and input sizes.

  • (a) \(\texttt{Fact}(n)\): returns \(1\) if \(n=0\), otherwise \(n\cdot\texttt{Fact}(n-1)\); with \(n=1000\).

  • (b) \(\texttt{SumDecrease}(a,n)\): returns \(0\) if \(n=0\), otherwise \(\texttt{SumDecrease}(a,n-1)+a[n]\); with \(n=10^6\).

  • (c) \(\texttt{SumHalving}(a,l,r)\): returns \(a[l]\) if \(l=r\), otherwise \(\texttt{SumHalving}(a,l,mid)+\texttt{SumHalving}(a,mid+1,r)\) with \(mid=\lfloor(l+r)/2\rfloor\); on an array of \(n=10^6\) elements.

  • (d) Merge Sort on an array of \(n=1000\) elements (base case: sub-arrays of one element).

  • (e) Tower of Hanoi with \(n=20\) disks (base case: \(0\) disks).

  • (f) \(\texttt{FibRec}(n)\): returns \(n\) if \(n\le 1\), otherwise \(\texttt{FibRec}(n-1)+\texttt{FibRec}(n-2)\); with \(n=30\).

  • (g) Recursive fast power \(x^n\) (base case: \(n=0\); recursive call on \(\lfloor n/2\rfloor\)); with \(n=10^9\).

Assume that every stack frame occupies \(48\) bytes and that the call stack has a size of \(8\) MB \(=8\cdot 2^{20}=8\,388\,608\) bytes.

Questions

  1. Determine the depth of the recursion of each algorithm for the given input size.

  2. Determine the memory occupied by the call stack at its maximum, and say which executions cause a stack overflow.

  3. Determine the largest \(n\) for which \(\texttt{SumDecrease}(a,n)\) does not cause a stack overflow, and the depth of \(\texttt{SumHalving}\) for the same \(n\).

  4. For \(\texttt{FibRec}(30)\), compare the depth of the recursion with the total number of calls. Is the problem of this algorithm the space or the time?

Solution

  1. The depth of the recursion is the maximum number of calls active at the same time, i.e., the number of calls on the longest path from the root to a leaf of the recursion tree.

    • (a) The active calls are \(\texttt{Fact}(1000),\texttt{Fact}(999),\dots,\texttt{Fact}(0)\): depth \(n+1=1001\).

    • (b) The active calls are \(\texttt{SumDecrease}(a,10^6),\dots,\texttt{SumDecrease}(a,0)\): depth \(n+1=1\,000\,001\).

    • (c) The largest sub-array at level \(t\) of the tree has \(\lceil n/2^t\rceil\) elements, which becomes \(1\) for \(t=\lceil\log_2 n\rceil\). Depth \(\lceil\log_2 n\rceil+1\); since \(2^{19}=524\,288<10^6\le 2^{20}=1\,048\,576\), we have \(\lceil\log_2 10^6\rceil=20\) and the depth is \(21\).

    • (d) As in (c): \(\lceil\log_2 1000\rceil+1=10+1=11\) (since \(2^9=512<1000\le 2^{10}=1024\)).

    • (e) The active calls are \(\texttt{Hanoi}(20),\texttt{Hanoi}(19),\dots,\texttt{Hanoi}(0)\): depth \(n+1=21\).

    • (f) The longest path is \(\texttt{FibRec}(30),\texttt{FibRec}(29),\dots,\texttt{FibRec}(1)\): depth \(n=30\).

    • (g) The exponent goes through the values \(n,\lfloor n/2\rfloor,\dots,1,0\), i.e., the depth is \(\lfloor\log_2 n\rfloor+2\). Since \(2^{29}=536\,870\,912\le 10^9<2^{30}\), we have \(\lfloor\log_2 10^9\rfloor=29\) and the depth is \(31\).

  2. The memory of the stack at its maximum is \(48\) bytes times the depth:

    algorithm depth stack (bytes) overflow?
    (a) Fact\((1000)\) \(1\,001\) \(48\,048\) no
    (b) SumDecrease, \(n=10^6\) \(1\,000\,001\) \(48\,000\,048\) yes
    (c) SumHalving, \(n=10^6\) \(21\) \(1\,008\) no
    (d) Merge Sort, \(n=1000\) \(11\) \(528\) no
    (e) Hanoi, \(n=20\) \(21\) \(1\,008\) no
    (f) FibRec\((30)\) \(30\) \(1\,440\) no
    (g) fast power, \(n=10^9\) \(31\) \(1\,488\) no

    Only (b) causes a stack overflow: \(48\,000\,048>8\,388\,608\) bytes (about \(46\) MB against \(8\) MB).

  3. The stack contains at most \(\lfloor 8\,388\,608/48\rfloor=174\,762\) frames. \(\texttt{SumDecrease}(a,n)\) needs \(n+1\) frames, so it does not overflow if and only if

    \[ n+1\le 174\,762 \quad\Longleftrightarrow\quad n\le 174\,761. \]

    For \(n=174\,761\), since \(2^{17}=131\,072<n\le 2^{18}=262\,144\), \(\texttt{SumHalving}\) has depth \(\lceil\log_2 n\rceil+1=18+1=19\), i.e., \(912\) bytes of stack. Both algorithms execute \(\Theta(n)\) steps: the halving version uses an exponentially smaller stack.

  4. \(\texttt{FibRec}(30)\) has depth \(30\) (only \(1\,440\) bytes of stack), but it executes

    \[ 2F(31)-1=2\cdot 1\,346\,269-1=2\,692\,537 \]

    calls. The problem of FibRec is the time, \(\Theta(\varphi^n)\), not the space, \(\Theta(n)\): the depth of the recursion and the number of calls are two very different quantities.

    A depth of the recursion \(\Theta(\log_2 n)\) is never a problem in practice; a depth \(\Theta(n)\) (decrease by one) causes a stack overflow already for \(n\) of the order of \(10^5\)–\(10^6\), while the corresponding loop uses \(\Theta(1)\) memory.

Exercise 18.3: Recursive versus iterative algorithms (E3)

Consider the following four recursive algorithms.

Algorithm: A: MaxDecrease
1function MaxDec(a, n)
2if \(n = 1\) then
3return \(a[1]\)
4end
5return \(\max(\texttt{MaxDec}(a, n-1),~ a[n])\)
6end

Algorithm: B: MaxHalving
1function MaxHalf(a, l, r)
2if \(l = r\) then
3return \(a[l]\)
4end
5\(mid := \lfloor (l+r)/2 \rfloor\)
6return \(\max(\texttt{MaxHalf}(a,l,mid),\)
\(\texttt{MaxHalf}(a,mid+1,r))\)
7end

Algorithm: C: PowerDecrease
1function PowDec(x, n)
2if \(n = 0\) then
3return \(1\)
4end
5return \(x\cdot \texttt{PowDec}(x, n-1)\)
6end

Algorithm: D: Tribonacci
1function Trib(n)
2if \(n \le 2\) then
3return \(\lfloor n/2 \rfloor\)
4end
5return \(\texttt{Trib}(n-1)+\texttt{Trib}(n-2)\)
\(+\,\texttt{Trib}(n-3)\)
6end

MaxDec and MaxHalf compute the maximum of an array \(a[1..n]\) (MaxHalf is called as \(\texttt{MaxHalf}(a,1,n)\)); PowDec computes \(x^n\); Trib computes the Tribonacci numbers \(T(0)=0\), \(T(1)=0\), \(T(2)=1\), \(T(n)=T(n-1)+T(n-2)+T(n-3)\).

Questions

For each of the four algorithms:

  1. write the recurrence of the number of steps \(S(n)\) and determine its order of growth;

  2. determine the depth of the recursion and the extra memory used;

  3. indicate the best iterative algorithm seen in the course for the same problem, with its time and space;

  4. decide whether recursion gains, is equivalent, or loses, justifying the answer.

Solution

A: MaxDecrease

  1. Each call executes a constant number \(c\) of steps besides the recursive call on \(n-1\) elements:

    \[ S(n)=S(n-1)+c,\qquad S(1)=d. \]

    Unrolling, \(S(n)=d+c\,(n-1)=\Theta(n)\).

  2. The calls \(\texttt{MaxDec}(a,n),\dots,\texttt{MaxDec}(a,1)\) are all active at the same time: depth \(n\), extra memory \(\Theta(n)\). The algorithm is not tail recursive (the maximum is computed after the call returns).

  3. FindMaximum (chapter «Running time»): a loop with \(S(n)=4n-1=\Theta(n)\) steps and \(\Theta(1)\) extra memory.

  4. SAME time, LOSS in space: the decrease-by-one recursion is a loop in disguise, with a call overhead and a risk of stack overflow for large \(n\).

B: MaxHalving

  1. Two recursive calls on halves, plus a constant number of steps:

    \[ S(n)=2S(n/2)+\Theta(1). \]

    Master Theorem: \(a=2\), \(b=2\), \(f(n)=\Theta(1)\); \(n^{\log_b a}=n^{\log_2 2}=n\). Since \(f(n)=\Theta(1)=O(n^{1-\varepsilon})\) with \(\varepsilon=1\), case 1 gives \(S(n)=\Theta(n)\).

  2. Depth \(\lceil\log_2 n\rceil+1\), extra memory \(\Theta(\log_2 n)\).

  3. Again FindMaximum: \(\Theta(n)\) time, \(\Theta(1)\) space.

  4. SAME time, small LOSS in space (\(\Theta(\log_2 n)\)). Divide and conquer does not help here: the recursion tree has \(2n-1\) nodes, each with constant work, so the total work is still \(\Theta(n)\). No algorithm can do better, because every element must be examined at least once. Divide and conquer gives a gain only when it reduces the total work, as in Merge Sort, where the combination of the halves costs \(\Theta(n)\) instead of the \(\Theta(n^2)\) of the iterative algorithms.

C: PowerDecrease

  1. \(S(n)=S(n-1)+c\), \(S(0)=d\) \(\Rightarrow\) \(S(n)=c\,n+d=\Theta(n)\).

  2. Depth \(n+1\) (calls with exponent \(n,n-1,\dots,0\)), extra memory \(\Theta(n)\).

  3. The loop with \(n\) multiplications has \(\Theta(n)\) time and \(\Theta(1)\) space; the iterative square-and-multiply algorithm PowerIt has \(\Theta(\log_2 n)\) time and \(\Theta(1)\) space.

  4. LOSS: same time as the simple loop and \(\Theta(n)\) memory; compared with the square-and-multiply loop it is even exponentially slower in terms of \(\log_2 n\). Recursion is convenient for the power only when it halves the exponent (fast power): \(S(n)=S(n/2)+\Theta(1)=\Theta(\log_2 n)\).

D: Tribonacci

  1. Let \(C(n)\) be the number of calls; then \(C(0)=C(1)=C(2)=1\) and

    \[ C(n)=1+C(n-1)+C(n-2)+C(n-3),\qquad n\ge 3, \]

    and \(S(n)=\Theta(C(n))\), since each call executes a constant number of steps. The function \(C\) is non-decreasing, so for \(n\ge 3\)

    \[ C(n)\ge 3\,C(n-3)\ge 3^2C(n-6)\ge\cdots\ge 3^{\lfloor n/3\rfloor}. \]

    Hence \(S(n)=\Omega(3^{n/3})=\Omega(1.442^n)\): the algorithm is exponential. (For example \(C(10)=289\), \(C(20)=128\,287\), \(C(25)=2\,700\,421\).) In the same way, \(C(n)\le 3C(n-1)+1\) gives \(S(n)=O(3^n)\).

  2. The longest path in the recursion tree is \(\texttt{Trib}(n),\texttt{Trib}(n-1),\dots,\texttt{Trib}(2)\): depth \(n-1\), extra memory \(\Theta(n)\).

  3. A loop that computes \(T(3),T(4),\dots,T(n)\) keeping only the last three values in three variables: \(\Theta(n)\) time and \(\Theta(1)\) space.

  4. Huge LOSS: the subproblems overlap (for example \(\texttt{Trib}(n-1)\) and \(\texttt{Trib}(n-2)\) both call \(\texttt{Trib}(n-3)\)), so the same values are recomputed an exponential number of times. Memoization or the bottom-up loop (Dynamic Programming) bring the time back to \(\Theta(n)\).

recursive best iterative verdict
time space time, space
A \(\Theta(n)\) \(\Theta(n)\) \(\Theta(n)\), \(\Theta(1)\) same time, loss in space
B \(\Theta(n)\) \(\Theta(\log_2 n)\) \(\Theta(n)\), \(\Theta(1)\) same time, small loss
C \(\Theta(n)\) \(\Theta(n)\) \(\Theta(\log_2 n)\), \(\Theta(1)\) loss
D exponential \(\Theta(n)\) \(\Theta(n)\), \(\Theta(1)\) huge loss

Exercise 18.4: Recursive versus iterative algorithms (E4)

The binomial coefficients satisfy, for \(0<k<n\), the recurrence (Pascal's rule)

\[ \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},\qquad \binom{n}{0}=\binom{n}{n}=1. \]

Consider the following recursive algorithm.

Algorithm: BinomRec
Input: Two natural numbers \(n\) and \(k\) with \(0\le k\le n\)
Output: The binomial coefficient \(\binom{n}{k}\)
1function BinomRec(n, k)
2if \(k = 0\) or \(k = n\) then
3return \(1\)
4end
5return \(\texttt{BinomRec}(n-1, k-1) + \texttt{BinomRec}(n-1, k)\)
6end

Questions

  1. Draw the recursion tree of \(\texttt{BinomRec}(4,2)\), count the calls and indicate the subproblems that are solved more than once.

  2. Prove that the number of calls executed by \(\texttt{BinomRec}(n,k)\) is \(N(n,k)=2\binom{n}{k}-1\).

  3. Compute \(N(10,5)\), \(N(30,15)\) and \(N(40,20)\), and estimate the time needed by \(\texttt{BinomRec}(40,20)\) on a computer that executes \(10^9\) calls per second.

  4. Write a memoized version BinomMemo and prove that, for \(0<k<n\), it executes exactly \(2k(n-k)+1\) calls. Compute this number for the three cases of question 3.

  5. Write an iterative algorithm that computes \(\binom{n}{k}\) row by row (Pascal's triangle), and give its time and space.

Solution

  1. Each node is a call, labelled with \((n,k)\); the leaves are base cases (\(k=0\) or \(k=n\)) and return \(1\).

    Figure 1

    The tree has \(11\) nodes, i.e., \(11\) calls, and \(6=\binom{4}{2}\) leaves. The subproblem \((2,1)\) is solved twice (and so are its sub-calls \((1,0)\) and \((1,1)\)).

  2. Every call is either a leaf (base case, returns \(1\)) or an internal node with exactly two children. The value returned by a call is the sum of the values returned by the leaves of its sub-tree, i.e., the number of its leaves. Hence the tree of \(\texttt{BinomRec}(n,k)\) has \(\binom{n}{k}\) leaves.

    In a tree in which every internal node has exactly two children, the number of internal nodes is the number of leaves minus one (by induction: a single leaf has \(0\) internal nodes; joining two such trees with \(L_1\) and \(L_2\) leaves under a new root gives \((L_1-1)+(L_2-1)+1=(L_1+L_2)-1\) internal nodes). Therefore

    \[ N(n,k)=\binom{n}{k}+\left(\binom{n}{k}-1\right)=2\binom{n}{k}-1. \]

    For example \(N(4,2)=2\cdot 6-1=11\), as in question 1.

3.

$$
N(10,5)=2\cdot 252-1=503,\qquad N(30,15)=2\cdot 155\,117\,520-1=310\,235\,039,
$$

$$
N(40,20)=2\cdot 137\,846\,528\,820-1=275\,693\,057\,639.
$$

At $10^9$ calls per second, $\texttt{BinomRec}(40,20)$ needs about $275.7$ seconds, i.e., more than $4.5$ minutes, to compute a number that can be obtained with a few hundred additions (see questions 4 and 5). Since $\binom{2m}{m}\ge \frac{4^m}{2m+1}$, the number of calls grows exponentially.

  1. We store the values already computed in a table \(memo\), indexed by the pair \((i,j)\):

    Algorithm: BinomMemo

    Input: Natural numbers \(0\le k\le n\) and a table \(memo\) whose entries are all undefined
    Output: The binomial coefficient \(\binom{n}{k}\)
    1function BinomMemo(n, k, memo)
    2if \(k = 0\) or \(k = n\) then
    3return \(1\)
    4end
    5if \(memo[n][k]\) is undefined then
    6\(memo[n][k] \leftarrow \texttt{BinomMemo}(n-1,k-1,memo)+\texttt{BinomMemo}(n-1,k,memo)\)
    7end
    8return \(memo[n][k]\)
    9end

    Number of calls. Starting from \((n,k)\), a call reaches the pairs \((n-s,\,k-t)\), where \(s\) is the number of steps down and \(t\le s\) is the number of these steps in which \(k\) decreases. Let \(u=s-t\) be the number of steps in which \(k\) does not decrease. A pair is internal (not a base case) if \(k-t\ge 1\) and \((n-s)-(k-t)\ge 1\), i.e.,

    \[ 0\le t\le k-1 \qquad\text{and}\qquad 0\le u\le n-k-1, \]

    so there are exactly \(k(n-k)\) internal subproblems, and all of them are reached. The body of each internal subproblem (the two recursive calls) is executed only the first time it is called; the following times the value is read from \(memo\). Every call, except the first one, is made by the body of an internal subproblem, which makes exactly \(2\) calls. Therefore the number of calls is

    \[ 1+2k(n-k). \]

    For the three cases:

    \[ (10,5):~1+2\cdot 25=51,\qquad (30,15):~1+2\cdot 225=451,\qquad (40,20):~1+2\cdot 400=801, \]

    against \(503\), \(310\,235\,039\) and \(275\,693\,057\,639\) calls of BinomRec. The time is \(\Theta(k(n-k))\) and the memory is \(\Theta(k(n-k))\) for the table plus \(\Theta(n)\) for the stack (depth \(\le n\)).

  2. Row \(i\) of Pascal's triangle is computed from row \(i-1\). Keeping a single array \(c[0..k]\) and updating it from right to left (so that \(c[j-1]\) still contains the value of the previous row when \(c[j]\) is updated):

    Algorithm: BinomIt

    Input: Two natural numbers \(n\) and \(k\) with \(0\le k\le n\)
    Output: The binomial coefficient \(\binom{n}{k}\)
    1function BinomIt(n, k)
    2\(c[0] := 1\); \(c[1..k] := 0\)
    3\(i := 1\)
    4while \(i \le n\) do
    5\(j := \min(i,k)\)
    6while \(j \ge 1\) do
    7\(c[j] \leftarrow c[j] + c[j-1]\)
    8\(j \leftarrow j-1\)
    9end
    10\(i \leftarrow i+1\)
    11end
    12return \(c[k]\)
    13end

    After the \(i\)-th iteration of the outer loop, \(c[j]=\binom{i}{j}\) for \(0\le j\le \min(i,k)\). The inner loop is executed at most \(k\) times for each of the \(n\) rows: time \(O(n\,k)\) (and \(\Theta(nk)\) when \(k\le n/2\)), extra memory \(\Theta(k)\), no recursion. For \((40,20)\) the algorithm executes \(\sum_{i=1}^{40}\min(i,20)=210+400=610\) additions.

    The naive recursion is exponential because the subproblems overlap; memoization (top-down) and the iterative Pascal's triangle (bottom-up) solve each subproblem once, with a polynomial number of steps. This is the idea of Dynamic Programming.

Exercise 18.5: Recursive versus iterative algorithms (E5)

Consider the two following algorithms for the Fibonacci numbers (\(F(0)=0\), \(F(1)=1\), \(F(n)=F(n-1)+F(n-2)\)).

Algorithm: FibRec
1function FibRec(n)
2if \(n \le 1\) then
3return \(n\)
4end
5return \(\texttt{FibRec}(n-1)\)
\(+\,\texttt{FibRec}(n-2)\)
6end

Algorithm: FibIt
1function FibIt(n)
2if \(n \le 1\) then
3return \(n\)
4end
5\(prev := 0\)
6\(curr := 1\)
7\(i := 2\)
8while \(i \le n\) do
9\(next := prev + curr\)
10\(prev \leftarrow curr\)
11\(curr \leftarrow next\)
12\(i \leftarrow i+1\)
13end
14return \(curr\)
15end

Assume that every line executed counts as one step (line 5 counts as one step, besides the steps of the two sub-calls) and that the computer executes \(10^9\) steps per second.

Questions

  1. Determine the exact number of steps \(S_{it}(n)\) executed by FibIt for \(n\ge 2\).

  2. Determine the exact number of steps \(S_{rec}(n)\) executed by FibRec, using the fact that FibRec\((n)\) executes \(2F(n+1)-1\) calls.

  3. Estimate the running times of the two algorithms for \(n=50\), knowing that

    \[ F(51)=20\,365\,011\,074. \]

  4. Estimate the running time of FibRec for \(n=60\) and \(n=100\), knowing that

    \[ F(61)=2\,504\,730\,781\,961 \qquad\text{and}\qquad F(101)\approx 5.73\cdot 10^{20}. \]

  5. Determine the largest \(n\) for which FibRec terminates within one hour, knowing that

    \[ F(58)=591\,286\,729\,879\qquad\text{and}\qquad F(59)=956\,722\,026\,041. \]
Solution

  1. For \(n\ge 2\) the number of times each line of FibIt is executed is:

    • Line 2 is executed \(1\) time (the return in the next line is not executed)

    • Lines 5, 6, 7 are executed \(1\) time each

    • Line 8 is executed \(n\) times (\(i=2,3,\dots,n+1\))

    • Lines 9, 10, 11, 12 are executed \(n-1\) times each

    • Line 14 is executed \(1\) time

    Therefore

    \[ S_{it}(n)=1+3+n+4(n-1)+1=5n+1=\Theta(n). \]

  2. Every call of FibRec executes exactly \(2\) steps of its own: line 2 and then either line 3 (base case) or line 5. Since \(\texttt{FibRec}(n)\) executes \(2F(n+1)-1\) calls,

    \[ S_{rec}(n)=2\big(2F(n+1)-1\big)=4F(n+1)-2=\Theta(\varphi^n). \]

  3. For \(n=50\):

    \[ S_{it}(50)=5\cdot 50+1=251 \text{ steps}\quad\Longrightarrow\quad \frac{251}{10^9}\text{ s}=251\text{ ns}, \]
    \[ S_{rec}(50)=4\cdot 20\,365\,011\,074-2=81\,460\,044\,294 \text{ steps}\quad\Longrightarrow\quad \approx 81.5 \text{ s}. \]

    The recursive algorithm is about \(3\cdot 10^8\) times slower.

  4. For \(n=60\):

    \[ S_{rec}(60)=4\cdot 2\,504\,730\,781\,961-2=10\,018\,923\,127\,842\text{ steps}\quad\Longrightarrow\quad\approx 10\,019\text{ s}\approx 2.8\text{ hours}. \]

    For \(n=100\):

    \[ S_{rec}(100)\approx 4\cdot 5.73\cdot 10^{20}\approx 2.29\cdot 10^{21}\text{ steps}\quad\Longrightarrow\quad\approx 2.29\cdot 10^{12}\text{ s}. \]

    Since one year has about \(3.156\cdot 10^7\) seconds, this is about \(7.3\cdot 10^4\) years. Meanwhile, FibIt\((100)\) executes \(501\) steps, i.e., about half a microsecond.

  5. One hour corresponds to \(3600\cdot 10^9=3.6\cdot 10^{12}\) steps. We need

    \[ 4F(n+1)-2\le 3.6\cdot 10^{12}\quad\Longleftrightarrow\quad F(n+1)\le 9\cdot 10^{11}+0.5. \]

    Since \(F(58)=591\,286\,729\,879\le 9\cdot 10^{11}<F(59)=956\,722\,026\,041\), the condition holds for \(n+1\le 58\). The largest \(n\) is \(n=57\), with

    \[ S_{rec}(57)=4\cdot 591\,286\,729\,879-2=2\,365\,146\,919\,514\text{ steps}\approx 39\text{ minutes}, \]

    while \(n=58\) already needs \(4F(59)-2\approx 3.83\cdot 10^{12}\) steps, i.e., about \(64\) minutes. Every time \(n\) increases by \(1\), the time of FibRec is multiplied by about \(\varphi\approx 1.618\): a computer \(10\) times faster would only allow to increase \(n\) by \(\log_\varphi 10\approx 4.8\).

    With an exponential algorithm, faster computers do not help: the size of the problems that can be solved grows only by an additive constant. The iterative algorithm, with \(5n+1\) steps, computes \(F(57)\) in less than \(0.3\) microseconds.