Recursion

In computer science, particularly, the idea of induction usually comes up in a form known as recursion. Recursion (sometimes known as ``divide and conquer'') is a method that breaks a large (hard) problem into parts that are smaller, and usually simpler to solve. If you can show that any problem can be subdivided into smaller ones, and that the smallest problems can be solved, you have a method to solve a problem of any size. Obviously, you can prove this using induction.

Here's a simple example. Suppose you are given the coordinates of the vertices of a simple polygon (a polygon whose vertices are distinct and whose sides don't cross each other), and you would like to subdivide the polygon into triangles. If you can write a program that breaks any large polygon (any polygon with 4 or more sides) into two smaller polygons, then you know you can triangulate the entire thing. Divide your original (big) polygon into two smaller ones, and then repeatedly apply the process to the smaller ones you get.

The concept of recursion is not unique to computer science--there are plenty of purely mathematical examples. Here's one of the most interesting that you may wish to play with:

Ackermann's function is defined as follows on all pairs of natural numbers:

\begin{eqnarray*} A(0, n) &=& n+1 \\ A(m, 0) &=& A(m-1, 1), \ \ \ \ \ \ \ \ \ \... ...> 0 \\ A(m, n) &=& A(m-1, A(m, n-1)),\ \ \mathrm{if\ } m, n > 0 \end{eqnarray*}



Just for fun, try to calculate $A(4,2)$. (Hint: First figure out what $A(0, n)$ looks like for all $n$. Then figure out what $A(1, n)$ looks like, for all $n$, et cetera.)