Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 38 ยท Projects and Practice

Practice: Recursion Problems

Eight practice problems on recursion, accumulators, tail calls and higher-order functions, each with a Racket solution, hints, and runnable JavaScript checks to compare against.

Reading about recursion is not the same as writing it. This practice set has eight problems that use the ideas of the whole course: structural recursion on lists and trees, accumulators and tail calls, and higher-order functions. For each problem, try writing your own Racket solution on paper or in DrRacket first, then compare it with the one shown.

The Racket solutions are read-only here, since Racket does not run on this site. For problems where it helps, a JavaScript stand-in implements the same algorithm so you can run checks and see the expected results. A good way to use this lesson: cover the solution, write your own, and test it against the examples listed.

The problems

For every problem, write the Racket function and think about base cases first.

1. (count-if pred lst) returns how many elements satisfy pred. Example: (count-if even? '(1 2 3 4 6)) gives 3.

RACKET
(define (count-if pred lst)
  (let loop ([lst lst] [n 0])
    (cond [(null? lst) n]
          [(pred (car lst)) (loop (cdr lst) (+ n 1))]
          [else (loop (cdr lst) n)])))

2. (flatten-once lst) joins a list of lists one level deep: '((1 2) (3) () (4 5)) becomes '(1 2 3 4 5).

RACKET
(define (flatten-once lst)
  (if (null? lst)
      '()
      (append (car lst) (flatten-once (cdr lst)))))

3. (deep-flatten tree) flattens arbitrarily nested lists: '(1 (2 (3 4)) 5) becomes '(1 2 3 4 5).

RACKET
(define (deep-flatten t)
  (cond [(null? t) '()]
        [(pair? t) (append (deep-flatten (car t)) (deep-flatten (cdr t)))]
        [else (list t)]))

4. (fib n) in linear time with an accumulator pair (no exponential blow-up).

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

5. (range-list a b) returns (a a+1 ... b-1) using a tail-recursive loop that counts down and conses, so no reverse is needed.

RACKET
(define (range-list a b)
  (let loop ([i (- b 1)] [acc '()])
    (if (< i a) acc (loop (- i 1) (cons i acc)))))

6. (compose2 f g) returns a function applying g then f; then use it to build (compose-all f ...) with foldr.

RACKET
(define (compose2 f g) (lambda (x) (f (g x))))
(define (compose-all . fs) (foldr compose2 (lambda (x) x) fs))
((compose-all add1 (lambda (x) (* 2 x)) sqrt) 16) ; => 9

7. (permutations lst) returns every ordering of a list (a classic).

RACKET
(define (permutations lst)
  (if (null? lst)
      '(())
      (append-map (lambda (x)
                    (map (lambda (p) (cons x p))
                         (permutations (remove x lst))))
                  lst)))

8. (power-set lst) returns all subsets.

RACKET
(define (power-set lst)
  (if (null? lst)
      '(())
      (let ([rest (power-set (cdr lst))])
        (append rest (map (lambda (s) (cons (car lst) s)) rest)))))

Running the ideas

Here are JavaScript versions of problems 1 to 5, with checks that print true when the answer matches. Compare the structure with the Racket: the base cases and recursive steps are the same.

JS Stand-in: problems 1 to 5 with checks

Press Run (or Ctrl + Enter) to see the console output here.

No output.

And problems 6 to 8, which depend on first-class functions and recursion over choices:

JS Stand-in: problems 6 to 8 with checks

Press Run (or Ctrl + Enter) to see the console output here.

No output.

How to approach any recursion problem

  1. Name the cases. What is the smallest input (empty list, zero)? What does the answer look like there?
  2. Assume the recursive call works. Suppose (f (cdr lst)) already returns the right answer for the smaller input.
  3. Combine. How do you build the answer for lst from (car lst) and that result?
  4. Check tail position if inputs may be huge: if not, ask whether an accumulator helps (accumulators).
  5. Test the edges: empty input, one element, a duplicate, a negative number, a deeply nested structure.
flowchart TD
  A["Smallest input?"] --> B["Base case answer"]
  C["Assume (f smaller) works"] --> D["Combine with current item"]
  B --> E["Test edges"]
  D --> E

Base case plus combine step is the whole recipe.

Challenge extensions

  • Write deep-flatten with an accumulator so it is tail recursive.
  • Make permutations produce results lazily with a generator (generators lesson).
  • Count the number of recursive calls in naive fib for n = 20, then in the accumulator version.
  • Write a picture of the power set of {1, 2, 3} using the stand-in ideas from drawing with pict.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the number of subsets of a list with n elements?

    Each element is either in or out of a subset, giving 2^n subsets; power-set of 3 elements returns 8.
  2. 2. Why is the accumulator version of fib linear while the naive one is exponential?

    The naive version recomputes the same Fibonacci numbers many times; the loop computes each once.
  3. 3. How many permutations does a list of 4 distinct elements have?

    4! = 24.
  4. 4. What is the first step in solving a recursion problem?

    Knowing the smallest input and its answer anchors the recursion.

Summary

  • Recursion problems follow one recipe: base case, assume the smaller call works, combine.
  • Accumulators give linear, tail-recursive versions of naive definitions like fib.
  • append-map, foldr and function composition express many solutions compactly.
  • Always test the edges: empty, one element, nested, duplicates.

Next: Practice: Macros and Review