Recursive Tree Method

3.7.3 Recursive Tree Method

Recursion

It is always possible to transform a recurrence problem into a recursive or iterative approach (within a loop) in computer programming. The simple definition of a recursive program (or function) is one that is defined in term of itself, where the recursive call represents the general case of the recurrence. However, a termination condition , which is the base case in terms of recurrence relation, must be specified; otherwise a recursive program can never stop calling itself, and thus becomes an infinite loop.

The use of recursion in an algorithm has both advantages and disadvantages. The main advantage is the simplicity. The main disadvantage is often that the algorithm may require huge amount of memory if the depth of the recursion is very large. Many practical computations can be achieved in a recursive manner, such as the linked list structure, tree structure, or the divide-and-conquer approach discussed below.

In recursive tree method, we converts the recurrence into a tree whose nodes represent the costs incurred at each level in the tree, and sum the costs at each level to determine the total cost of all levels of the recursions. Recursion trees are particularly useful when the algorithm is based on divide-and-conquerer algorithm.

Take Merge Sort (of equation 3.9.2), for example.

First, compute the middle of the array of size n, which takes Θ(1) time.
Second, recursively divide the subproblem into half, and solve the subproblem over half of the array, and thus, contribute 2 ⋅ T() to the running time.
Third, combine the sub-solutions on an n-element sub-array, which takes Θ(n) running time.

Let us see how to illustrate this recursive relation in tree model:

| cn = c⋅ n20 cn | | | cn = c⋅ n cn | 2 21 2 cn | lg(n+ 1) cn4-= c⋅ n22- cn4- cn4- cn4 cn | | | ... ... ... ... ... ... ... ... cn | - - - - - - - - | - - - - - - - - c = c⋅ 2lngn c c c c c c c cn

The total is cn ⋅ lg n + cn
T(n) = n ⋅ T(1) + cn ⋅ lg n = Θ(n ⋅ lg n)

Divide and Conquer

Many useful algorithms are recursive in structure, such as merge sort. To solve this kind of problem, we usually follow divide-and-conquer approach, a fundamental recursive scheme. That is, we first break the problem into several subproblems that are similar to the original problem but smaller in size. Next, we solve the subproblems recursively. Last, we combine these sub-solutions bottom-up to create the final solution to the original problem. In other words,

Method 3.7.3.1. Divide and Conquer

Divide the problem into a number of subproblems
Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, solve the the subproblems directly
Combine the sub-solutions into the final solution for the original problem.

Proof>