Stack overflow regarding two functions

Question

So I am new to lisp, and I am quite confused about the problem I have:

(defun factorial (x)
  (if (>= x 1)
      (* x (factorial (- x 1)))
      1))

The factorial function can output 3000! without a problem, however

(defun sum (x)
  (if (<= x 1)
      1
      (+ x (sum (- x 1)))))

Stack overflows at (sum 10000), I am using clisp.

Could anyone please clarify why this is happening?

Not sure, but it could be a syntax error - should there be a space between sum and (- x 1)? — jstaab
– jstaab, Commented Mar 19, 2014 at 18:36
Would be prettier, but it's not an error :/. I'm quite unsure why this is happening, could it be that lisp has a maximum amount of recursive calls it can do? — user3105379
– user3105379, Commented Mar 19, 2014 at 18:37
That's definitely true; if your interpreter doesn't optimize for tail recursion, you're going to have a really tall stack. What number are you passing the function? This is just a re-implementation of factorial, right? — jstaab
– jstaab, Commented Mar 19, 2014 at 18:41
Yeah, I was messing about with basic functions like that, I was passing (factorial 5000) and (sum 5000) which worked fine, however going to (sum 6000) it no longer works and it stack overflows, how would I fix that? — user3105379
– user3105379, Commented Mar 19, 2014 at 18:43
@jstaab Even if an implementation optimizes tail calls, these functions aren't written in a way where that would be applicable. Each stack frame needs to remain active until the recursive call returns so that the arithmetic operation can be performed. (A very smart compiler might figure out a way to optimize this, perhaps a la tail recursion modulo cons.) — Joshua Taylor
– Joshua Taylor, Commented Mar 19, 2014 at 21:05

sds · Accepted Answer · 2014-03-19 18:48:29Z

3

Your functions are not tail-recursive, so the compiler (and interpreter) increase stack for each iteration, eventually running out of it.

Your options are enumerated in FAQ How do I avoid stack overflow?; the relevant are:

answered Mar 19, 2014 at 18:48

sds

60.5k31 gold badges178 silver badges303 bronze badges

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

1 Answer 1