Using Recursion To Solve Problems

Divide and Conquer:

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

Everyday example:

P = carry a pile of 50 books from your office to your car.

The pile is too big, split it into 3 piles:

P1 (10 books), P2 (15 books), P3 (25 books)

Suppose you can directly solve P1 and P2 (i.e. they are small enough to carry) but P3 is too big to be carried. Divide P3 into two piles:

P3a (11 books), P3b (14 books)

Finally, put P3a on top of P3b, P2 on top of that, and P1 on top of the whole thing.