Is there any limit to recursion in lisp?

I enjoy using recursion whenever I can, it seems like a much more natural way to loop over something then actual loops. I was wondering if there is any limit to recu开发者_StackOverflow中文版rsion in lisp? Like there is in python where it freaks out after like 1000 loops? Could you use it for say, a game loop?

Testing it out now, simple counting recursive function. Now at >7000000!

Thanks alot

---

First, you should understand what tail call is about.

Tail call are call that do not consumes stack. Now you need to recognize when your are consuming stack.

Let's take the factorial example:

(defun factorial (n)
    (if (= n 1)
        1
        (* n (factorial (- n 1)))))

Here is the non-tail recursive implementation of factorial. Why? This is because in addition to a return from factorial, there is a pending computation.

(* n ..)

So you are stacking n each time you call factorial. Now let's write the tail recursive factorial:

(defun factorial-opt (n &key (result 1))
    (if (= n 1)
        result
        (factorial-opt (- n 1) :result (* result n))))

Here, the result is passed as an argument to the function. So you're also consuming stack, but the difference is that the stack size stays constant. Thus, the compiler can optimize it by using only registers and leaving the stack empty.

The factorial-opt is then faster, but is less readable. factorial is limited to the size of the stack will factorial-opt is not. So you should learn to recognize tail recursive function in order to know if the recursion is limited.

There might be some compiler technique to transform a non-tail recursive function into a tail recursive one. Maybe someone could point out some link here.

---

Scheme mandates tail call optimization, and some CL implementations offer it as well. However, CL does not mandate it.

Note that for tail call optimization to work, you need to make sure that you don't have to return. E.g. a naive implementation of Fibonacci where there is a need to return and add to another recursive call, will not be tail call optimized and as a result you will run out of stack space.