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 recursion 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
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.
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 not tail recursive implementation of factorial. Why? This is because in other to return from factorial there is a pending computation.
(* n ..)
So you are stacking n each time you call factorial. Now let 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 past as an argument to the function. So your also consume stack but the difference is that the stack size stay constant. Thus the compiler can optimize it by using only register and letting 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 other to know if a recursion is limited.
There might be some compiler technique to transform a non tail recursive function into a tail recursive one. May be someone could point out some link here.