CODEWITHSUNDEEP
lispclisp
user3105379
user3105379

Reputation:

Stack overflow regarding two functions

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?

Upvotes: 1

Views: 39

Answers (1)

sds
sds

Reputation: 60004

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:

  1. Compile the functions
  2. Increase Lisp stack size
  3. Rewrite using iteration instead of recursion
  4. Rewrite using tail-recursion and compile

Upvotes: 3

Related Questions