Recursion is the art of solving a problem by just doing a little bit of work, taking a piece off the entire task, reducing the problem to a slightly simpler or smaller one, which can be solved by taking a piece off in turn… and so on and so forth, till one is left with a trivial problem that can be solved immediately. The challenge, of course, is to figure out how to reduce a problem to a simpler one.
Here we give an introduction to recursion, looking at some simple and some classical recursive algorithms.