Recursion: A Mirror Within a Mirror

Explore the power of recursion, solving problems by breaking them down into smaller, identical sub-problems. In Lispex, recursion is like a mirror endlessly reflecting itself—a key to elegantly and clearly unraveling complexity.

In functional languages like Lispex, iteration and looping are typically achieved through recursion. This guide will teach you what recursion is and how to write your own recursive functions to solve common problems.

What is Recursion?

Recursion is a simple but powerful idea: a function that calls itself.

To prevent a function from calling itself forever, a recursive function must have two key parts:

  1. Base Case: A condition that tells the function when to stop recursing.
  2. Recursive Step: The part where the function calls itself, but with a slightly different input that moves it closer to the base case.

Let's see this in action with a classic example.

Example 1: Calculating a Factorial

The factorial of a number n (written as n!) is the product of all positive integers up to n. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.

Here is a recursive function in Lispex to calculate a factorial:

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

(factorial 5)  ; ⇒ 120

How It Works

When we call (factorial 3), here's what the interpreter does:

  1. Is 3 <= 1? No. So, calculate (* 3 (factorial 2)).
  2. To do that, it must calculate (factorial 2). Is 2 <= 1? No. So, calculate (* 2 (factorial 1)).
  3. To do that, it must calculate (factorial 1). Is 1 <= 1? Yes. It hits the base case and returns 1.
  4. Now it can solve step 2: (* 2 1) which is 2.
  5. Now it can solve step 1: (* 3 2) which is 6.

The final result is 6.

Example 2: Recursion on a List

Recursion is the primary way to "loop" over a list in Lispex. The common pattern is to process the first element and then recurse on the rest of the list.

Let's write a function to sum all the numbers in a list.

(define (sum-list lst)
  (if (empty? lst)
      0
      (+ (list-first lst) (sum-list (list-rest lst)))))

(sum-list (list 10 20 30))  ; ⇒ 60

How It Works

  1. sum-list is called with (list 10 20 30).
  2. The list is not empty, so it calculates (+ 10 (sum-list (list 20 30))).
  3. sum-list is called with (list 20 30).
  4. The list is not empty, so it calculates (+ 20 (sum-list (list 30))).
  5. sum-list is called with (list 30).
  6. The list is not empty, so it calculates (+ 30 (sum-list (list))).
  7. sum-list is called with an empty list (). It hits the base case and returns 0.
  8. The results then "bubble up": (+ 30 0) is 30, (+ 20 30) is 50, and finally (+ 10 50) is 60.

A Note on Tail Recursion

For very deep recursion (e.g., (factorial 10000)), the simple recursive pattern can sometimes lead to an error called a "stack overflow." To solve this, you can use a technique called tail recursion.

A function is tail-recursive if the recursive call is the very last thing it does. This allows the Lispex interpreter to perform an optimization (Tail Call Optimization) to avoid stack overflow errors. This is often achieved using an "accumulator" variable.

Here's the tail-recursive version of our factorial function:

(define (factorial n)
  (let ((factorial-helper (lambda (n acc)
                             (if (<= n 1)
                                 acc
                                 (factorial-helper (- n 1) (* acc n))))))
    (factorial-helper n 1)))

(factorial 5)  ; ⇒ 120 (tail-recursive)

Conclusion

Recursion is a fundamental concept in Lispex. By understanding the base case and recursive step, you can perform any kind of iteration or looping in a clean, functional way.

Now, try writing your own recursive function! For example, can you write a function called my-length that calculates the length of a list recursively?