Ch 5. Recurrence Relations
5.4 Recursive Algorithms and Algorithm Analysis
Recursive Algorithms
A recursive algorithm solves a problem by calling itself on smaller instances of the same problem. This approach is particularly effective when the problem exhibits a natural recursive structure, such as computing factorials (see Theorem 5.3), traversing trees (Section 9.2), or solving mathematical puzzles (see Examples 5.17 and 5.18). Recursive algorithms are defined using two key components: a base case, which terminates the recursion, and a recursive case, which reduces the problem toward the base case.
A recursive function is a function that is defined in terms of itself. Formally, a function [latex]f[/latex] is recursive if its definition includes a call to [latex]f[/latex] with a smaller or simpler input. Recursive functions must always include a base case to ensure that the recursion eventually terminates.
To illustrate, consider the factorial function, which is defined for all non-negative integers [latex]n[/latex] as
[latex]n! = \begin{cases} 1 & \text{ if } n = 0\\ n(n-1)! & \text{ if } n > 0 \end{cases}[/latex]
This definition naturally leads to a recursive algorithm. The input is a non-negative integer [latex]n[/latex], and the output is the product of all positive integers from [latex]1[/latex] to [latex]n[/latex]. The algorithm terminates when it reaches the base case [latex]n = 0[/latex], and a trace of the execution shows how recursive calls accumulate and then resolve.
Here is the pseudocode for the recursive factorial algorithm:
FUNCTION factorial(n)
IF n == 0 THEN
RETURN 1
ELSE
RETURN n * factorial(n - 1)
END FUNCTION
A trace of the algorithm for factorial(3) would show the following steps:
factorial(3) calls factorial(2)
factorial(2) calls factorial(1)
factorial(1) calls factorial(0)
factorial(0) returns 1
factorial(1) returns 1 x 1 = 1
factorial(2) returns 2 x 1 = 2
factorial(3) returns 3 x 2 = 6
To verify the correctness of this algorithm, we present the following theorem and its proof.
Theorem 5.3: Correctness of the Recursive Factorial Algorithm
For all integers [latex]n \geq 0[/latex], the recursive algorithm factorial(n) returns the value of [latex]n![/latex].
Proof
We use mathematical induction on [latex]n[/latex].
Basis Step: Let [latex]n = 0[/latex]. The algorithm returns 1, which matches the definition [latex]0! = 1[/latex]. So, the base case holds.
Inductive Step: Assume that for some [latex]k \geq 0[/latex], the algorithm correctly computes [latex]k![/latex]; that is, factorial(k) returns [latex]k![/latex]. We must show that factorial(k + 1) returns [latex](k + 1)![/latex].
By the algorithm:
factorial(k + 1) [latex]= (k + 1)[/latex] factorial(k)
By the inductive hypothesis, factorial(k) returns [latex]k![/latex], so
factorial(k + 1) [latex]= (k + 1)k! = (k + 1)![/latex]
Thus, the algorithm correctly computes [latex](k + 1)![/latex]. By the principle of mathematical induction, the algorithm returns [latex]n![/latex] for all [latex]n \geq 0.[/latex]
[latex]\square[/latex]
Once we know that an algorithm's output is correct, we can analyze its time complexity by defining a recurrence relation (see Section 5.2). For the factorial function we have been using as an illustration, let [latex]t_{n}[/latex] represent the time it takes to compute [latex]n![/latex] using the pseudocode in factorial(n). Notice that each recursive call performs a constant amount of work (a single multiplication) and makes one recursive call. Then we have the recurrence relation.
[latex]t_{n} = t_{n-1} + c[/latex]
where [latex]c[/latex] is a constant representing the time taken for multiplication and the recursive call setup. Solving this recurrence by iteration (see Section 5.2) gives
[latex]t_{n} = t_{n-1} + c = t_{n-2} + 2c = \dots = t_{0} + nc[/latex]
Assuming [latex]t_{0}[/latex] is constant, the total time is linear in [latex]n[/latex].
Recursive algorithms are powerful but must be carefully designed to ensure termination and avoid excessive resource consumption. In practice, they are often compared with iterative algorithms, which use loops instead of recursion. While recursion can lead to elegant, concise code, iteration may be more memory-efficient, especially in languages or environments with limited stack space.
Algorithm Analysis
As we saw in the analysis above of the time complexity of the factorial function, algorithm analysis is the process of determining how many computational resources an algorithm requires as a function of its input size. Computational resources can be measured in time or space, but for simplicity in this textbook, we consider only time. This analysis helps us compare algorithms, predict performance, and decide which algorithm is most appropriate for a given situation.
One of the most important aspects of algorithm analysis is understanding how the algorithm behaves under different conditions. If the algorithm receives the most favourable input, it completes in the best-case time. On the other hand, if the algorithm receives the least favourable input, it completes in the worst-case time. If the input distribution is known, the average-case time is the expected time the algorithm takes over all possible inputs of a given size.
Example 5.24
Consider the linear search algorithm from Example 5.23, which finds the position of a target value in a list of size [latex]n[/latex]. In the best case, the target is the first element, in which case the algorithm completes in one comparison. In the worst case, the target is the last element or absent, requiring [latex]n[/latex] comparisons. In the average case, we assume the target is equally likely to be at any position, which can be shown to require [latex]\frac{n+1}{2}[/latex] comparisons.
When describing the growth of an algorithm’s running time, we focus on the algorithm’s dominant behaviour, not on constant factors and lower-order terms. This is achieved using asymptotic notation, which characterizes the growth of the function as the input size increases.
Definition 5.1(a): Big Omega Notation (Lower Bound)
A function [latex]f(n)[/latex] is in [latex]\Omega (g(n))[/latex] if there exist a constant [latex]c > 0[/latex] such that, for sufficiently large [latex]n[/latex],
[latex]f(n) \geq c g(n)[/latex]
This means that [latex]g(n)[/latex] serves as an asymptotic lower bound on [latex]f(n)[/latex], describing the algorithm’s best-case growth rate.
Definition 5.1(b): Big O Notation (Upper Bound)
A function [latex]f(n)[/latex] is in [latex]O(g(n))[/latex] if there exist a constant [latex]c > 0[/latex] such that, for sufficiently large [latex]n[/latex],
[latex]f(n) \leq c g(n)[/latex]
This means that [latex]g(n)[/latex] serves as an asymptotic upper bound on [latex]f(n)[/latex], describing the algorithm’s worst-case growth rate.
Definition 5.1(c): Big Theta Notation (Tight Bound)
A function [latex]f(n)[/latex] is in [latex]\Theta (g(n))[/latex] if there exist constants [latex]c_{1}, c_{2} > 0[/latex] such that, for sufficiently large [latex]n[/latex],
[latex]c_{1} g(n) \leq f(n) \leq c_{2} g(n)[/latex]
This means that [latex]g(n)[/latex] serves as an asymptotic tight bound on [latex]f(n)[/latex], capturing both the upper and lower bounds and describing the algorithm’s exact growth rate.
Using asymptotic notation for the linear search algorithm in Example 5.24, the time complexity is best case [latex]\Omega (n)[/latex], worst case [latex]O(n)[/latex], and tight bound [latex]\Theta (n)[/latex].
The next example analyzes the time complexity of insertion sort, a sorting algorithm that builds the final sorted list one element at a time. It works as follows:
- Start with the second element in the list (the first element is considered sorted).
- Compare it with the elements before it.
- Shift all larger elements one position to the right.
- Insert the current element into its correct position.
- Repeat for all elements in the list.
Example 5.25
Consider the insertion sort algorithm applied to a list of size [latex]n[/latex].
In the best case, the list is already sorted. Only one comparison per element is needed, so the time complexity is [latex]\Omega (n)[/latex].
In the worst case, the list is sorted in reverse order. Each new element must be compared with all previous elements, resulting in [latex]O(n^{2})[/latex] time.
In the average case, each element is compared with half of the sorted portion, leading again to [latex]\Theta (n^{2})[/latex] time.
Thus, the time complexity of insertion sort is best case [latex]\Omega (n)[/latex], worst case [latex]O(n^{2})[/latex], and tight bound [latex]\Theta (n^{2})[/latex].
The next three examples are of three important recursive algorithms: the Fibonacci sequence, binary search, and merge sort. Each example includes a description, pseudocode, and a proof of its time complexity.
Example 5.26
The Fibonacci sequence (see Example 5.13) is defined as
[latex]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}[/latex]
The pseudocode is as follows:
FUNCTION fibonacci(n)
IF n == 0 THEN
RETURN 0
ELSE IF n == 1 THEN
RETURN 1
ELSE
RETURN fibonacci(n - 1) + fibonacci(n - 2)
END FUNCTION
Theorem 5.4: Worst-Case Time Complexity of Recursive Fibonacci Algorithm
The worst-case time complexity of the Fibonacci recursive algorithm is [latex]O(2^{n})[/latex].
Proof
When computing fibonacci(n), each call to the function triggers two additional calls (fibonacci(n - 1) and fibonacci(n - 1)), unless a base case (n == 0 or n == 1) is reached. These two additional calls may trigger another two additional calls each. This process continues until level [latex]n[/latex] is reached, and the number of calls is bounded above by [latex]2^{n}[/latex]. Therefore, the algorithm performs at most [latex]2^{n}[/latex] calls, which confirms the worst-case time complexity of [latex]O(2^{n})[/latex].
[latex]\square[/latex]
Example 5.27
There are many types of search algorithms, such as the linear search algorithm in Example 5.23 and the binary search algorithm in this example. A binary search finds a specific target in a sorted list by repeatedly dividing the search interval in half. The pseudocode is as follows:
FUNCTION binary_search(list, target, low, high)
IF low > high THEN
RETURN -1
SET mid TO (low + high) / 2
IF list[mid] == target THEN
RETURN mid
ELSE IF list[mid] > target THEN
RETURN binary_search(list, target, low, mid - 1)
ELSE
RETURN binary_search(list, target, mid + 1, high)
END FUNCTION
To find the index of the target value 42 in the sorted list
list = [5, 12, 19, 26, 31, 42, 57, 63, 78]
the following trace is executed:
low = 0, high = 8 → mid = 4 → list[4] = 31 → 42 > 31
low = 5, high = 8 → mid = 6 → list[6] = 57 → 42 < 57
low = 5, high = 5 → mid = 5 → list[5] = 42
The output is the index 5.
Theorem 5.5: Worst-Case Time Complexity of Binary Search
The worst-case time complexity of binary search on a sorted list of size [latex]n[/latex] is [latex]O(\text{log } n)[/latex].
Proof
Let [latex]t_{n}[/latex] be the maximum number of comparisons required to search a list of size [latex]n[/latex]. Then
[latex]t_{n} = t_{\frac{n}{2}} + 1[/latex]
This recurrence reflects the fact that each recursive call reduces the problem size by half and performs one comparison. Solving this recurrence by iteration, we obtain
[latex]t_{n} = t_{n/2} + 1 = t_{n/4} + 2 = \cdots = t_{1} + \text{log}_{2}n[/latex]
Since [latex]t_{1} = 1[/latex], we have
[latex]t_{n} = O(\text{log }n)[/latex]
Thus, the worst-case time complexity of binary search is [latex]O(\text{log } n).[/latex]
[latex]\square[/latex]
Example 5.28
Like search algorithms, there are many types of sort algorithms, such as the insertion sort algorithm in Example 5.25 and the merge sort algorithm in this example. The merge sort algorithm uses a divide-and-conquer approach, by recursively splitting a list into halves, sorting each half, and then merging them back together. The pseudocode is as follows:
FUNCTION merge_sort(list)
IF LENGTH(list) <= 1 THEN
RETURN list
SET mid TO LENGTH(list) / 2
SET left TO merge_sort(list[0:mid])
SET right TO merge_sort(list[mid:])
RETURN merge(left, right)
FUNCTION merge(left, right)
SET result TO empty list
WHILE left AND right ARE NOT EMPTY
IF left[0] <= right[0] THEN
APPEND left[0] TO result
REMOVE left[0]
ELSE
APPEND right[0] TO result
REMOVE right[0]
APPEND remaining elements of left and right TO result
RETURN result
To sort the list
list = [52, 14, 6, 88, 21, 3, 47]
the following trace is executed:
Split [52, 14, 6, 88, 21, 3, 47]
→ [52, 14, 6] and [88, 21, 3, 47]
Split [52, 14, 6] → [52] and [14, 6] → [14] and [6]
Merge [6] and [14] → [6, 14], then merge with [52] → [6, 14, 52]
Split [88, 21, 3, 47] → [88, 21] and [3, 47]
→ [88], [21], [3], [47]
Merge [88] and [21] → [21, 88], merge [3] and [47] → [3, 47]
Merge [21, 88] and [3, 47] → [3, 21, 47, 88]
Merge [6, 14, 52] and [3, 21, 47, 88]
→ [3, 6, 14, 21, 47, 52, 88]
The output is the list [3, 6, 14, 21, 47, 52, 88].
Theorem 5.6: Worst-Case Time Complexity of Merge Sort
The worst-case time complexity of merge sort on a list of size [latex]n[/latex] is [latex]O(n \text{log }n)[/latex].
Proof
Let [latex]t_{n}[/latex] denote the time required to sort a list of size [latex]n[/latex]. The recurrence relation for merge sort is
[latex]t_{n} = 2t_{\frac{n}{2}} + cn[/latex]
where [latex]cn[/latex] represents the time to merge two sorted lists of size [latex]\frac{n}{2}[/latex]. We solve this recurrence by expanding it iteratively as follows:
[latex]t_{n} = 2t_{\frac{n}{2}} + cn = 2 [ 2t_{\frac{n}{4}} + c \frac{n}{2}] + cn = 4 t_{\frac{n}{4}} + cn + cn[/latex]
[latex]= 4t_{\frac{n}{4}} + 2cn = 8t_{\frac{n}{8}} + 3cn = \cdots = 2^{k}t_{\frac{n}{2^{k}}} + kcn[/latex]
We continue expanding until [latex]\frac{n}{2^{k}} = 1[/latex], which implies [latex]k = \text{log}_{2}n[/latex]. Substituting this into the recurrence gives
[latex]t_{n} = t_{1} + cn \text{log}_{2} n[/latex]
Since [latex]t_{1}[/latex] is a constant, we have
[latex]t_{n} = O(n \text{ log } n)[/latex]
Therefore, the worst-case time complexity of merge sort is [latex]t_{n} = O(n \text{ log } n).[/latex]
[latex]\square[/latex]
Real-World Example 5.4: File System Backup Utility
Suppose you are using a file system backup utility to back up all your files in a directory, including files in subdirectories. The software uses a recursive algorithm to traverse the file system by starting from a root directory, processing each file, and when encountering a subdirectory, recursively calling itself to process each file in the subdirectory. The pseudocode for this process is as follows:
FUNCTION backup_directory(path)
FOR EACH item IN path
IF item IS a file THEN
COPY item TO backup_location
ELSE IF item IS a directory THEN
CALL backup_directory(item)
END FUNCTION
The input is a directory path, and the output is a complete copy of all files and subdirectories. Termination occurs since the recursion ends when all subdirectories have been visited, and all files have been copied. A trace shows the order in which directories are entered and files are copied.
Let’s analyse this algorithm by letting [latex]n[/latex] be the total number of files and directories. Each file is visited once, and each directory is entered once, so the time complexity is [latex]O(n)[/latex]. However, if the algorithm performs additional operations, such as compressing files, the complexity may increase accordingly.
