Why does this overflow the stack instead of using tail recursion?

Question

I've defined the following functions in Clojure.

; return the input unchanged
(defn same [x] x)

; Recursively call the function on the input N times
(defn recurse-n-times [input function n]
  (if (= n 0)
    input
    (recurse-n-times (function input) function (- n 1))
  )
)

Here are some outputs from my recursion function:

(recurse-n-times 0 inc 5)     ; returns 5, as expected
(recurse-n-times 0 same 5)    ; returns 0, as expected
(recurse-n-times 0 same 5000) ; StackOverflowError:
                              ; clojure.lang.Numbers$LongOps.combine
                              ; (Numbers.java:394)

I don't understand why I get a StackOverflowError. The last thing that recurse-n-times does is call itself, so I expect it to use tail recursion and not grow the stack at all.

I would expect this alternate definition to give a StackOverflowError:

(defn bad-recurse-n-times [input function n]
  (if (= n 0)
    input
    (function (alt-recurse-n-times input function (- n 1)))
  )
)

Why does recurse-n-times not use tail recursion?

Hmmmm, if within recurse-n-times I call recur instead of recurse-n-times, it works. — Nathan Long
– Nathan Long, Commented Sep 7, 2013 at 22:01
Also, if I try that trick in bad-recurse-n-times I get java.lang.UnsupportedOperationException: Can only recur from tail position — Nathan Long
– Nathan Long, Commented Sep 7, 2013 at 22:02
Also worth noting, if you need non-recursive (or multi-function-chain recursive) tail call elimination, you can convert your code to use trampoline. — noisesmith
– noisesmith, Commented Sep 8, 2013 at 1:21

Chiron · Accepted Answer · 2013-09-07 22:02:49Z

14

This is a limitation of the JVM, not of Clojure. JVM doesn't support TCO.

Clojure offers a special form for this, recur

(defn recurse-n-times [input function n]
  (if (= n 0)
  input
  (recur (function input) function (- n 1))))

(recurse-n-times 0 same 500000) ;; will work

recur form should appear at the tail position otherwise the Clojure compiler will complain about it.

Note that recur is the only non-stack-consuming looping construct in Clojure. There is no tail-call optimization and the use of self-calls for looping of unknown bounds is discouraged. recur is functional and its use in tail-position is verified by the compiler.

answered Sep 7, 2013 at 22:02

Chiron

20.3k18 gold badges84 silver badges135 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Nathan Long Over a year ago

I guess that means that TCO when calling a different function isn't possible in Clojure: stackoverflow.com/questions/18593540/…

Thumbnail Over a year ago

@NathanLong Adapt your program to use trampoline. There is a nice example here. Note that trampoline only copes with mutual tail recursion.

muhuk · Accepted Answer · 2015-01-12 19:56:07Z

4

According to clojure.org

There is no tail-call optimization, use recur.

So you must use "recur" special form to do that.

edited Jan 12, 2015 at 19:56

muhuk

16.1k10 gold badges64 silver badges101 bronze badges

answered Sep 7, 2013 at 22:01

Magicianeer

2,1801 gold badge15 silver badges12 bronze badges

1 Comment

Chiron Over a year ago

recur isn't a keyword, it is a special form.

Collectives™ on Stack Overflow

Why does this overflow the stack instead of using tail recursion?

2 Answers 2

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related