Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 38 ยท Lists and Recursion

Recursion Basics

Learn recursion in Racket and Scheme: base cases, recursive steps, factorial, Fibonacci, accumulators, tracing calls with the substitution model, and common mistakes.

Racket and Scheme have for loops (Racket) and named let loops, but the foundation is recursion: a function that calls itself on a smaller version of the problem. Because Lisp data (lists, trees) is itself recursively defined, recursion fits like a glove. In this lesson you learn the recipe, trace a few calls to see what happens, and meet accumulators.

Run examples use the stand-in interpreter. It handles recursion depth in the low thousands, which is enough for these examples; real Racket recurses far deeper because it grows the stack on demand.

The two-part recipe

Every recursive function has:

  1. A base case that answers the smallest version of the problem directly.
  2. A recursive step that solves a slightly smaller problem with the same function and combines the result.
RACKET
(define (factorial n)
  (if (= n 0)
      1                            ; base case: 0! is 1
      (* n (factorial (- n 1)))))  ; step: n! = n * (n-1)!

Make sure each recursive call gets closer to the base case; otherwise the function never stops.

Factorial

Tracing with the substitution model

Rewrite the call step by step to see what happens:

TEXT
(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

The expression grows as the recursion goes down, and the multiplications wait until the base case returns. Each pending * is stored on the call stack. Remember this shape: it is called linear recursive and uses memory proportional to n.

flowchart TB
    A["factorial 3"] --> B["3 * factorial 2"]
    B --> C["2 * factorial 1"]
    C --> D["1 * factorial 0"]
    D --> E["1"]

Calls go down until the base case; results multiply on the way back up.

Another example: counting down

RACKET
(define (count-down n)
  (when (>= n 0)
    (displayln n)
    (count-down (- n 1))))
(count-down 3)

This prints 3, 2, 1, 0. The base case is "do nothing when n is negative".

Two recursive calls: Fibonacci

A function may call itself more than once:

RACKET
(define (fib n)
  (cond [(= n 0) 0]
        [(= n 1) 1]
        [else (+ (fib (- n 1)) (fib (- n 2)))]))

This is a faithful translation of the definition, but slow: (fib 30) repeats the same sub-calls over a million times. The tree of calls roughly doubles with every step.

Fibonacci, the naive way

Accumulators: making it fast

The fix is to carry the running result along as an extra argument, called an accumulator. The function works in a loop-like way, and the recursive call is the last thing it does:

RACKET
(define (fib-fast n)
  (let loop ([i 0] [a 0] [b 1])
    (if (= i n)
        a
        (loop (+ i 1) b (+ a b)))))

a and b hold two consecutive Fibonacci numbers. Each step shifts them forward. There is no pending work after the call, so the whole thing runs in constant stack space and linear time.

The same trick fixes factorial:

RACKET
(define (fact-iter n)
  (let loop ([i n] [acc 1])
    (if (= i 0)
        acc
        (loop (- i 1) (* acc i)))))

A call in this final position is a tail call, and Racket and Scheme guarantee that tail calls do not grow the stack. You will study that guarantee fully in the chapter on continuations and tail calls.

Accumulator versions

The last example loops 100,000 times without overflowing: each loop call replaces the previous one instead of stacking on top of it.

Designing recursive functions

  1. Write down what the function should do and give some examples.
  2. Identify the smallest input (the base case) and its answer.
  3. Assume the function already works for a smaller input. How do you get from that answer to the answer for the current input?
  4. Check that every recursive call moves toward the base case.

Common mistakes

  • Missing base case: infinite recursion. Real Racket eventually runs out of memory; the stand-in reports a stack error.
  • Wrong direction: calling (factorial (+ n 1)) never reaches 0.
  • Forgetting to combine: (factorial (- n 1)) alone returns the smaller answer, not n!.
  • Recomputing: naive double recursion repeats work; use an accumulator or memoization.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What two parts does a recursive function need?

    The base case ends the recursion; the step reduces the problem so it reaches the base case.
  2. 2. Why is the naive (fib 30) slow?

    Each call spawns two more, so the same values are recomputed over and over.
  3. 3. In (loop (+ i 1) (+ acc i)), what is special about the position of the call?

    With nothing left to do after the call, Racket reuses the current frame, so the stack does not grow.
  4. 4. What does an accumulator hold?

    An accumulator carries the partial answer through the recursive calls.

Summary

  • A recursive function needs a base case and a step that moves toward it.
  • The substitution model shows pending operations piling up in linear recursion.
  • Double recursion such as naive Fibonacci can be exponentially slow.
  • An accumulator with a tail call gives loop-like speed and constant stack space.
  • Named let is the idiomatic way to write the loop.

Next: Recursion on Lists: Patterns