Re: Any use for recursion?

Tomás Ó hÉilidhe <toe@xxxxxxxxxxx> writes:
While I don't think many people would deny that recursive
functions are fun and intriguing to write, I think they come with far
too much overhead. With each recursive call, there's stuff being
pushed onto the stack, the program counter being changed, stuff being
popped back off the stack, the program counter being changed again.
Also, if the recursion is deep, e.g. 16 levels deep, then it results
in a ridiculously big stack. A microcontroller would have no problem
whatsoever dealing with a loop but the stack's going to overflow if
the recursion goes 16 levels deep!

So basically I'm asking if there's any place _at all_ for
recursive functions? Is there any example of an algorithm that can be
implemented as a recursive function which _cannot_ be implemented
better as a loop?

Basically I'm asking: Are recursive functions for fun and nothing
more?

Strictly speaking, recursion is a superset of iteration. Anything that
can be done with a plain loop can be done with a recursive function.
Anything that can be done with a recursive function can be done with a
plain loop + a stack.

Some which require a stack for bookkeeping (e.g. depth-first search and
LL(k) parsing) can use the natural stack that the language keeps via the
call sequence rather than having to manage a stack themselves. This can
result in greater code clarity. You need a stack anyway, so you might
as well use the one the language environment gives you for free.

Also, with languages or compilers performing tail-call optimization to
eliminate the excess overhead of recursive calls which do not need stack
tracking, I frequently find recursion to be a more natural way of
expressing many iterations (although some may consider me twisted in
that regard).

- Michael

--
mouse, n: A device for pointing at the xterm in which you want to type.
.

Relevant Pages

  • Re: Any use for recursion?
    ... In modern languages there is no overhead. ... popped back off the stack, the program counter being changed again. ... Recursion is ubiquitous in modern software. ...
    (comp.programming)
  • Re: Memory management strategy
    ... >>trading memory for speed ... The use of registers instead of the stack doesn't need inlining. ... >longer instructions to access smaller data than they were optimized for. ... square) but it didn't need recursion or some kind of stack. ...
    (comp.lang.c)
  • Re: grassfire algorithm in java
    ... > How many recursions did it take to overflow the stack? ... > say, recursion counting does. ... For debugging it MAY be a useful technique - but you are talking about using ...
    (comp.lang.java.programmer)
  • Re: Is this tai-recursion?
    ... There is no difference between tail-recursion and iteration. ... That's why tail-recursion is so simple, ... fetch next instruction from instruction pointer ... instructions will manipulate the processor stack. ...
    (comp.lang.scheme)
  • Re: How do i increase the size of the program stack?
    ... function that has a correct end condition for recursion. ... For some input data,the recursive function gets called so many times ... How do i increase the size of the program stack? ... implementation-specific newsgroups, or at least platform-specific ...
    (comp.lang.c)