How do recursive function calls work?

This question was asked at chia_network.public on Keybase.

A good resource for understanding recursion in Lisp is Recursion on Simple Lists.

Essentially, you define a function that checks for a termination condition and continues or exits accordingly. This allows you to do things like iterate or build lists, trees, or maps, or to calculate something that requires multiple similar steps.

Here is an example that calculates the factorial of a number. First, we check if the number we’re getting the factorial of is 2 or less, in which case the factorial is simply the number. This is our base case, the end of the recursive chain. If the number is greater than that, we need to multiply it by the previous factorial. A mathematical formula to represent this is f(n) = n * f(n - 1).

And here is how you iterate over a list, for example, to double every item. First, we make sure that the list passed in is actually a list. Our base case here is the list is nil, which happens at the end of a list. If it’s not the end of the list, we continue by returning a cons pair, of which the first element is the mapped item of the list, and the rest is a recursive call to the function with the rest of the items. In this case, we multiply the first element by two, and therefore this function maps every item in a list to double its value.

2 Likes