Edgardo Carreras | Blog

Tail Recursions

August 02, 2021

Tail Recursion

Today I learned about loop and recursion in Clojure.

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

This works fine with small numbers but, once you get big integers the stack fills up rather quickly.

(time (is-even? 1999999999))
Execution error (StackOverflowError) at koan-engine.runner/is-even? (form-init12162138873637638637.clj:2).

Yikes. That’s because he has to dec n times the value of n. And that gets added up in the stack until it evaluates every single possible value.

What if we can go backward?

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

This is what tail recursion looks like in Clojure. We start at the evaluated number and our tail is the beginning, we accumulate the value as to not blow the stack!

(time (is-even-bigint? 1999999999))
"Elapsed time: 89511.457975 msecs"

Want to hear more from me?

Signup to my newsletter!

CarrerasDev Newsletter

A free email newsletter on how to create high-performing development teams.

Written by Edgardo Carreras.

© 2024, Edgardo Carreras