We recommend black text on a light gray background,
but you can try other color schemes.
| This Site : | Bottom-of-Page | Home | Part 1 | Part 2 | Other Topics |
I think that the simplest possible example of a recursive function
can be constructed by using a toy programming language
( similar to LISP ) that performs operations on lists of objects.
Assume that two built-in functions
car and
cdr exist for
operating on lists and are defined as follows:
| Given a list L, | |||||||||||||
|
| Example 1 | |||
| L = ( a b c ) | → | car [ L ] = a and cdr [ L ] = ( b c ) | |
| Example 2 | |||
| L = ( ( a b ) c ) | → | car [ L ] = ( a b ) and cdr [ L ] = ( c ) | |
| Example 3 | |||
| L = ( ( a b ) c ) | → | car [ cdr[L] ] = c and cdr [ car[L] ] = ( b ) | |
Now, for our recursion example, let's define a function f to count the number of top-level elements in any given list. ( Perhaps a better name for f would be "length" or "len", but I use f for brevity. )
In example 1 above, the list L has 3 top-level
elements -- a, b, and c.
In example 2, L has just two top-level
elements --
the list ( a b ) and the object c.
Define the function f recursively as follows
| L = ( ) | → | f [ L ] = 0 | |
| L not empty | → | f [ L ] = 1 + f [ cdr [ L ] ] |
This says that the length of an empty list is zero, and
the length of a non-empty list
is simply one more than the length of the list obtained after
removing its first element.
Now if we choose a particular list and trace thru a
step-by-step execution
of f on that list,
we will get a good idea of how recursion works.
Fig 1 below shows the trace for f executing
on a list that has four top-level elements.
The vertical line below each call to f shows
the value returned by that call.
| This Site : | Top-of-Page | Home | Part 1 | Part 2 | Other Topics |