Recursion and Recurrences: Formulation of Recurrences

Recursion and Recurrences: Formulation of Recurrences

Recursion

In mathematics and computer science, recursion refers to the process where a function calls itself in its definition. It is a method used to solve problems by breaking them down into smaller, similar subproblems. Recursive problems typically have a "base case," which provides a simple, non-recursive solution for the smallest instances of the problem, and a recursive case, which solves the problem by reducing it to smaller subproblems.

A recursive function typically follows the structure:

1. Base Case(s): Defines the solution for the smallest or simplest input(s), usually without recursion.
2. Recursive Case: Defines the solution for a larger problem in terms of smaller instances of the same problem.

Example of Recursion: Factorial Function

The factorial function $n!$ is defined as the product of all positive integers less than or equal to $n$. Using recursion, the factorial can be defined as:

$$n! = \begin{cases} 1 & \text{if } n = 0 \\ n \times (n-1)! & \text{if } n > 0 \end{cases}$$

Here:

• Base Case: $0! = 1$ (since 0 factorial is defined as 1).
• Recursive Case: $n! = n \times (n-1)!$.

Recurrences

A recurrence relation (or simply recurrence) is an equation that defines a sequence of values in terms of previous terms in the sequence. Recurrences are commonly used in computer science to model the running time of recursive algorithms, particularly divide-and-conquer algorithms.

Formulation of Recurrences

Formulating a recurrence involves expressing the problem in a recursive way, based on the structure of the problem. When formulating recurrences, you identify:

1. The base case(s): The simplest problem(s) where the solution is known directly.
2. The recursive case(s): A way to break down the problem into smaller subproblems, along with a recurrence relation that defines how the solution for a larger problem can be obtained from smaller subproblems.

Example of Recurrence Formulation: Merge Sort

Let's consider the Merge Sort algorithm, a classic divide-and-conquer algorithm used to sort an array. The idea behind Merge Sort is to:

1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the sorted halves to produce the final sorted array.

To analyze the running time of Merge Sort, we can formulate a recurrence relation. Let $T(n)$ represent the time complexity of Merge Sort for an array of size $n$.

• Base case: If the array has only one element (or is empty), no sorting is needed, so the time complexity is constant. Thus, $T(1) = O(1)$.

• Recursive case: To sort an array of size $n$, Merge Sort divides the array into two subarrays of size $n/2$, recursively sorts each subarray, and then merges the two sorted subarrays. The merging step takes $O(n)$ time. Therefore, the recurrence relation for $T(n)$ is:

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

Here:

• $2T\left(\frac{n}{2}\right)$ accounts for the recursive sorting of the two subarrays.
• $O(n)$ accounts for the merging step.

This recurrence helps describe the time complexity of Merge Sort, which can be solved using methods such as the recursion-tree method or the Master Theorem.

Steps for Formulating Recurrences

When you are tasked with formulating a recurrence relation for a recursive algorithm or problem, follow these general steps:

1. Identify the base case(s): This is the simplest form of the problem that can be solved directly without recursion. It typically involves small input sizes or trivial computations.

2. Define the recursive case(s): Determine how the problem can be broken down into smaller subproblems. This usually involves dividing the input into smaller pieces and solving each piece recursively. If the input size is $n$, break it down into subproblems of smaller sizes, such as $n/2$, $n/3$, etc.

3. Express the time complexity or solution for the problem in terms of the time complexity or solution of the subproblems. Typically, this results in a recurrence relation that expresses the total work as a function of the work done on the subproblems and any additional work done outside of the recursion (e.g., merging, computing results).

Example 2: Fibonacci Numbers

The Fibonacci sequence is another classic example of a recursive problem. The Fibonacci numbers $F(n)$ are defined as:

$$F(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F(n-1) + F(n-2) & \text{if } n > 1 \end{cases}$$

This is a direct recursive definition, but if we were to express the time complexity of a naive recursive approach to calculate Fibonacci numbers, the recurrence relation would be:

$$T(n) = T(n-1) + T(n-2) + O(1)$$

Here:

• $T(n-1)$ and $T(n-2)$ represent the recursive calls to calculate $F(n-1)$ and $F(n-2)$, respectively.
• $O(1)$ represents the constant time required to add the two values $F(n-1)$ and $F(n-2)$.

Solving Recurrences

Once a recurrence relation is formulated, the next step is solving it to determine the time complexity or behavior of the algorithm. Common techniques to solve recurrences include:

1. Substitution Method: This method involves guessing the solution and using induction to prove it.
2. Recursion Tree: This method visualizes the recurrence as a tree, where each node represents a subproblem, and the branches represent recursive calls.
3. Master Theorem: This provides a straightforward way to solve recurrences of a specific form, commonly used for divide-and-conquer algorithms.

Master Theorem for Divide-and-Conquer Recurrences

The Master Theorem is a powerful tool for solving recurrences of the form:

$$T(n) = aT\left(\frac{n}{b}\right) + O(n^d)$$

Where $a \geq 1$, $b > 1$, and $d \geq 0$. The Master Theorem provides solutions based on the values of $a$, $b$, and $d$.

• Case 1: If $a > b^d$, then $T(n) = O(n^{\log_b a})$.
• Case 2: If $a = b^d$, then $T(n) = O(n^d \log n)$.
• Case 3: If $a < b^d$, then $T(n) = O(n^d)$.

Using this theorem, you can quickly determine the time complexity for many divide-and-conquer recurrences.

Conclusion

Formulating recurrences is essential for analyzing recursive algorithms and solving problems with a recursive structure. By expressing the problem in terms of smaller subproblems and combining the results of these subproblems, recurrences help characterize the behavior of algorithms and solutions. Understanding how to correctly formulate and solve recurrences is a critical skill in both mathematics and computer science.