Iterative vs. Recursive coding
thomas at jollybox.de
Sat Aug 21 01:59:46 CEST 2010
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
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.
More information about the Python-list