1

Im trying to understand how trampoline is used to support mutual recursion with tail recursion. However im lost when both the example below compiles with the same result. I believed that each defmethod had to return a function as in example 2 below. But this is clearly not the case since example 1 works just as fine. So are the two implementations below tail recursive and identical in there performance or what is the difference between them?

Example 1:

(defmulti jump :beff)
(defmethod jump 1 [{:keys [beff]}]                                         
      (print beff)                                                             
      (jump {:beff (inc beff)}))                                               
(defmethod jump 2 [{:keys [beff]}]                                         
      (print beff)                                                             
      (jump {:beff (inc beff)}))                                               
(defmethod jump :default [{:keys [beff]}]                                  
      (print beff))                                                            
(def v {:beff 1})     
(trampoline jump v) 

Example 2:

(defmulti jump :beff)
(defmethod jump 1 [{:keys [beff]}]                                         
      (print beff)                                                             
      #(jump {:beff (inc beff)}))                                               
(defmethod jump 2 [{:keys [beff]}]                                         
      (print beff)                                                             
      #(jump {:beff (inc beff)}))                                               
(defmethod jump :default [{:keys [beff]}]                                  
      #(print beff))                                                            
(def v {:beff 1})     
(trampoline jump v)
1
  • Try executing Example 1 with a value that will recurse several 1000 times before producing a result.
    – noahlz
    May 19, 2015 at 19:56

1 Answer 1

3

Example 1 is wrong and Example 2 is correct.

the first one only works because it's recuring only twice and doesn't blow the stack. The call to trampoline does nothing because the function never returns a function, so the trampoline function simply returns the value it returned.

it works in the same way this does:

user> (trampoline #(inc 41))
42

In this case trampoline makes the initial call to the function, then checks to see if the returned value is a function. Since the result is the number 42 it simply returns this. in Example 1 trampoline makes the first call, which recurs within it's self all the way through and returns a value that is not a function. Trampoline then returns this value without "bouncing" at all. Here's another example that does it wrong in the same way:

user> (trampoline (fn example
                    ([] (example 4))
                    ([x] (if (pos? x) (do (println x) (example (dec x)))))))
4
3
2
1
nil

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.