From ... From: Erik Naggum Subject: Re: Lisp is *SLOW* Date: 1997/07/16 Message-ID: <3078042529703162@naggum.no>#1/1 X-Deja-AN: 257201774 References: <5puscn$e0h$1@cdn-news.telecom.com.au> <33CA6A40.7A44@capital.net> <33CC7236.752C@cse.unl.edu> mail-copies-to: never Organization: Naggum Software; +47 8800 8879; http://www.naggum.no Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++ * W. Daniel Axline | Actually, I have been given to understand quite the opposite. Apparently | whenver (during runtime) a function calls itself, it has to make another | complete copy of itself to run. You can see how this would tend to take | up much more in the way of resources than an iterative function. I'm not | sure what the exact effect on speed would be, but I imagine it would be | slower. In my limited experience, iterative algorithms have not been that | much larger than their recursive counterparts, just more difficult to | divine. I wonder what you mean by "a complete copy of itself". it appears that you think a copy of the actual function's _code_ is copied, and this is of course not true. however, a new stack frame is often created upon a function call, with space for various registers, local variables, etc, etc. this does consume resources. languages that are made for or encourage recursive function calls often offer "tail call merging" to handle the case where a function returns simply what the function it is about to call would return. in such a case, the calling function's stack frame is undone before the call (if necessary), and the called function returns to the caller's caller, saving both time and memory. (Scheme is "properly tail recursive" because it requires an implementation to do tail calls as jumps, not calls. most Common Lisp implementations offer tail call merging.) I previously made a serious mistake in believing that Lisp compilers were so much faster than C compilers when the real difference was that the Lisp compilers did tail call merging and the C compiler did not. on a SPARC, this translates to a very heavy penalty because of the way register windows are saved on the stack, so the Lisp compilers won big, disproportionately. (I haven't been able to compute the actual cost of a call so I could discount it and get a better comparison. for now, the GNU C compiler makes recursion extremely costly on the SPARC.) programmers who write recursive functions learn to use tail recursion soon after they discover that each function call can take up hundreds of bytes of memory. e.g., the former of these two functions will use memory (stack space) proportional to n, while the latter will use constant space if the compiler merges tail calls. (defun factorial (n) (if (plusp n) (* n (factorial (1- n))) 1)) (defun factorial (n) (flet ((tail-factorial (n accumulator) (if (plusp n) (tail-factorial (1- n) (* n accumulator)) accumulator))) (tail-factorial n 1))) let's hope this puts some needless worries about recursion to rest. #\Erik -- Microsoft Pencil 4.0 -- the only virtual pencil whose tip breaks.