Suppose you want to count how many things are in a list.
In this list, every thing is a thing and a reference to the next thing. The last thing in the list references null as the next thing, so you know it's the last one when you see it.
Now, you write a function that does the following:
- take the list
- look at the first thing in the list
- if you find a null, return 0
- if not, you remove the first thing in the list and call the function again, using your shortened list as the argument
- and add 1 to whatever that function is going to return
Suppose your list is three things long.
length(1,2,3); will become length(length(2,3)) and then length(length(length(3))) and length(length(length(length(null)))).
The last call to length() returns zero and all the other ones add 1 to it. Your length is 3.
The alternative is to use a loop to iterate through the list elements and keep a count of them in a variable. Recursion might be useful here if your lists are going to be longer than what you can store in a single variable.