Recursion is the idea of designing a function so that it calls itself.
Suppose we want to write factorial, where (factorial n) is the product of integers from 1 to n, inclusive. This non-recursive version updates product on each pass of a loop and then returns its value at the end:
1 2 3 4 5 6 7 8
We might notice that for n greater than 1, (factorial n) is always n multiplied by (factorial (- n 1)). Thus, we can rewrite factorial as a simpler recursive function:
Every recursive function, including factorial, has two essential ingredients:
The task to be done by the function is broken down into smaller versions of the same task. Here, each possible value of factorial can be described in terms of another value of factorial.
The function reaches a terminating condition. Here, once n reaches 1, the recursion stops, and the function simply returns 1. Without this condition, the function would recurse indefinitely.
Another common way of writing recursive functions is with a named let. The function below converts a natural number to a string, using a radix between 2 and 16. In this case, the inner let is named loop, which can be recursively invoked just like a function:
1 2 3 4 5 6 7 8 9 10 11 12 13
(define (n->s num [radix 10]) (define digits (list->vector (string->list "0123456789abcdef"))) (let loop ([num num][acc empty]) (if (zero? num) (if (empty? acc) "0" (list->string acc)) (let* ([r (modulo num radix)] [q (/ (- num r) radix)]) (loop q (cons (vector-ref digits r) acc)))))) (n->s 36 2) ; "100100" (n->s 36) ; "36" (n->s 36 16) ; "24"
The idea of recursion also surfaces with data structures that are defined partly in terms of themselves. For instance, in Racket a list is precisely defined as:
Just like a recursive function, this recursive data structure is described in terms of smaller versions of itself (a list is made of nested lists) until it reaches a terminating condition (the value null). + We can also think of this as starting with null and building upward, which is why recursive structures are also called inductively defined structures.
Furthermore, because so many data structures in functional languages are defined recursively—like lists—recursive functions end up being the most natural way to work with them. For instance, simplified versions of map and filter can be defined compactly as recursive functions that follow the recursive definition of a list:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
(define (my-map proc xs) (if (null? xs) null (cons (proc (car xs)) (my-map proc (cdr xs))))) (my-map abs (range -3 3)) ; '(3 2 1 0 1 2) (define (my-filter pred xs) (if (null? xs) null (if (pred (car xs)) (cons (car xs) (my-filter pred (cdr xs))) (my-filter pred (cdr xs))))) (my-filter even? (range 10)) ; '(0 2 4 6 8)
Here, we use car and cdr to break the task into smaller versions of the same task. Then we test the input for null? as our terminating condition.
Tail recursion refers to the special case where the return value of the recursive branch is nothing more than the value of the next recursive call (also known as a tail call).
For instance, our factorial function was recursive—because it called itself—but not tail recursive, because the last line of the recursive branch has to multiply n by the result of the next recursive call to factorial:
By contrast, the tail-factorial function below uses an to pass each intermediate product as an argument to the next recursive call. By using an accumulator, we can move the multiplication inside the recursive call, thereby making this version tail recursive:
1 2 3 4 5 6
Making the function tail recursive causes the integers to be multiplied in a different order, but of course this doesn’t change the result.
Tail recursion has special status in Racket because the compiler notices tail calls and optimizes them.
Ordinarily, each call to a function, including a recursive call, causes another set of arguments to be saved on the call stack. The call stack is an area of memory that stores the arguments for each function as it’s called. As one function calls another, more arguments pile up on the call stack. Later, as the return values are calculated, arguments are removed from the call stack and replaced with the return values.
For instance, let’s make a recursive sum function that’s like factorial, but adds the integers from 1 to n rather than multiplying them. sum pushes an argument onto the stack on each pass, so calculating (sum n) requires a maximum of n units of space on the stack (a process visualized below):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
But there’s a lurking problem. For sufficiently large n, we could use up all the memory available for the call stack (aka the dreaded stack overflow). In most programming languages, we’d be stuck.
But in Racket, we can rely on tail-call optimization. Recall that in a tail-recursive function, the return value doesn’t depend on the current arguments—just the result of the next call to the function. So when Racket sees a tail call, it simply discards the current arguments on the call stack, and replaces them with the arguments of the tail call. + The effect is to leave the call stack in a same state as if the current invocation of the function had never happened. Some people describe this as a type of goto. Really it’s more like time travel into the past. This means that if we instead use a tail-recursive function called tail-sum, it will never grow the stack:
1 2 3 4 5 6 7 8 9 10 11
In practical terms, what tail-call optimization means is that we can use a tail-recursive function to avoid using space on the stack, and thereby recurse to any depth.
For instance, in DrRacket let’s go to Racket → Limit Memory and change the limit to 8 MB. Then let’s try using our original sum function to add the positive integers up to 100,000,000:
When we try to run this, we’ll get an Interactions disabled message that signals DrRacket has run out of memory. Why? sum needs to store 100 million integers, but we only have about 8 million bytes of memory.
But if we use tail-sum, DrRacket can calculate an answer, because the tail call is optimized so it uses no extra space on the call stack:
(Don’t forget to go back to Racket → Limit Memory in DrRacket and set the memory limit back to a reasonable level.)