The trampoline function is Clojure's way to explicitly optimize mutual recursion.

Mutual recursion

A quick Wikipedia check you will get the idea, but lets just get an simple overview right here.

Put it simply , if two function call each other they are mutual recursive. Simple enough. One of the most important use case of mutual recursion is programming language's grammar. Most syntax structures in a grammar are naturally mutual recursion. For example, an IF statement can contains an FOR statement which again can contains an IF statement.

From this point of view the mundane recursive is just a special case of mutual recursive which a function mutual recursive with itself. For example when an IF statement contains an IF statement.

For a mundane recursion we can simply copy the function definition and change the function name and let them call each other, and it becomes a mutual recursion. I will use the example in last post Understand Clojure recur and tail recursion optimization to demonstrate.

 
(declare recurseme2)
(defn recurseme1 [n]
   (if (= n 0)   
     ()
     (do 
       (println (str n "th loop in recurseme1"))
       (recurseme2 (- n 1))
     )
   )
)
 
;; copy and change its name
(defn recurseme2 [n]
   (if (= n 0)   
     ()
     (do 
       (println (str n "th loop in recurseme2"))
       (recurseme1 (- n 1))
     )
   )
)
(recurseme1 20)
 

How to optimize it with trampoline function

Now you can not use recur to optimize it , and trampoline comes to rescue. This is not a special form, just a function, its a nifty tool with some cleverness in it .

Lets first see how to use trampoline

 
(declare recurseme2)
(defn recurseme1 [n]
   (if (= n 0)   
     ()
     (do 
       (println (str n "th loop in recurseme1"))
       #(recurseme2 (- n 1))
     )
   )
)
 
;; copy and change its name
(defn recurseme2 [n]
   (if (= n 0)   
     ()
     (do 
       (println (str n "th loop in recurseme2"))
       #(recurseme1 (- n 1))
     )
   )
)
(trampoline recurseme1 20)
 

You just put a # in front of where the mutual call happens which makes it return an anonymous function. And using trampoline to call the function. What trampoline do is use recur on those anonymous functions, it actually transform mutual recursion into a mundane recursion by using an anonymous function.

The code of trampoline makes it more obvious.

 
user=> (source trampoline)
(defn trampoline
  "trampoline can be used to convert algorithms requiring mutual
  recursion without stack consumption. Calls f with supplied args, if
  any. If f returns a fn, calls that fn with no arguments, and
  continues to repeat, until the return value is not a fn, then
  returns that non-fn value. Note that if you want to return a fn as a
  final value, you must wrap it in some data structure and unpack it
  after trampoline returns."
  {:added "1.0"
   :static true}
  ([f]
     (let [ret (f)]
       (if (fn? ret)
         (recur ret)
         ret)))
  ([f & args]
     (trampoline #(apply f args))))
 

In the loop, the anonymous function passed down as parameter and its executed at the start of each loop, inside that anonymous function can be either call to any one of the two mutual recursive function.

For a mundane tail recursion, we can also use a trampoline becuase its just a special case of mutual recursion.

 
(defn recurseme [n]
   (if (= n 0)   
     ()
     (do 
       (println (str n "th loop"))
       #(recurseme (- n 1))
     )
   )
)
 
(trampoline recurseme 100)