Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister

Re: Behold! The power of recursion.

by TedPride (Priest)
on Oct 18, 2004 at 05:41 UTC ( #400069=note: print w/replies, xml ) Need Help??

in reply to Behold! The power of recursion.

The only time that recursion is actually useful is when you're branching out. If each instance of your function only calls the function once, you should be using a loop to eliminate the function overhead. Even branching functions can often be done better with stacks, since with a stack you can allocate all memory needed in advance, while a recursive function has to allocate and deallocate every time it runs through an instance of itself.

++ to everyone who posted similar messages.

Replies are listed 'Best First'.
Re^2: Behold! The power of recursion.
by stvn (Monsignor) on Oct 18, 2004 at 12:16 UTC
    The only time that recursion is actually useful is when you're branching out.

    I think you maybe have the "usefulness" of recursion confused with the "misuse of an un-optimized implementation of recursion in a language compiler".

    Just because most C compilers inefficiently implement recursion and many other C based languages do not fix this problem does not mean it is a lost cause. If you look at the compiler technology underlying recent implementations of Standard ML, Haskell or Scheme you will see that recursion can be implemented efficiently.

      Would you please give URL references here. I would like to follow your thoughts, but am not familiar with the literature. This is a particularly interesting thread for me, having been severely reprimanded for using recursion (some years ago) and having made an effort to repress the impulse to use it ever since. -ben

        As with any tool, its all about how you use it.

        The common misconception is that recursion is inefficient because each iteration entails calling a subroutine. In a lot of langauges, this means allocating a stack frame and freezing the previous stack frame until the next one exits. This can quickly eat up recourses, and depending upon the complexity of the recursion, leave a number of half finished computations. The result is that your function takes up exponetntial memory/stack/resource space. A common technique to avoid this in Scheme and other languages (even including C with the right compiler) is called Tail Call Optimization.

        Standard ML is a functional language, which means that calling functions is important, so therefore, the Standard ML compiler is built to optimize function calls. As for recursion, it uses a heap based allocation rather than stack based, which allows for a number of optimizations to take place. I would provide a link on this, but to be honest, I read it while waist deep in the Standard ML site and I have never been able to dig it out again.

        Scheme too makes many optimizations which allow it to be very efficient, even in the face of recusion which would bring most other languages to a halt (since they would have consumed all available resources). Googling "Scheme", "Optimized", etc will get you a number of links to lots of good info.

        But my point is that it is unwise, as compiler technology improves, to rule out a recursive solution which is more understandable and maintainable because 5-10 years ago compiler technology couldn't handle it.

        There is always a trade off between programmer time (writing, documenting and maintaining) and computer time (execution). Back in the days of yore, computer time was more expensive than programmer time. The inverse is true now.

        Once again, it is all in how you use it. Bad recursion is not worse than bad iteration, its all bad programming in the end. If the problem/algorithm itself is recursive then the most understandable and maintainable version of it will be the recursive one.


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://400069]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (6)
As of 2018-01-21 00:27 GMT
Find Nodes?
    Voting Booth?
    How did you see in the new year?

    Results (227 votes). Check out past polls.