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)
    (not (is-even? (dec n)))))

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

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

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

  "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)))

Clojure Koans Walkthrough in Light Table IDE

This screencast tutorial helps you learn the Clojure programming language. Experience the joy of Clojure in the Light Table IDE as we tour through the Clojure Koans, taking you all the way from Beginner to Intermediate to Advanced.

Clojure is a Lisp created by Rich Hickey that runs on the JVM, as an alternative to Java. ClojureScript can target the web browser environment, and node.js, by compiling down to JavaScript, using the Google Closure compiler. Clojure features immutability, functional programming, and being a Lisp, macros.