Recursive Functions

By introducing conditionals we’ve actually made our language a lot more powerful. This is because they effectively let us implement recursive functions.

Recursive functions are those which call themselves. We’ve used these already in C to perform reading in and evaluation of expressions. The reason we require conditionals for these is because they let us test for the situation where we wish to terminate the recursion.

For example we can use conditionals to implement a function len which tells us the number of items in a list. If we encounter the empty list we just return 0. Otherwise we return the length of the tail of the input list, plus 1. Think about why this works. It repeatedly uses the len function until it reaches the empty list. At this point it returns 0 and adds all the other partial results together.

(fun {len l} {
  if (== l {})
    {0}
    {+ 1 (len (tail l))}
})

Just as in C, there is a pleasant symmetry to this sort of recursive function. First we do something for the empty list (the base case). Then if we get something bigger, we take off a chunk such as the head of the list, and do something to it, before combining it with the rest of the thing to which the function has been already applied.

Here is another function for reversing a list. As before it checks for the empty list, but this time it returns the empty list back. This makes sense. The reverse of the empty list is just the empty list. But if it gets something bigger than the empty list, it reverses the tail, and sticks this in front of the head.

(fun {reverse l} {
  if (== l {})
    {{}}
    {join (reverse (tail l)) (head l)}
})

We’re going to use this technique to build many functions. This is because it is going to be the primary way to achieve looping in our language.