A Primer on Recursion

by Amit

The study of Recursion abounds in such statements as:

“Hofstadter’s Law: It always takes longer than you expect, even when you take into account Hofstadter’s Law. ” —Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid.

They are amusing and thought provoking at the same time. The idea of recursion is simple when you think of expressing something complex in terms of simpler versions of itself. You will then see recursion in action in the simple things we do everyday, the music we create, the language we speak and the things that happen at sub-atomic levels. In the chapter titled “Recursive Structures and Processes”, of Gödel, Escher, Bach ( http://en.wikipedia.org/wiki/Gödel,_Escher,_Bach ), Douglas Hofstadter ( http://en.wikipedia.org/wiki/Douglas_Hofstadter )takes you into a World of Music, Art, Physics and Programming where recursion abound. The underlying concept is to decompose a big problem into indivisible sub-problems, solve them and then combine each of these partial solutions to get the holistic solution. This combination operator is not a universal operator and is specific to the problem at hand. As a crude example, consider the factorial function, fact(N). It is elementary to observe that  fact(N)   = N * fact(N-1) = N * (N-1) * fact(N-2)…

As is apparent, we are combining smaller fact()’s by the multiplication operator to obtain fact(N). Here our combination operator is multiplication operator- ‘*’. In the rest of this paper, I shall touch upon recursion in Formal Languages, Linguistics, Mathematics and Computer Science. Except for the last one, in which I have had my education, I am just a guy who takes keen interest in these fields.

The rest of the essay is available in PDF here or html here

Suggestions/Comments welcome.

Advertisement