wayne@dsndata.uucp (Wayne Schlitt) (07/10/88)
I used to think that recursion was unnecssary and very expensive, but now i am not so sure. what about the cases where you recurse from more than one place? can you do that without a stack of flags and lots of ifs? an example, how would you do something like this: void fna( x, y, z ) int x, y, z; { /* a bunch of setup */ if( /* some test */ ) { /* a bunch of code */ fna( a, b, c ); /* a bunch more code */ } else { /* some different code */ if( /* some other test */ ) fna( d, e, f ); /* yet some more code */ } } -- Wayne Schlitt | Design Data Corporation hplabs!hpfcla ----------\ | 1033 "O" St. Suite 324 ncar!handel!hpfcla ------>---> !dsndata!wayne | Lincoln Ne, 68508 ihnp4!upba -------------/ | (402) 476-8278
bill@proxftl.UUCP (T. William Wells) (07/13/88)
In article <WAYNE.88Jul9134227@dsndata.uucp>, wayne@dsndata.uucp (Wayne Schlitt) writes: > I used to think that recursion was unnecssary and very expensive, but > now i am not so sure. what about the cases where you recurse from > more than one place? can you do that without a stack of flags and > lots of ifs? an example, how would you do something like this: > > [example omitted] I'll be very surprised if your message does not draw flames from both the recursion and anit-recursion fanatics. But let me inject some common sense into what is likely to become a religious debate. The question you posed is meaningless. `Necessary' has a meaning only in a definite context. Since programming is a utilitarian art, like architecture, the appropriate question is "Is recursion the right tool for job X?" If the answer to that is indefinite, one can then ask: "Is recursion the most esthetic tool for job X?" So, to give some examples: should one code strlen() using recursion? (This from an idiot debate I got sucked into on comp.misc). Obviously no. Should one use recursion when the processor your program is to run won't be able to handle the stack? (Consider the poor soul limited to 256 bytes in a 6502 stack.) Or, when you need to control memory use and have no good way to check the amount of memory used by the stack? Obviously no. Should one use pure tail recursion? Depends on the programming language. In C, one should not use tail recursion; the only compiler that I know of that will optimize this out is gcc. Arguing that that is sufficient reason is very parochial. In Scheme, on the other hand, tail recursion is absolutely the way to go. Should one use recursion when the stack depth and function call overhead are not issues and there is a reasonable nonrecursive method of implementation? That is an esthetic issue. How about when the nonrecursive implementation is just the recursive implementation in disguise? Obviously yes. The point of all this is that recursion is just a tool. It is not a magic bullet as its enthusiasts claim, nor is it a ticket to hell as its detractors claim. Like any other tool, it has to be evaluated as to its appropriateness to the job. You might note that my examples are weighted towards not using recursion. There are several reasons for this, however, the main one is that, at least in C, unlike other control structures, recursion has an overhead that can't usually be avoided or ignored. In the real world, resources usually have limits that we are going to have to be aware of and which will affect the algorithms we choose.