EECS 281: Data Structures and Algorithms

Section 04 Recursion

University of Michigan at Ann Arbor

Last Edit Date: 05/12/2023

Disclaimer and Term of Use:

We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file

This personal note is adapted from Professor Marcus Darden and David Paoletti. Please contact us to delete this file if you think your rights have been violated.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Introduction to Recursion¶

A recursive function calls itself to accomplish its task
At least one base case is required
At least one recursive case if required
Each subsequent call has simpler (smaller) input
Single recursion can be used on lists
Multiple recursion can be used on trees

Tail Recursion¶

When a function is called, it gets a stack frame, which stores the local variables
A simple recursive function generates a stack frame for each recursive call
A function is tail recursive if there is no pending computation at each recursive step
- "Reuse" the stack frame rather than create a new one
Tail recursion and iteration are equivalent

The Program Stack

When a function call is made
- All local variables are saved in a special storage called the program stack
- Then argument values are pushed onto the program stack
When a function call is received
- Function arguments are popped off the stack
When return is issued within a function
- The return value is pushed onto the program stack
When return is received at the call site
- The return value is popped off the program stack
- Saved local variables are restored
Program stack supports nested function calls
- Six nested calls = six sets of local variables
There is only one program stack (per thread)
- NOT the program heap, (where dynamic memory is allocated)
Program stack size is limited
- The number of nested funciton calls is limited

Note: A buggy recursion function will exhaust program stack very quickly.

Recursion vs. Tail Recursion

Recursion

 1     int factorial(int n) {
 2         if (n == 0) {
 3             return 1;
 4         }
 5         return n * factorial(n - 1);
 6     }

For the recursive factorial() function above, we have $\Theta(n)$ time complexity and $\Theta(n)$ space complexity because it uses n stack frames.

Try it out:

Open in new window

Tail Recursion

 1     int factorial(int n, int resultSoFar = 1) {
 2         if (n == 0) {
 3             return resultSoFar;
 4         }
 5         return factorial(n - 1, resultSoFar * n);
 6     }

For the tail recursive function factorial() above, we have $\Theta(n)$ time complexity and $\Theta(1)$ space complexity because it reuses 1 stack frame.

Try it out:

Open in new window

Recurrence Relations

A recurrence relation describes the way a probelm depends on a subproblem.

A recurrence can be written for a computation:

$$ x^n = \begin{equation} \begin{cases} 1&n = 0\\ x\times x^{n-1}&n > 0\\ \end{cases} \end{equation} $$

A recurrence can be written for the time taken:

$$ T(n) = \begin{equation} \begin{cases} c_0&n = 0\\ T(n - 1)+c_1&n > 0\\ \end{cases} \end{equation} $$

A recurrence can be written for the amount of memory used (non-tail recursive):

$$ M(n) = \begin{equation} \begin{cases} c_0&n = 0\\ M(n - 1)+c_1&n > 0\\ \end{cases} \end{equation} $$

Common Recurrences

Recurrence	Example	Big-O Solution
$$T(n) = T \left( \frac{n}{2} \right) + c$$	Binary Search	$$O(\text{log} n)$$
$$T(n) = T(n - 1) + c$$	Linear Search	$$O(n)$$
$$T(n) = 2T \left( \frac{n}{2} \right) + c$$	Tree Traversal	$$O(n)$$
$$T(n) = T(n - 1) + c_1\cdot n + c_2$$	Selection / etc. Sorts	$$O(n^2)$$
$$T(n) = 2T\left(\frac{n}{2}\right) + c_1\cdot n + c_2$$	Merge / Quick Sorts	$$O(n \text{log} n)$$

Solving Recurrences Using Master Theorem¶

1. Master Theorem

Let $T(n)$ be a monotonically increasing function that satisfies:

$$T(n) = aT \left(\frac{n}{b} \right) + f(n)$$$$T(1) = c_0~\text{or}~T(0) = c_0$$

where $a \ge 1$, $b > 1$. If $f(n) \in \Theta(n^c)$, then

$$ T(n) \in \begin{equation} \begin{cases} \Theta(n^{\log_ba})&\text{if}~a > b^c\\ \Theta(n^c \log n)&\text{if}~a = b^c\\ \Theta(n^c)&\text{if}~a < b^c\\ \end{cases} \end{equation} $$

Example 1:

$$T(n) = 3T \left(\frac{n}{2} \right) + \frac{3}{4} n + 1$$

The parameters are:

$a = 3$
$b = 2$
$c = 1$

Since $a > b^c = 3 > 2^1$, it is in the form of $T(n) = aT \left(\frac{n}{b} \right) + f(n)$, and $f(n) \in \Theta(n^c)$, so we can get:

$$T(n) = \Theta(n^{\log_23})$$

Example 2:

$$T(n) = 2T \left(\frac{n}{4} \right) + \sqrt{n} + 7$$

The parameters are:

$a = 2$
$b = 4$
$c = \frac{1}{2}$

Since $a = b^c = 2 = \sqrt{4}$, it is in the form of $T(n) = aT \left(\frac{n}{b} \right) + f(n)$, and $f(n) \in \Theta(n^c)$, so we can get:

$$T(n) = \Theta(\sqrt{n}\log n)$$

Example 3:

$$T(n) = T \left(\frac{n}{2} \right) + \frac{1}{2} n^2 + n$$

The parameters are:

$a = 1$
$b = 2$
$c = 2$

Since $a < b^c = 2 < 2^2$, it is in the form of $T(n) = aT \left(\frac{n}{b} \right) + f(n)$, and $f(n) \in \Theta(n^c)$, so we can get:

$$T(n) = \Theta(n^2)$$

Note: We cannot use the master theorm when:

The recursion does not involve division: $T(n) = T(n - 1) + n$
Master Theorem not applicable: $T(n) \ne aT(\frac{n}{b}) + f(n)$

Fourth Condition

There is a 4th condition that allows polylogarithmic functions:

If $f(n) \in \Theta(n^{\log_ba}\log^kn)$ for some $k \ge 0$, then $T(n) = \Theta(n^{\log_ba}\log^{k + 1}n)$

This condition is fairly limited

Example (fourth condition):

Given the following recurrence:

$$T(n) = 2T\left(\frac{n}{2} \right) + n \log n$$

Clearly $a = 2$, $b = 2$, but $f(n)$ is not polynomial
However $f(n) \in \Theta(n \log n)$ and $k = 1$

So we can have:

$$T(n) = \Theta(n \log^2 n).$$