Clojure Koans Walkthrough

1. Introduction
2. Lists
3. Vectors
4. Sets
5. Maps
6. Functions
7. Conditionals
8. Higher Order Functions
9. Runtime Polymorphism
10. Lazy Sequences
11. Sequence Comprehensions
12. Creating Functions
13. Recursion
14. Destructuring
15. Refs
16. Atoms
17. Macros
18. Datatypes
19. Java Interop
20. Partition

Recommended Books

• ← Creating Functions
• Destructuring →

13. Recursion - Koans Walkthrough

This video introduces recursion, which is a key concept in functional programming. Although the JVM does not support tail-call optimization, Clojure has a trick up it's sleeve to accomplish the same thing via the special "recur" operator. In this way you can do recursive looping without consuming any stack space.

Here is the 13_recursion.clj source code:

(defn is-even? [n]
  (if (= n 0)
    true 
    (not (is-even? (dec n)))))

(defn is-even-bigint? [n]
  (loop [n   n
         acc true]
    (if (= n 0)
      acc 
      (recur (dec n) (not acc)))))

(defn recursive-reverse [coll]
  (loop [coll coll
          reversed '()]
         (if (empty? coll)
           reversed
           (recur (rest coll) (cons (first coll) reversed)))))

(defn factorial [n]
  (loop [n n
         res 1]
    (if (= 0 n)
      res
      (recur (dec n) (* n res)))))

(meditations
  "Recursion ends with a base case"
  (= true (is-even? 0))

  "And starts by moving toward that base case"
  (= false (is-even? 1))

  "Having too many stack frames requires explicit tail calls with recur"
  (= false (is-even-bigint? 100003N))

  "Reversing directions is easy when you have not gone far"
  (= '(1) (recursive-reverse [1]))

  "Yet more difficult the more steps you take"
  (= '(5 4 3 2 1) (recursive-reverse [1 2 3 4 5]))

  "Simple things may appear simple."
  (= 1 (factorial 1))

  "They may require other simple steps."
  (= 2 (factorial 2))

  "Sometimes a slightly bigger step is necessary"
  (= 6 (factorial 3))

  "And eventually you must think harder"
  (= 24 (factorial 4))

  "You can even deal with very large numbers"
  (< 1000000000000000000000000N (factorial 1000N))

  "But what happens when the machine limits you?"
  (< 1000000000000000000000000N (factorial 100003N)))