Recursion is a common form of the general-purpose problem-solving technique called ``divide and conquer''. The principle of divide-and-conquer, is that you solve a given problem P in 3 steps:

- divide P into several subproblems, P1,P2,...Pn.
- solve, however you can, each of the subproblems to get solutions S1...Sn.
- Use S1...Sn to construct a solution to the original problem, P.

P = carry a pile of 50 books from your office to your car.Well, you can't even lift such a big pile, never mind carry it. So you split the original pile into 3 piles:

P1 contains 10 books, P2 contains 15 books, P3 contains 25 books.Your plan, of course, is to carry each pile to the car separately, and then put them back together into one big pile once they are all there. This is a recursive divide-and-conquer strategy; you have divided the original problem P into 3 problems

Now suppose you can directly solve P1 and P2 - they are small enough that you can carry them to the car. So, P1 and P2 are now sitting out there by the car. Once you get P3 there, you will pile them up again.

But P3 is too big to be carried. You apply the same strategy recursively: divide P3 into smaller problems, solve them, and combine the results to make the solution for P3. You divide P3 into two piles, P3a has 11 books, P3b has 14, and carry these separately to the car. Then you put P3a back onto P3b to form the pile P3 there at the car.

Now you have solved all the subproblems: P1, P2, P3 are sitting at the car. You stack them into one big pile, and presto, you have solved the original problem.

This may seem like a rather hokey example, but it illustrates very well the principles of divide-and-conquer. Let us see how we can use the very same ideas to solve mathematical and computer science problems.

Find an algorithm for raising a number X to the power N, where N is a
positive integer. You may use *only* two operations:
multiplication, subtraction. We would like to multiply N copies of X
all at once, but, like the piles of books, we do not have an operation
that directly allows us to do that: we can only multiply two numbers
at a time. In other words, the problems we can solve directly are
these:

- raise X to the power 1: answer = X.
- raise X to the power 2: answer = X * X.

So, if N > 2, we split the original problem into two subproblems:

- P1: raise X to the power I. The answer to this is S1.
- P2: raise X to the power N-I. The answer to this is S2.
- To get the final answer, S, combine S1 and S2: S = S1 * S2.

To see the strategy in action consider raising 3 to the power 7. 7 is too big, we can't directly solve this problem, so we divide it into:

- P1: raise 3 to the power 2. (choose I=2, no particular reason)
- P2: raise 3 to the power 5.

We can directly solve P1, the answer is S1 = 9. But P2 we have to further decompose:

- P2.1: raise 3 to the power 1. (choose I=1, no particular reason)
- P2.2: raise 3 to the power 4.
Again, P2.1 can be directly solved, S2.1 = 3, but P2.2 must be further decomposed:

- P2.2.1: raise 3 to the power 2.
- P2.2.2: raise 3 to the power 2.

*combined*to give S2.2 = 9*9 = 81.Now that we have the solutions to P2.1 and P2.2 we combine them to get the solution to P2, S2 = 3*81 = 243.

I said that the strategy would work no matter how we chose to
subdivide the problem: any choice of `I' will give the correct answer.
However, some choices of `I' compute the final answer *faster*
than others. Which do you think is faster: choosing I=1 (every time)
or I=2?

**Answer:** *The computation will be faster if you choose I=2
because there will be half the number of recursive calls, and
therefore half the overhead.*

This is true of most recursive strategies: they usually work correctly for many different ways of decomposing the problem, but some ways are much more efficient than others. In our first example, we also were free to divide the pile of books into as many piles and whatever sizes we liked. but it obviously would be very inefficient to carry one book at a time.

Many problems involving data structures are naturally solved
recursively. This is because most data structures are *collections*
of components and they can easily be divided into *sub*collections
that can be independently processed, just as, in our first example, we
divided the pile of books into smaller piles that could be carried to
the car separately.

For example, suppose we want to add up the numbers stored in array X between positions FIRST and LAST. We can solve this directly in two very simple cases:

- FIRST=LAST:
- there is one number to be added, the answer is X[FIRST].
- FIRST+1=LAST:
- there are 2 numbers to be added, the answer is X[FIRST] + X[LAST].

- P1: add up the numbers in X between positions FIRST and M; the answer is S1.
- P2: add up the numbers in X between positions M+1 and LAST; the answer is S2.

The exact way we divide up the array does not affect the correctness of this strategy: M can be any value at all, FIRST<M<LAST.

The `structure' of the collection dictates which are the easiest
ways to divide up the collection. As we've just seen arrays are very
flexible, it is easy to divide them into a *front* and a *back*
at any division point we care to choose. Other data structures are
easily divided only in certain ways.

For example, suppose we want to add up all the numbers in a stack. We'll base our solution on the recursive definition of stack we saw earlier: a stack is Empty, or has 2 parts, Top and Remainder.

We can directly add up all the numbers in an Empty stack! There are
none, and by convention, the sum of *no* numbers is 0.

To add up the numbers in a non-empty stack, we will divide the stack into two parts, add up the parts separately, and combine the results. This is exactly what we did for arrays, but now we have to think, what is an easy way to divide a stack into two parts?

The definition of stack gives us an immediate answer: a stack naturally decomposes into a Top element (which is a number, not a stack), and a Remainder, which is a stack. So we can decompose the problem of adding up the numbers in a nonempty stack into these two subproblems:

- P1: add up all the numbers in the Top part. This is not a
recursive call, because Top is not a stack. In fact, Top is just
a number, so the solution to this subproblem is just the top
value itself. S1=Top value.
- P2: add up all the numbers in Remainder. This is a recursive call, because Remainder is a stack. The solution is S2.

Of course, there is nothing special about `adding'. The very same strategy would work if we wanted to multiply together all the values in a collection, to find the largest value, to print out the elements, to count the number of elements, and so on. To illustrate how powerful this strategy is, let us finish with an example we will study in more detail later in the course.

Suppose we wished to *sort* the values in array X between
positions FIRST and LAST. We can solve this directly in two very
simple cases:

- FIRST=LAST:
- there is one number to be sorted, nothing needs to be done.
- FIRST+1=LAST:
- there are 2 numbers to be sorted; compare them and, if they are out of order, swap them.

- P1: sort the numbers in X between positions FIRST and M; the answer is S1.
- P2: sort the numbers in X between positions M+1 and LAST; the answer is S2.

As before, the exact way we divide up the array does not affect the correctness of this strategy: M can be any value at all, FIRST<M<LAST. Certain values of M correspond to well-known sorting algorithms:

- M = 1
- gives rise to the sorting algorithm called insertion sort.
- M = the midpoint between FIRST and LAST
- gives rise to the MergeSort algorithm.