tail vs divide recursion

Let's use finding the largest in an array to illustrate two kinds of recursions: namely tail recursion and divide-n-conquer recursion. Another term for divide-n-conquer recursion is binary recursion. That's probably a better term, just like binary search.

Tail Recursion

In the following RecursionTest(), largest(A, 0, 6) will find the largest int from A[0] to A[6]. The largest() function implements a tail recursion function which compares the beginning array element arr[low] with the largest of the rest of array largest(arr, low+1, high). The recursive function is applied to the "tail" of the array. The tail starts with low+1, so we can "reduce" our function.

The console displays the actual sequences of each recursive calls. We go from 0 to 6, 1 to 6, 2 to 6, etc. until we reach the base case (6 to 6). The base case returns immediately. So, the return sequence goes from 6 to 6, 5 to 6, 4 to 6,..., 0 to 6 which returns to the main calling function RecursionTest().

Divide-n-Conquer Recursion

Another recursive method is like largest2(), also shown above. The largest2(A, 0, 6) performs the same function as previous implementation. However, the recursive method is different. The largest2() function compares the first half's largest array element largest2(arr, low, low+(high-low)/2)] with the largest of the second half array largest2(arr, low+(high-low)/2, high). For every largest2() function call, two recursive functions are produced to deal with two halves of the array.

Just see a careless bug in the above largest2 code :-( Can you see it?

Anyway, I fixed it and the run result is shown below. Try to plot out the calling sequence. It should looks like a tree for the divide-n-conquer recursion. If you like to explore more, how about the "return sequence"?

Discussions

1. What's the difference between "largest" and "largest2"? Can you plot the call/return sequence of both routines?

2. Largest2 has two recursive calls, did you notice that the second parameter is evaluated first?

3. Tail recursion is more like iteration. It virtually walks through the list.

4. How do you compare the complexity of iteration and tail recursion? Wow, that's one order of magnitude difference.

5. How about the complexity of divide-n-conquer recursion?

6. Divide-n-conquer uses a lot more recursive calls than tail recursion (almost twice as many, 13 versus 7 in our example).

7. Hmmm, more calls means slower. So, why would people use divide-n-conquer approach? Can you come up with one example that divide-n-conquer works better?