1. Foreword On Recursion

This lecture is mainly about recursion. You've probably all heard of recursion, and in all likelihood think of it as a rather obscure and highly inefficient programming technique. It is neither!

	 Recursion is your friend!

	 Recursion is powerful!

Powerful friends can get you what you want simply and efficiently, but they should be treated with care lest they turn on you and get you in a heap of trouble instead.

Recursion is more than just a programming technique. It has two other uses in computer science and software engineering, namely:

as a way of describing, defining, or specifying things.
as a way of designing solutions to problems (divide and conquer).

As a descriptive method, and as a problem-solving method, recursion is extremely widely used and it is often the method of choice, unparalleled in its power and clarity.

So even if, for whatever reason (legitimate or unfounded prejudice), you choose not to use recursion as a programming technique, you should always consider its use whenever you are describing or solving a problem.

We will look at these three uses of recursion one by one.

Recursive Definitions