Uses of Recursion

Binary Search

A simple recursive routine used by many people is the binary search.
When asked to guess a number between one and a hundred, most people would start by guessing fifty.  If you are told that the number is higher, you would probably guess seventy five.  If you were told lower, you'd then guess a number roughly half way between fifty and seventy five.
Here, you are applying the principal of recursion, defining the number you are searching for by repeatedly applying the rule "Find the number half way between x and y"

Language

Linguists point out that  Recursion is used in sentence construction.  For example one might say
"The book is very interesting"
One could embed a sentence inside the first 
"The book (that I read last week) is very interesting"
and again
"The book (that I read (on the bus) last week) is very interesting"
The process could go on forever...

Do you know what I'm thinking?

Do you realise that I know what that you're thinking what I'm thinking?
Guessing what others are thinking is a basic human trait.  How far can we recursively map others thoughts?

Intelligence

It has been suggested that the ability to think recursively is a necessary component of intelligence
Recursion allows a limited number of "rules" to be applied recursively to create an infinite number of states.
For example, the game rock paper and scissors can be described by a finite number of states
(rock rock) draw
(rock scissors) player 1 wins
(rock paper) player 2 wins
(scissors rock) player 2 wins
...etc.
It would take an awful lot of space to write down all the states, or possible board layouts, of a game of chess.  Programming a computer to play chess by putting in all possible states in the manner of the rock paper scissors game would take a very long time.
Recursion means that a few rules (say the rules of chess) can be laid down that, applied over and over again, effectively work out all the states of the game as they are required.


Next: Recursion the Novel