Re: Any use for recursion?

Tomás Ó hÉilidhe wrote:
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.

In modern languages there is no 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.

That depends entirely upon the language implementation you are using.

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!

Stack limits typically allow hundreds of thousands of recursive calls.

So basically I'm asking if there's any place _at all_ for
recursive functions?

Recursion is ubiquitous in modern software.

Is there any example of an algorithm that can be
implemented as a recursive function which _cannot_ be implemented
better as a loop?

You just gave an example. Your non-recursive implementation is not only
hideous by comparison and wrong but it also offers no advantages whatsoever
over the recursive implementation.

Can someone please post an example, if any, of an algorithm that's
better done as a recursive function?

Algorithms that traverse trees and divide and conquor algorithms are obvious
examples.

Look at this recursive function for inserting into a balanced red-black
tree:

let rec ins x t = match t with
`E -> `R(`E, x, `E)
| `R(a, y, b) ->
if x < y then `R(ins x a, y, b) else
if x > y then `R(a, y, ins x b) else t
| `B(a, y, b) ->
if x < y then match ins x a, y, b with
`R(`R(a, x, b), y, c), z, d -> `R(`B(a, x, b), y, `B(c, z, d))
| `R(a, x, `R(b, y, c)), z, d -> `R(`B(a, x, b), y, `B(c, z, d))
| a, x, b -> `B(a, x, b) else
if x > y then match a, y, ins x b with
a, x, `R(`R(b, y, c), z, d) -> `R(`B(a, x, b), y, `B(c, z, d))
| a, x, `R(b, y, `R(c, z, d)) -> `R(`B(a, x, b), y, `B(c, z, d))
| a, x, b -> `B(a, x, b) else t

let add x s = match ins x s with
`R(a, y, b) -> `B(a, y, b)
| s -> s

A non-recursive alternative is likely to require many times more code, will
be less compositional and will run more slowly in many modern environments.

Recursion is also useful when evaluating abstract syntax trees in programs
like interpreters or term rewriters because the evaluation of one
expression can depend upon the evaluation of subexpressions:

let rec eval vars = function
| EApply(func, arg) -> apply (eval vars func) (eval vars arg)
| EAdd(e1, e2) -> VInt (int(eval vars e1) + int(eval vars e2))
| EMul(e1, e2) -> VInt (int(eval vars e1) * int(eval vars e2))
| EEqual(e1, e2) -> VBool (eval vars e1 = eval vars e2)
| EIf(p, t, f) -> eval vars (if bool (eval vars p) then t else f)
| EInt i -> VInt i
| ELetRec(var, arg, body, rest) ->
let rec vars' = (var, VClosure(arg, vars', body)) :: vars in
eval vars' rest
| EVar s -> List.assoc s vars
and apply func arg = match func with
| VClosure(var, vars, body) -> eval ((var, arg) :: vars) body
| _ -> invalid_arg "Attempt to apply a non-function value";;

Of course when I say, "better", it could refer to things like:

* Short (e.g. just three lines of code)
* Easy to understand when you first glance at it
* Fast execution time
* Minimal resource requirements (e.g. memory and stack space)

but I'd like to hear what arguments people would pose in support of
using recursive functions?

They make life easier and often make code faster. Stack allocation is often
faster than heap allocation, particularly in multithreaded environments
where the stack is thread-local store.

Regarding the example I give above, well I
think it's nice and short but then I don't think this justifies the
ridiculous overhead in terms of execution speed and stack usage.

There is no performance difference and you are only making at most tens of
calls, so stack consumption is guaranteed to remain well within acceptable
limits.

(Please ignore the fact that the code calls "putchar" which has
massive overhead thus making negligible the overhead imposed by the
recursion, I can give other examples -- or at the very least pretend
that putchar is routed into a communications link that's running at 1
gigabit per second).

The problem is that you are only looking at a single language that has poor
support for recursive, probably with a compiler that does a poor job of
handling recursion. Try more modern languages and you will quickly see how
beneficial and cheap recursion can be. Try converting any of my examples
into C++, for example.

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

They are essential to the working of all of our products because we only use
modern languages like F#, OCaml and Mathematica.

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com/products/?u
.

Relevant Pages

  • 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: Macros versus lists
    ... C is a stack based language, ... You are calling six functions with each instantiation of the macro, of which, two are so expensive that you could add a lot of stuff there and the performance of your application wouldn't really notice a thing. ... You can just aswell make code slower rather than faster with "inlining" too much, usually inlining is better when the workload of the function is smaller than the calling overhead. ... If the only way to achieve a good performance is to use goto's, global variables and other debatable constructs there is usually something gone horribly wrong. ...
    (comp.graphics.api.opengl)
  • 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: grassfire algorithm in java
    ... All you have is the stack overflow error message, ... >> rather long, uninformative stack trace, and no other options. ... along with the recursion count. ... void showResult{ ...
    (comp.lang.java.programmer)
Loading