[Go to site: main page, start]
Thank you for your comment

Beau­tiful Racket / explainers

Recursion

Recur­sion is the idea of designing a func­tion so that it calls itself.

Suppose we want to write factorial, where (factorial n) is the product of inte­gers from 1 to n, inclu­sive. This non-recur­sive version updates product on each pass of a loop and then returns its value at the end:

(define (factorial n)
  (define product 1)
  (for ([i (in-naturals 1)]
        #:final (= i n))
       (set! product (* product i)))
  product)

(factorial 20) ; 2432902008176640000
1
2
3
4
5
6
7
8
(define (factorial n)
  (define product 1)
  (for ([i (in-naturals 1)]
        #:final (= i n))
       (set! product (* product i)))
  product)

(factorial 20) ; 2432902008176640000
copy to clipboard

We might notice that for n greater than 1, (factorial n) is always n multi­plied by (factorial (- n 1)). Thus, we can rewrite factorial as a simpler recur­sive func­tion:

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

(factorial 20) ; 2432902008176640000
1
2
3
4
5
6
(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

(factorial 20) ; 2432902008176640000
copy to clipboard

Every recur­sive func­tion, including factorial, has two essen­tial ingre­di­ents:

  1. The task to be done by the func­tion 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.

  2. The func­tion reaches a termi­nating condi­tion. Here, once n reaches 1, the recur­sion stops, and the func­tion simply returns 1. Without this condi­tion, the func­tion would recurse indef­i­nitely.

Another common way of writing recur­sive func­tions is with a named let. The func­tion 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 recur­sively invoked just like a func­tion:  + Under the hood, let is imple­mented as a macro that expands into lambda, so the kinship with func­tions is not acci­dental.

(define (n->s num [radix 10])
  (define digits
    (list->vector (string->list "0123456789abcdef")))
  (let loop ([num num][acc empty])
    (cond
      [(zero? num) (if (empty? acc) "0" (list->string acc))]
      [else
       (define-values (q r) (quotient/remainder num radix))
       (loop q (cons (vector-ref digits r) acc))])))

(n->s 36 2) ; "100100"
(n->s 36) ; "36"
(n->s 36 16) ; "24"
 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])
    (cond
      [(zero? num) (if (empty? acc) "0" (list->string acc))]
      [else
       (define-values (q r) (quotient/remainder num radix))
       (loop q (cons (vector-ref digits r) acc))])))

(n->s 36 2)  ; "100100"
(n->s 36)    ; "36"
(n->s 36 16) ; "24"
copy to clipboard

The idea of recur­sion also surfaces with data struc­tures that are defined partly in terms of them­selves. For instance, in Racket a list is precisely defined as:

Just like a recur­sive func­tion, this recur­sive data struc­ture is described in terms of smaller versions of itself (a list is made of nested lists) until it reaches a termi­nating condi­tion (the value null).  + We can also think of this as starting with null and building upward, which is why recur­sive struc­tures are also called induc­tively defined struc­tures.

Why is recur­sion impor­tant?

Recur­sion is a favored tech­nique in func­tional program­ming because it helps avoid muta­tion of values. The first version of our factorial func­tion mutated the vari­able product on each pass. The second did not.

Further­more, because so many data struc­tures in func­tional languages are defined recur­sively—like lists—recur­sive func­tions end up being the most natural way to work with them. For instance, simpli­fied versions of map and filter can be defined compactly as recur­sive func­tions that follow the recur­sive defi­n­i­tion of a list:

(define (my-map proc xs)
  (if (null? xs)
      null
      (cons (proc (first xs)) (my-map proc (rest xs)))))

(my-map abs (range -3 3)) ; '(3 2 1 0 1 2)

(define (my-filter pred xs)
  (if (null? xs)
      null
      (if (pred (first xs))
          (cons (first xs) (my-filter pred (rest xs)))
          (my-filter pred (rest xs)))))

(my-filter even? (range 10)) ; '(0 2 4 6 8)
 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 (first xs)) (my-map proc (rest xs)))))

(my-map abs (range -3 3)) ; '(3 2 1 0 1 2)

(define (my-filter pred xs)
  (if (null? xs)
      null
      (if (pred (first xs))
          (cons (first xs) (my-filter pred (rest xs)))
          (my-filter pred (rest xs)))))

(my-filter even? (range 10)) ; '(0 2 4 6 8)
copy to clipboard

Here, we use first and rest to break the task into smaller versions of the same task. Then we test the input for null? as our termi­nating condi­tion.

Tail recur­sion

Tail recur­sion refers to the special case where the return value of the recur­sive branch is nothing more than the value of the next recur­sive call (also known as a tail call).

For instance, our factorial func­tion was recur­sive—because it called itself—but not tail recur­sive, because the last line of the recur­sive branch had to multiply n by the result of the next recur­sive call to factorial:

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1))))) ; not tail recursive

(factorial 20) ; 2432902008176640000
1
2
3
4
5
6
(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1))))) ; not tail recursive

(factorial 20) ; 2432902008176640000
copy to clipboard

By contrast, the tail-factorial func­tion below uses an accu­mu­lator to pass each inter­me­diate product as an argu­ment to the next recur­sive call. By using an accu­mu­lator, we can move the multi­pli­ca­tion inside the recur­sive call, thereby making this version tail recur­sive:

(define (tail-factorial n [acc 1])
  (if (= n 1)
      acc
      (tail-factorial (- n 1) (* n acc)))) ; tail recursive

(tail-factorial 20) ; 2432902008176640000
1
2
3
4
5
6
(define (tail-factorial n [acc 1])
  (if (= n 1)
      acc
      (tail-factorial (- n 1) (* n acc)))) ; tail recursive

(tail-factorial 20) ; 2432902008176640000
copy to clipboard

Making the func­tion tail recur­sive causes the inte­gers to be multi­plied in a different order. Of course, this doesn’t change the result.

Tail-call opti­miza­tion

Tail recur­sion has special status in Racket because the compiler notices tail calls and opti­mizes them.

Ordi­narily, each call to a func­tion, including a recur­sive call, causes another set of argu­ments to be saved in a block of memory called the call stack. As one func­tion calls another, more argu­ments pile up on the call stack. Later, as the return values are calcu­lated, argu­ments are removed from the call stack and replaced with the return values.

For instance, let’s make a recur­sive sum func­tion that’s like factorial, but adds the inte­gers from 1 to n rather than multi­plying them. sum pushes an argu­ment onto the stack on each pass, so calcu­lating (sum n) requires a maximum of n units of space on the stack (a process visu­al­ized below):

(define (sum n)
  (if (zero? n)
      0
      (+ n (sum (- n 1))))) ; not tail recursive

(sum 5)
(+ 5 (sum 4))
(+ 5 (+ 4 (sum 3)))
(+ 5 (+ 4 (+ 3 (sum 2))))
(+ 5 (+ 4 (+ 3 (+ 2 (sum 1)))))
(+ 5 (+ 4 (+ 3 (+ 2 (+ 1 (sum 0))))))
(+ 5 (+ 4 (+ 3 (+ 2 (+ 1 0)))))
(+ 5 (+ 4 (+ 3 (+ 2 1))))
(+ 5 (+ 4 (+ 3 3)))
(+ 5 (+ 4 6))
(+ 5 10)
15
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
(define (sum n)
  (if (zero? n)
      0
      (+ n (sum (- n 1))))) ; not tail recursive

(sum 5)
(+ 5 (sum 4))
(+ 5 (+ 4 (sum 3)))
(+ 5 (+ 4 (+ 3 (sum 2))))
(+ 5 (+ 4 (+ 3 (+ 2 (sum 1)))))
(+ 5 (+ 4 (+ 3 (+ 2 (+ 1 (sum 0))))))
(+ 5 (+ 4 (+ 3 (+ 2 (+ 1 0)))))
(+ 5 (+ 4 (+ 3 (+ 2 1))))
(+ 5 (+ 4 (+ 3 3)))
(+ 5 (+ 4 6))
(+ 5 10)
15
copy to clipboard

But there’s a lurking problem. For large enough values of n, we could use up all the memory avail­able for the call stack (aka the dreaded stack over­flow). In most program­ming languages, we’d be stuck.  + Unlike most languages, Racket’s call stack isn’t restricted to a block of memory sepa­rate from the program memory. So stack over­flows are less likely, but still possible.

But in Racket, we can rely on tail-call opti­miza­tion. Recall that in a tail-recur­sive func­tion, the return value doesn’t depend on the current argu­ments—just the result of the next call to the func­tion. So when Racket sees a tail call, it simply discards the current argu­ments on the call stack, and replaces them with the argu­ments of the tail call.  + The effect is to leave the call stack in a same state as if the current invo­ca­tion of the func­tion had never happened. Some people describe this as a type of goto. Arguably, it’s more like time travel into the past. This means that if we instead use a tail-recur­sive func­tion called tail-sum, it will never grow the stack:

(define (tail-sum n [acc 0])
  (if (zero? n)
      acc
      (tail-sum (- n 1) (+ n acc)))) ; tail recursive

(tail-sum 5)
(tail-sum 4 5)
(tail-sum 3 9)
(tail-sum 2 12)
(tail-sum 1 14)
15
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
(define (tail-sum n [acc 0])
  (if (zero? n)
      acc
      (tail-sum (- n 1) (+ n acc)))) ; tail recursive

(tail-sum 5)
(tail-sum 4 5)
(tail-sum 3 9)
(tail-sum 2 12)
(tail-sum 1 14)
15
copy to clipboard

In prac­tical terms, what tail-call opti­miza­tion means is that we can use a tail-recur­sive func­tion 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 orig­inal sum func­tion to add the posi­tive inte­gers up to 123,456,789:

(define (sum n)
  (if (zero? n)
      n
      (+ n (sum (sub1 n)))))

(sum 123456789) ; error: not enough space on the stack
1
2
3
4
5
6
(define (sum n)
  (if (zero? n)
      n
      (+ n (sum (sub1 n)))))

(sum 123456789) ; error: not enough space on the stack
copy to clipboard

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 over 123 million inte­gers, but we only have about 8 million bytes of memory.

But if we use tail-sum, DrRacket can calcu­late an answer, because the tail call is opti­mized so it uses no extra space on the call stack:

(define (tail-sum n [acc 0])
  (if (zero? n)
      acc
      (tail-sum (sub1 n) (+ n acc))))

(tail-sum 123456789) ; 7620789436823655
1
2
3
4
5
6
(define (tail-sum n [acc 0])
  (if (zero? n)
      acc
      (tail-sum (sub1 n) (+ n acc))))

(tail-sum 123456789) ; 7620789436823655
copy to clipboard

(When you’re done, don’t forget to go back to Racket → Limit Memory in DrRacket and set the memory limit back to a reason­able level.)

Further

← prev next →