Clojure Koans 14 Recursion Notebook

{:hello (clojure-version)}

(defn is-even? [n]

  (if (= n 0)

    true ;; note: this is the blank to fill in for "Recursion ends with a base case"

    (not (is-even? (dec n))))) ;; note: this is the blank to fill in for "And starts by moving toward that base case"

;; skill 14001: Create a recursive function which does *not* utilize explicit tail calls with recur

(defn is-even-bigint? [n]

  (loop [n   n

         acc true]

    (if (= n 0)

      acc ;; question 14001: Is the correct answer here `false` or `acc` ?

      (recur (dec n) (not acc)))))

;; hint1: Having too many stack frames requires explicit tail calls with recur

;; skill 14002: Create a recursive function which *does* utilize explicit tail calls with recur

;; question 14001: What is "tail-call optimization" explained simply?

(defn recursive-reverse [coll]

  (loop [n 0 acc '()]

    (if (= (count acc) (count coll))

      acc

      (recur (inc n) (conj acc (nth coll n))))))

;; note: This also passes the single test: `(reduce conj '() coll)`

;; question 14002: What are other correct, well-written answers?

;; exercise 14001: Write a recursive sequence reverse function that utilizes tail-call optimization

(defn factorial [n]

  ;; (cond

  ;;   (= n 1) 1 ;; step 1

  ;;   (= n 2) 2 ;; step 2

  ;;   (= n 3) (* 3 (factorial 2)) ;; step 3

  ;;   (> n 3) (* n (factorial (dec n)))) ;; step 4

  (loop [n n acc 1]

    (if (= n 1)

      acc

      (recur (dec n) (* acc n)))))

;; exercise 14002: Write a factorial function that utilizes tail-call optimization

;; "Recursion ends with a base case"

(= true (is-even? 0))

;; hint: Read this file from top to bottom, looking for references to `is-even?`

;; "And starts by moving toward that base case"

(= false (is-even? 1))

;; question 14003: How can "moving toward that base case" be made more clear & explicit in the "how" it "moves" (recursive call trace stack/tree)?

;; "Having too many stack frames requires explicit tail calls with recur"

(= false (is-even-bigint? 100003N))

;; question 14004: Why does this Koan have two accepted? (`false` and `acc`)

;; "Reversing directions is easy when you have not gone far"

(= '(1) (recursive-reverse [1]))

;; question 14005: What is the expected take-away (learning) here?

;; "Yet it becomes more difficult the more steps you take"

(= '(6 5 4 3 2) (recursive-reverse [2 3 4 5 6]))

;; question 14006: Is `(reduce conj '() coll)` recursive?

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