RC08. Lispful for Recursion

Daily dispatches from my 12 weeks at the Recurse Center in Summer 2023

Something that intrigues me about Lisp so far is the way in which it lends itself, almost automatically and as a first principle, to recursion. In my experience working through various introductory programming books, recursion is a topic usually saved for later – and for good reason, I think (or thought), since it is a vertigo-inducing headache-maker of a topic.

But for some reason with Lisp it feels front-and-center. Before loops, even. Maybe that’s because the very applicative-order evaluation at its core is recursive, which is to say that evaluating (read: understanding) a complex expression as a human requires drilling down first to the deepest elements and creating a mental stack along the way.

For instance, the equation

$\frac{\left(2+10\right)\left(3-21\right)}{\frac{3}{7}\left(3+11\right)}$

in Lisp would look like:

(/ (* (+ 2 10) (- 3 21)) (* (/ 3 7) (+ 3 7)))

so automatically we find we must recursively drill down this hierarchy of expressions to the innermost, atomic parts – things like (+ 3 11) or (/ 3 7) which are the bedrock of this particular expression – and move back outward.

It’s not that far a leap from here to a recursive procedure, such as this computation of a factorial:

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

Probably Lisp’s affinity with recursion has something to do with the fact that, as its name implies (LISt Processing), its very structure is defined by lists of lists of lists, which is recursive by nature. In a way that is not quite so palpable in other languages, I find while working with a Lisp dialect that I am viscerally aware of the lamination and the nesting, and that in turn quietly opens the door to recusive thinking.

Anyway, here’s an algo I wrote today that uses Newton’s method to approximate cube roots, which holds that, if y is an approximate cube root of x, an improved approximation can be obtained by the following:

$\frac{\frac{x}{y^2}+2y}{3}$

(define (cuberoot target)
  (cuberoot-itr 1.0 target))

(define (cuberoot-itr guess target) ; the recursive piece
  (if (good-enough? guess target)
    guess
    (cuberoot-itr (improve guess target) target)))

(define (good-enough? guess target)
  (< (abs (- (cube guess) target)) .01))

(define (cube x) (* x x x))

(define (improve guess target)
  (/ (+ (/ target (square guess)) (* 2 guess)) 3))

(define (square x) (* x x))

(define (abs x)
  (if (< x 0)
    (- x)
    x))