Algorithms : Recursion

Contents

Recursive Algorithms

• Factorial
• Unsorted Array Search
• Sorted Array Search
• Integer Product
• Exponentation or Power Function
• Array Sum
• Fibonacci Number
• Towers of Hanoi
• Largest Common Divisor

Recursion

Recursion is self-repetition or self-reproduction or self-reference.

Why care for recursion?

• Nature $\rightarrow$ repetition in unicellular organisms
• Nature $\rightarrow$ reproduction in multicellular organisms
• Nature $\rightarrow$ fractals
• Natural languages $\rightarrow$ sentences
• Mathematics $\rightarrow$ recursive functions
• Computer science $\rightarrow$ recursive functions
• Computer science $\rightarrow$ algorithm design techniques
• Decrease-and-conquer
• Divide-and-conquer
• Dynamic programming
• Backtracking

Factorial

$$ \begin{align} \text{Recursive definition: } &n! = \begin{cases} 1 & \text{if } n = 0,\\ n \cdot (n - 1)! & \text{if } n > 0. \end{cases}\\ \text{Nonrecursive definition: } &n! = \begin{cases} 1 & \text{if } n = 0,\\ n \cdot (n - 1) \cdot \cdots \cdot 3 \cdot 2 \cdot 1 & \text{if } n > 0. \end{cases} \end{align} $$

\begin{algorithm}
\caption{Recursive Factorial Algorithm}
\begin{algorithmic}
\REQUIRE $n$: a non-negative integer
\ENSURE $n!$: the factorial of $n$
\FUNCTION{Factorial}{$n$}
    \IF{$n = 0$}
        \RETURN 1
    \ELSE
        \RETURN $n \times$ \CALL{Factorial}{$n-1$}
    \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
    \caption{Nonrecursive Factorial Algorithm}
    \begin{algorithmic}
    \REQUIRE $n$: a non-negative integer
    \ENSURE $n!$: the factorial of $n$
    \FUNCTION{Factorial}{$n$}
        \STATE $factorial \leftarrow 1$
        \FOR{$i \leftarrow 1$ \TO $n$}
          \STATE $factorial \leftarrow factorial \times i$
        \ENDFOR
        \RETURN $factorial$
	  \ENDFUNCTION
    \end{algorithmic}
\end{algorithm}

Compute $\text{Factorial}(5)$. Suppose the main function calls $\text{Factorial}(5)$.

• $\text{Factorial}(5) = 5 \times \text{Factorial}(4)$
• $\text{Factorial}(4) = 4 \times \text{Factorial}(3)$
• $\text{Factorial}(3) = 3 \times \text{Factorial}(2)$
• $\text{Factorial}(2) = 2 \times \text{Factorial}(1)$
• $\text{Factorial}(1) = 1 \times \text{Factorial}(0)$
• $\text{Factorial}(0) = 1$
• $\text{Factorial}(1) = 1 \times 1 = 1$
• $\text{Factorial}(2) = 2 \times 1 = 2$
• $\text{Factorial}(3) = 3 \times 2 = 6$
• $\text{Factorial}(4) = 4 \times 6 = 24$
• $\text{Factorial}(5) = 5 \times 24 = 120$
• $\text{Factorial}(5)$ returns $120$ to the main function

Algorithm	Time $T(n)$	Space $S(n)$
Recursive	$\begin{align} &= \left. \begin{cases} \Theta(1) & \text{if } n = 0,\\ T(n-1) + \Theta(1) & \text{if } n > 0. \end{cases} \right\} \in \Theta(n) \end{align}$	$\begin{align} &= \left. \begin{cases} \Theta(1) & \text{if } n = 0,\\ S(n-1) + \Theta(1) & \text{if } n > 0. \end{cases} \right\} \in \Theta(n) \end{align}$
Nonrecursive	$\Theta(n)$	$\Theta(1)$

Unsorted array search

\begin{algorithm}
\caption{Recursive Linear Search}
\begin{algorithmic}
\REQUIRE Array $A$, target element $x$, start index $low$, end index $high$
\ENSURE Index of $x$ in $A[low...high]$, or -1 if not found

\FUNCTION{LinearSearch}{$A[low \ldots high], x$}
    \IF{$low > high$}
        \RETURN $-1$ \COMMENT{Base case: empty range, element not found}
    \ENDIF
    
    \IF{$A[low] = x$}
        \RETURN $low$ \COMMENT{Base case: element found at low index}
    \ENDIF
    
    \RETURN \CALL{LinearSearch}{$A[(low + 1) \ldots high], x$} \COMMENT{Recursive case}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Nonrecursive Linear Search}
\begin{algorithmic}
\REQUIRE Array $A[1...n]$, target element $x$
\ENSURE Index of $x$ in $A$, or -1 if not found

\FUNCTION{LinearSearch}{$A[1 \ldots n], x$}
    \FOR{$i \gets 1$ \TO $n$}
        \IF{$A[i] = x$}
            \RETURN $i$
        \ENDIF
    \ENDFOR
    \RETURN $-1$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Algorithm	Time $T(n)$	Space $S(n)$
Recursive	$\begin{align} &= \left. \begin{cases} \Theta(1) & \text{if } n = 0,\\ T(n-1) + \Theta(1) & \text{if } n > 0. \end{cases} \right\} \in \Theta(n) \end{align}$	$\begin{align} &= \left. \begin{cases} \Theta(1) & \text{if } n = 0,\\ S(n-1) + \Theta(1) & \text{if } n > 0. \end{cases} \right\} \in \Theta(n) \end{align}$
Nonrecursive	$\Theta(n)$	$\Theta(1)$

Sorted array search

\begin{algorithm}
\caption{Recursive Binary Search}
\begin{algorithmic}
\REQUIRE Sorted array $A[1...n]$, target element $x$
\ENSURE Index of $x$ in $A$, or -1 if not found

\FUNCTION{BinarySearch}{$A[1 \ldots n], x$}
    \RETURN \CALL{BinarySearch-Recursive}{$A[1 \ldots n], x$}
\ENDFUNCTION

\FUNCTION{BinarySearch-Recursive}{$A[low \ldots high], x$}
    \IF{$low > high$}
        \RETURN $-1$ \COMMENT{Base case: element not found}
    \ENDIF
    
    \STATE $mid \gets \left\lfloor \frac{low + high}{2} \right\rfloor$
    
    \IF{$A[mid] = x$}
        \RETURN $mid$ \COMMENT{Base case: element found}
    \ELSIF{$A[mid] < x$}
        \RETURN \CALL{BinarySearch-Recursive}{$A[(mid + 1) \ldots high], x$} \COMMENT{Search right half}
    \ELSE
        \RETURN \CALL{BinarySearch-Recursive}{$A[low \ldots (mid - 1)], x$} \COMMENT{Search left half}
    \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Nonrecursive Binary Search}
\begin{algorithmic}
\REQUIRE Sorted array $A[1...n]$, target element $x$
\ENSURE Index of $x$ in $A$, or -1 if not found

\FUNCTION{BinarySearch}{$A[1 \ldots n], x$}
    \STATE $low \gets 1$
    \STATE $high \gets n$
    
    \WHILE{$low \leq high$}
        \STATE $mid \gets \left\lfloor \frac{low + high}{2} \right\rfloor$
        
        \IF{$A[mid] = x$}
            \RETURN $mid$ \COMMENT{Element found}
        \ELSIF{$A[mid] < x$}
            \STATE $low \gets mid + 1$ \COMMENT{Search in right half}
        \ELSE
            \STATE $high \gets mid - 1$ \COMMENT{Search in left half}
        \ENDIF
    \ENDWHILE
    
    \RETURN $-1$ \COMMENT{Element not found}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Algorithm	Time $T(n)$	Space $S(n)$
Recursive	$\begin{align} &\le \left. \begin{cases} \Theta(1) & \text{if } n = 1,\\ T(n/2) + \Theta(1) & \text{if } n > 1. \end{cases} \right\} \in O(\log n) \end{align}$	$\begin{align} &\le \left. \begin{cases} \Theta(1) & \text{if } n = 1,\\ S(n/2) + \Theta(1) & \text{if } n > 1. \end{cases} \right\} \in O(\log n) \end{align}$
Nonrecursive	$O(\log n)$	$\Theta(1)$

Integer Product

\begin{algorithm}
\caption{Product: Recursive Decrease-and-Conquer (decrease $b$)}
\begin{algorithmic}
\REQUIRE Whole numbers $a, b$
\ENSURE $a \times b$
\FUNCTION{Product}{$a, b$}
  \IF{$b = 0$}
    \RETURN $0$
  \ELSE
    \RETURN $a$ + \CALL{Product}{$a, b-1$}
  \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Product: Recursive Decrease-and-Conquer (decrease $a$)}
\begin{algorithmic}
\REQUIRE Whole numbers $a, b$
\ENSURE $a \times b$
\FUNCTION{Product}{$a, b$}
  \IF{$a = 0$}
    \RETURN $0$
  \ELSE
    \RETURN $b$ + \CALL{Product}{$a-1, b$}
  \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Product: Recursive Decrease-and-Conquer (use $\max(a,b)$ and $\min(a,b)$)}
\begin{algorithmic}
\REQUIRE Whole numbers $a, b$
\ENSURE $a \times b$
\FUNCTION{Multiply}{$a, b$}
  \RETURN \CALL{Product}{$\max(a,b), \min(a,b)$}
\ENDFUNCTION
\FUNCTION{Product}{$a, b$}
  \IF{$b = 0$}
    \RETURN $0$
  \ELSE
    \RETURN $a +$ \CALL{Product}{$a, b-1$}
  \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Product: Nonrecursive Algorithm (repeat $a$ for $b$ times)}
\begin{algorithmic}
\REQUIRE Whole numbers $a, b$
\ENSURE $a \times b$
\FUNCTION{Product}{$a, b$}
  \STATE $product \leftarrow 0$
  \FOR{$i \leftarrow 1$ \TO $b$}
    \STATE $product \leftarrow product + a$
  \ENDFOR
  \RETURN $product$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Product: Nonrecursive Algorithm (repeat $b$ for $a$ times)}
\begin{algorithmic}
\REQUIRE Whole numbers $a, b$
\ENSURE $a \times b$
\FUNCTION{Product}{$a, b$}
  \STATE $product \leftarrow 0$
  \FOR{$i \leftarrow 1$ \TO $a$}
    \STATE $product \leftarrow product + b$
  \ENDFOR
  \RETURN $product$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Product: Nonrecursive Algorithm (repeat $\max(a,b)$ for $\min(a,b)$ times)}
\begin{algorithmic}
\REQUIRE Whole numbers $a, b$
\ENSURE $a \times b$
\FUNCTION{Product}{$a, b$}
  \STATE $product \leftarrow 0$
  \FOR{$i \leftarrow 1$ \TO $\min(a,b)$}
    \STATE $product \leftarrow product + \max(a,b)$
  \ENDFOR
  \RETURN $product$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Product: Recursive Divide-and-Conquer}
\begin{algorithmic}
\REQUIRE Whole numbers $a, b$
\ENSURE $a \times b$
\FUNCTION{Multiply}{$a, b$}
  \RETURN \CALL{Product}{$\max(a,b), \min(a,b)$}
\ENDFUNCTION
\FUNCTION{Product}{$a, b$}
  \IF{$b = 0$}
    \RETURN $0$
  \ENDIF
  \STATE $part1 \leftarrow$ \CALL{Product}{$a, b/2$}
  \STATE $part2 \leftarrow$ \CALL{Product}{$a, b/2$}
  \IF{$b $ \% $2 = 1$}
    \RETURN $part1 + part2 + a$
  \ELSE
    \RETURN $part1 + part2$
  \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Product: Recursive Decrease-and-Conquer (fast)}
\begin{algorithmic}
\REQUIRE Whole numbers $a, b$
\ENSURE $a \times b$
\FUNCTION{Multiply}{$a, b$}
  \RETURN \CALL{Product}{$\max(a,b), \min(a,b)$}
\ENDFUNCTION
\FUNCTION{Product}{$a, b$}
  \IF{$b = 0$}
    \RETURN $0$
  \ENDIF
  \STATE $partial \leftarrow$ \CALL{Product}{$a, b/2$}
  \IF{$b$ \% $2 = 1$}
    \RETURN $partial + partial + a$
  \ELSE
    \RETURN $partial + partial$
  \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Product: Recursive Decrease-and-Conquer (fast)}
\begin{algorithmic}
\REQUIRE Whole numbers $a, b$
\ENSURE $a \times b$
\FUNCTION{Multiply}{$a, b$}
  \RETURN \CALL{Product}{$\max(a,b), \min(a,b)$}
\ENDFUNCTION
\FUNCTION{Product}{$a, b$}
  \IF{$b = 0$}
    \RETURN $0$
  \ENDIF
  \STATE $partial \leftarrow$ \CALL{Product}{$a, b/3$}
  \IF{$b$ \% $3 = 1$}
    \RETURN $partial + partial + partial + a$
  \ELSIF{$b$ \% $3 = 2$}
    \RETURN $partial + partial + partial + a + a$
  \ELSE
    \RETURN $partial + partial + partial$
  \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Let $n = \min(a,b)$

Algorithm	Time $T(\cdot)$	Space $S(\cdot)$
Recursive (decrease $b$)	$\begin{align} T(a) &= \left.\begin{cases} \Theta(1) & \text{if } a = 0,\\ T(a-1) + \Theta(1) & \text{if } a > 0. \end{cases}\right\} \in \Theta(a) \end{align}$	$\begin{align} S(b) &= \left.\begin{cases} \Theta(1) & \text{if } b = 0,\\ S(b-1) + \Theta(1) & \text{if } b > 0. \end{cases}\right\} \in \Theta(b) \end{align}$
Recursive (decrease $a$)	$\begin{align} T(a) &= \left.\begin{cases} \Theta(1) & \text{if } a = 0,\\ T(a-1) + \Theta(1) & \text{if } a > 0. \end{cases}\right\} \in \Theta(a) \end{align}$	$\begin{align} S(a) &= \left.\begin{cases} \Theta(1) & \text{if } a = 0,\\ S(a-1) + \Theta(1) & \text{if } a > 0. \end{cases}\right\} \in \Theta(a) \end{align}$
Recursive (use max$(a,b)$ and min$(a,b)$)	$\begin{align} T(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ T(n-1) + \Theta(1) & \text{if } n > 0. \end{cases}\right\}\\ &\in \Theta(n) = \Theta(\min(a,b)) \end{align}$	$\begin{align} S(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ S(n-1) + \Theta(1) & \text{if } n > 0. \end{cases}\right\}\\ &\in \Theta(n) = \Theta(\min(a,b)) \end{align}$
Nonrecursive (repeat $a$ for $b$ times)	$\Theta(b)$	$\Theta(1)$
Nonrecursive (repeat $b$ for $a$ times)	$\Theta(a)$	$\Theta(1)$
Nonrecursive (repeat max$(a, b)$ for min$(a, b)$ times)	$\Theta(\min(a,b))$	$\Theta(1)$
Recursive DC (slow)	$\begin{align} T(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ 2T(n/2) + \Theta(1) & \text{if } n > 0. \end{cases}\right\}\\ &\in \Theta(n) = \Theta(\min(a,b)) \end{align}$	$\begin{align} S(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ S(n/2) + \Theta(1) & \text{if } n > 0. \end{cases}\right\}\\ &\in \Theta(\log n) = \Theta(\log \min(a,b)) \end{align}$
Recursive DC (fast, 2-way)	$\begin{align} T(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ T(n/2) + \Theta(1) & \text{if } n > 0. \end{cases}\right\}\\ &\in \Theta(\log n) = \Theta(\log \min(a,b)) \end{align}$	$\begin{align} S(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ S(n/2) + \Theta(1) & \text{if } n > 0. \end{cases}\right\}\\ &\in \Theta(\log n) = \Theta(\log \min(a,b)) \end{align}$
Recursive DC (fast, 3-way)	$\begin{align} T(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ T(n/3) + \Theta(1) & \text{if } n > 0. \end{cases}\right\}\\ &\in \Theta(\log n) = \Theta(\log \min(a,b)) \end{align}$	$\begin{align} S(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ S(n/3) + \Theta(1) & \text{if } n > 0. \end{cases}\right\}\\ &\in \Theta(\log n) = \Theta(\log \min(a,b)) \end{align}$

Exponentiation or power function

\begin{algorithm}
\caption{Exponentiation: Recursive Algorithm}
\begin{algorithmic}
\REQUIRE Element $a$, integer $n \ge 0$
\ENSURE $a^n$

\FUNCTION{Power}{$a, n$}
  \IF{$n = 0$}
    \RETURN $1$
  \ELSE
    \RETURN $a \times$ \CALL{Power}{$a, n-1$}
  \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Exponentiation: Nonrecursive Algorithm}
\begin{algorithmic}
\REQUIRE Element $a$, integer $n \ge 0$
\ENSURE $a^n$

\FUNCTION{Power}{$a, n$}
  \STATE $result \leftarrow 1$
  \FOR{$i \leftarrow 1$ \TO $n$}
    \STATE $result \leftarrow result \times a$
  \ENDFOR
  \RETURN $result$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Divide-by-2 algorithm

Observation:
$$ \begin{align*} a^{10} &= (a^5)^2\\ a^{5} &= (a^2)^2 \times a\\ a^{2} &= (a^1)^2\\ a^{1} &= (a^0)^2 \times a\\ a^{0} &= 1 \end{align*} $$ Core idea: repeated squaring / doubling: $$ \begin{align*} a^{n} &= \left. \begin{cases} 1 & \text{if } n = 0, \\ ( a^{\lfloor n/2 \rfloor} )^2 & \text{if } n > 0 \text{ and $n$ is even},\\ ( a^{\lfloor n/2 \rfloor} )^2 \times a & \text{if } n > 0 \text{ and $n$ is odd.} \end{cases} \right\} \end{align*} $$

\begin{algorithm}
\caption{Exponentiation: Recursive Decrease-and-Conquer (repeated squaring / doubling)}
\begin{algorithmic}
\REQUIRE Element $a$, integer $n \ge 0$
\ENSURE $a^n$

\FUNCTION{Power}{$a, n$}
  \IF{$n = 0$}
    \RETURN $1$
  \ENDIF
  \STATE $result \leftarrow$ \CALL{Power}{$a, \lfloor n/2 \rfloor$}
  \STATE $result \leftarrow result \times result$
  \IF{$n$ is odd}
    \STATE $result \leftarrow result \times a$
  \ENDIF
  \RETURN $result$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Exponentiation: Nonrecursive (repeated squaring / doubling)}
\begin{algorithmic}
\REQUIRE Element $a$ (real number), exponent $n$ (non-negative integer)
\ENSURE $a^n$ 

\FUNCTION{Power}{$a, n$}
    \STATE $result \gets 1$
    \STATE $base \gets a$
    \STATE $exp \gets n$
    
    \WHILE{$exp > 0$}
        \IF{$exp$ is odd} \COMMENT{If current exponent bit is 1}
            \STATE $result \gets result \times base$
        \ENDIF
        \STATE $base \gets base \times base$ \COMMENT{Square the base}
        \STATE $exp \gets \left\lfloor \frac{exp}{2} \right\rfloor$ \COMMENT{Shift right (divide by 2)}
    \ENDWHILE
    
    \RETURN $result$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Algorithm	Time $T(n)$	Space $S(n)$
Recursive	$\begin{align} T(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ T(n-1) + \Theta(1) & \text{if } n > 0. \end{cases}\right\} \in \Theta(n) \end{align}$	$\begin{align} S(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ S(n-1) + \Theta(1) & \text{if } n > 0. \end{cases}\right\} \in \Theta(n) \end{align}$
Nonrecursive	$\Theta(n)$	$\Theta(1)$
Recursive (repeated squaring / doubling)	$\begin{align} T(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ T(n/2) + \Theta(1) & \text{if } n > 0. \end{cases}\right\} \in \Theta(\log n) \end{align}$	$\begin{align} S(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 0,\\ S(n/2) + \Theta(1) & \text{if } n > 0. \end{cases}\right\} \in \Theta(\log n) \end{align}$
Nonrecursive (repeated squaring / doubling)	$\Theta(\log n)$	$\Theta(1)$

How can we compute $a^n$ when $n$ is a rational/real number?
Please note that there can be multiple solutions to $a^n$, when $n$ is a real number but not an integer. E.g. $a^{1/100}$ has 100 roots.

Array sum

\begin{algorithm}
\caption{Array sum: Recursive Decrease-and-Conquer}
\begin{algorithmic}
\REQUIRE Array $A[1 \ldots n]$
\ENSURE $\sum_{i=1}^{n} A[i]$
\FUNCTION{ArraySum}{$A[low \ldots high]$}
  \IF{$low = high$}
    \RETURN $A[low]$
  \ENDIF
  \RETURN \CALL{ArraySum}{$A[low \ldots (high-1)]$} + $A[high]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Array sum: Nonrecursive algorithm}
\begin{algorithmic}
\REQUIRE Array $A[1 \ldots n]$
\ENSURE $\sum_{i=1}^{n} A[i]$
\FUNCTION{ArraySum}{$A[1 \ldots n]$}
  \STATE $sum \leftarrow 0$
  \FOR{$i \leftarrow 1$ \TO $n$}
    \STATE $sum \leftarrow sum + A[i]$
  \ENDFOR
  \RETURN $sum$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Array sum: Recursive Divide-and-Conquer}
\begin{algorithmic}
\REQUIRE Array $A[1 \ldots n]$
\ENSURE $\sum_{i=1}^{n} A[i]$
\FUNCTION{ArraySum}{$A[low \ldots high]$}
  \IF{$low > high$}
    \RETURN $0$
  \ENDIF
  \IF{$low = high$}
    \RETURN $A[low]$
  \ENDIF
  \STATE $mid \leftarrow \left\lfloor \frac{low + high}{2} \right\rfloor$
  \STATE $leftsum \leftarrow$ \CALL{ArraySum}{$A[low \ldots mid]$}
  \STATE $rightsum \leftarrow$ \CALL{ArraySum}{$A[(mid+1) \ldots high]$}
  \RETURN $(leftsum + rightsum)$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Algorithm	Time $T(n)$	Space $S(n)$
Recursive	$\begin{aligned} T(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 1,\\ T(n-1) + \Theta(1) & \text{if } n > 1. \end{cases}\right\} \in \Theta(n) \end{aligned}$	$\begin{aligned} S(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 1,\\ S(n-1) + \Theta(1) & \text{if } n > 1. \end{cases}\right\} \in \Theta(n) \end{aligned}$
Nonrecursive	$\Theta(n)$	$\Theta(1)$
Recursive DC	$\begin{aligned} T(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 1,\\ 2T(n/2) + \Theta(1) & \text{if } n > 1. \end{cases}\right\} \in \Theta(n) \end{aligned}$	$\begin{aligned} S(n) &= \left.\begin{cases} \Theta(1) & \text{if } n = 1,\\ S(n/2) + \Theta(1) & \text{if } n > 1. \end{cases}\right\}\in \Theta(\log n) \end{aligned}$

Fibonacci number

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12	$\cdots$
$F_n$	0	1	1	2	3	5	8	13	21	34	55	89	144	$\cdots$

\begin{algorithm}
\caption{Fibonacci number: Recursive Algorithm}
\begin{algorithmic}
\REQUIRE Integer $n \ge 0$
\ENSURE $F_n$

\FUNCTION{F}{$n$}
  \IF{$n = 0$ \OR $n = 1$}
    \RETURN $n$
  \ENDIF
  \RETURN \CALL{F}{$n-1$} + \CALL{F}{$n-2$}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Fibonacci number: Top-down DP}
\begin{algorithmic}
\REQUIRE Integer $n \ge 0$
\ENSURE $F_n$

\FUNCTION{F}{$n$}
\STATE Create global array $f[0 \ldots n]$; $f[0] \leftarrow 0$; $f[1] \leftarrow 1$
    \FOR{$i \leftarrow 2$ \TO $n$}
        \STATE $f[i] \leftarrow -1$
    \ENDFOR
    \RETURN \CALL{G}{$n$}
\ENDFUNCTION

\FUNCTION{G}{$n$}
  \IF{$f[n] = -1$}
    \STATE $f[n] \leftarrow$ \CALL{G}{$n-1$} + \CALL{G}{$n-2$}
  \ENDIF
  \RETURN $f[n]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Fibonacci number: Bottom-up DP}
\begin{algorithmic}
\REQUIRE Integer $n \ge 0$
\ENSURE $F_n$

\FUNCTION{F}{$n$}
\STATE Create array $f[0 \ldots n]$; $f[0] \leftarrow 0$; $f[1] \leftarrow 1$
\FOR{$i \leftarrow 2$ \TO $n$}
  \STATE $f[i] \leftarrow f[i-1] + f[i-2]$
\ENDFOR
\RETURN $f[n]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Fibonacci number: Space-optimized Bottom-up DP}
\begin{algorithmic}
\REQUIRE Integer $n \ge 0$
\ENSURE $F_n$

\FUNCTION{F}{$n$}
\STATE $curr \leftarrow 0$, $prev \leftarrow 1$
\FOR{$i \leftarrow 1$ \TO $n$}
  \STATE $next \leftarrow curr + prev$
  \STATE $prev \leftarrow curr$
  \STATE $curr \leftarrow next$
\ENDFOR
\RETURN $curr$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Algorithm	Time $T(n)$	Space $S(n)$
Recursive	$\begin{align} T(n) &= \left.\begin{cases} \Theta(1) & \text{if } n \le 1,\\ T(n-1) + T(n-2) + \Theta(1) & \text{if } n > 1 \end{cases}\right\} \in \Theta(\phi^n) \end{align}$	$\begin{align} S(n) &= \left.\begin{cases} \Theta(1) & \text{if } n \le 1,\\ S(n-1) + \Theta(1) & \text{if } n > 1 \end{cases}\right\} \in \Theta(n) \end{align}$ where $\phi$ is the golden ratio.
DP $\rightarrow$ Top-down	$\Theta(n)$	$\Theta(n)$
DP $\rightarrow$ Bottom-up	$\Theta(n)$	$\Theta(n)$
DP $\rightarrow$ Bottom-up DP $\rightarrow$ Space-optimized	$\Theta(n)$	$\Theta(1)$

Towers of Hanoi

Suppose $k = 1$. Then, the 1-step solution is:

1. Move disk 1 from peg $A$ to peg $C$.

Suppose $k = 2$. Then, the 3-step solution is:

1. Move disk 1 from peg $A$ to peg $B$.
2. Move disk 2 from peg $A$ to peg $C$.
3. Move disk 1 from peg $B$ to peg $C$.

Suppose $k = 3$. Then, the 7-step solution is:

1. Move disk 1 from peg $A$ to peg $C$.
2. Move disk 2 from peg $A$ to peg $B$.
3. Move disk 1 from peg $C$ to peg $B$.
4. Move disk 3 from peg $A$ to peg $C$.
5. Move disk 1 from peg $B$ to peg $A$.
6. Move disk 2 from peg $B$ to peg $C$.
7. Move disk 1 from peg $A$ to peg $C$.

Suppose $k = 4$. Then, the 15-step solution is:

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

For any $k \ge 2$, the recursive solution is:

1. Transfer the top $k-1$ disks from peg $A$ to peg $B$.
2. Move the bottom disk from peg $A$ to peg $C$.
3. Transfer the top $k-1$ disks from peg $B$ to peg $C$.

\begin{algorithm}
\caption{Towers of Hanoi}
\begin{algorithmic}
\REQUIRE $k$ disks, source peg $A$, target peg $C$, auxiliary peg $B$
\ENSURE Move all $k$ disks from $A$ to $C$

\FUNCTION{TowersOfHanoi}{$k, A, C, B$}
  \IF{$k = 1$}
    \STATE Move disk $k$ from $A$ to $C$
  \ELSE
    \STATE \CALL{TowersOfHanoi}{$k-1, A, B, C$}
    \STATE Move disk $k$ from $A$ to $C$
    \STATE \CALL{TowersOfHanoi}{$k-1, B, C, A$}
  \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Let $M(n)$ denote the minimum number of moves required to move $n$ disks from one peg to another peg. Then $$M(n) = \left.\begin{cases} 1 & \text{if } n = 1,\\ 2M(n-1) + 1 & \text{if } n \ge 2 \end{cases}\right\} = 2^n - 1$$

Algorithm	Time $T(n)$	Space $S(n)$
Recursive	$= \left.\begin{cases} \Theta(1) & \text{if } n = 1,\\ 2T(n-1) + \Theta(1) & \text{if } n > 1 \end{cases}\right\} \in \Theta(2^n)$	$\Theta(n)$

Largest common divisor

The largest common divisor (LCD) of two integers $a$ and $b$ is the largest integer that divides both $a$ and $b$. LCD intuition.
Examples

• $\text{LCD}(2, 100) = 2$
• $\text{LCD}(3, 99) = 3$
• $\text{LCD}(3, 4) = 1$
• $\text{LCD}(12, 30) = 6$
• $\text{LCD}(1071, 462) = 21$

Slow algorithm

1. Find the divisors of the two numbers
2. Find the common divisors
3. Find the greatest of the common divisors

Fast algorithm

Recurrence relation: Suppose $a > b$. $$ \text{LCD}(a,b) = \left. \begin{cases} a & \text{if } b = 0,\\ \text{LCD}(b, a \bmod b) & \text{if } b > 0. \end{cases} \right\} $$ $$ \begin{align*} &\text{LCD}(1071,462)\\ &= \text{LCD}(462, 1071 \bmod 462) \\ &= \text{LCD}(462, 147) \qquad (\because 1071 = 2 \cdot 462 + 147) \\ &= \text{LCD}(147, 462 \bmod 147) \\ &= \text{LCD}(147, 21) \qquad (\because 462 = 3 \cdot 147 + 21) \\ &= \text{LCD}(21, 147 \bmod 21) \\ &= \text{LCD}(21, 0) \qquad (\because 147 = 7 \cdot 21 + 0) \\ &= 21 \end{align*}$$

\begin{algorithm}
\caption{Recursive Greatest common divisor Algorithm}
\begin{algorithmic}
\REQUIRE Nonnegative integers $a \ge b$
\ENSURE $\text{LCD}(a,b)$
\FUNCTION{LCD}{$a, b$}
  \IF{$b = 0$}
    \RETURN $a$
  \ELSE
    \RETURN \CALL{LCD}{$b, a$ \% $b$}
  \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Nonrecursive Greatest common divisor Algorithm}
\begin{algorithmic}
\REQUIRE Nonnegative integers $a, b$
\ENSURE $\text{LCD}(a,b)$
\FUNCTION{LCD}{$a, b$}
  \WHILE{$b \ne 0$}
    \STATE $temp \leftarrow b$
    \STATE $b \leftarrow a$ \% $b$
    \STATE $a \leftarrow temp$
  \ENDWHILE
  \RETURN $a$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Algorithm	Time $T(a, b)$	Space $S(a, b)$
Recursive	$ \begin{align} O(\log \min(a,b)) \end{align} $	$ \begin{align} O(\log \min(a,b)) \end{align} $
Nonrecursive	$ \begin{align} O(\log \min(a,b)) \end{align} $	$ \begin{align} \Theta(1) \end{align} $