Iterative vs. Recursive coding

Thomas Jollans 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
> 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.




More information about the Python-list mailing list