On Saturday 21 August 2010, it occurred to Baba to exclaim: > - every time the procedure calls itself the memory gradually fills up > with the copies until the whole thing winds down again > as the "return" statements start being executed. > - the above point means that a recursive approach is expensive on > resources so in the practical world it should be avoided. > (Thanks John for giving me a real life example where recursion is > recommended)
This is only partly true. In most programming languages "typical" today, this is true: each recursion is a normal function call which allocates space on the stack. Thus, the maximum recursion depth is severely limited. However, in most functional programming languages, recursion is recognized as a highly expressive, powerful, and idiomatic tool that can often be optimized. Languages like haskell or scheme compile tail-end recursive functions in a manner that is just as efficient as a loop would have been. In general, if you could rewrite a recursive scheme function to use a loop, then a decent scheme compiler will be able to "do it for you" behind the scenes. -- http://mail.python.org/mailman/listinfo/python-list
