13

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

Isaiah
  • 1,995
  • 2
  • 18
  • 29
  • 1
    Enjoying recursion is like enjoying hammers. Sometimes it's the best tool available, but when you want to put in a screw, reach for a screwdriver. – Xach Jun 08 '10 at 09:33
  • I like the idea of recursion. It fascinates me. However, I would never really use it in anything commercial. Sure, it makes code easier to write, but at the expense of efficiency and memory consumption. I prefer iterative versions, to be safe. – JosephTLyons Mar 02 '18 at 19:32

2 Answers2

11

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.

Sid Heroor
  • 663
  • 4
  • 11
  • 2
    +1 for specifically mentioning that not all recursion is tail call. – Davy8 Jun 08 '10 at 01:52
  • Could you write me an example of what to avoid that would negate tail call? – Isaiah Jun 08 '10 at 01:58
  • @Isaiah: A simple implementation of a factorial does: `(defun fact (n) (if (> n 0) (* n (fact (- n 1))) 1))` The reason is that the multiplication is done *after* the recursive call returns. – Greg Hewgill Jun 08 '10 at 02:44
  • I would replace "some CL implementations" with "most CL implementations". @Greg Hewgill: just to make it clear, the `*` invocation would be tail called (but that does not help the recursion). – Svante Jun 08 '10 at 08:05
11

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.

Community
  • 1
  • 1
mathk
  • 7,973
  • 6
  • 45
  • 74
  • 3
    In Common Lisp, it is not necessarily true that tail calls (i.e. calls in tail position) do not consume any stack space. That depends on the optimisation settings and the compiler. – Matthias Benkard Jun 10 '10 at 21:41
  • without doubt it took my factorial computation from 2700 to 3650 but after that it threw Stack over flow. This is a good piece of info to know.[Another helpful answer ](http://stackoverflow.com/questions/15269193/stack-overflow-from-recursive-function-call-in-lisp) – Pankaj Sejwal Mar 25 '14 at 11:37