A computer program is said to be recursive if it calls itself while running. Without an example, this is difficult to understand… and it is even harder to see why all programming languages now use recursion, whereas early languages such as Cobol, for business data processing, and Fortran, for scientific computing, did without it. One reason is the reliability of recursive programs: they are virtually the only programs that can be proved to do exactly what they are supposed to do…
Induction and card games
======================================================================================================
Take a deck of cards, shuffle it, and then try to sort it. How should you proceed? At first glance, the task seems complex. Induction makes it considerably simpler if we reframe the question: suppose you know how to sort n cards; how can you sort n + 1? More prosaically, you know how to sort a deck of four cards. You are given one more; what do you do?
Naturally, you sort the first four cards and then insert the fifth in its proper place. To do so, simply compare it in turn with the cards already sorted, starting with the first. Here, the new card is inserted after the second. This method rests squarely on the idea of induction! To see why, let us formalize it in the style of a proof by induction. Here, then, is a method that takes a deck of cards T and returns the same deck sorted:
