Totally OT, but frustrated.....

Sean 'Captain Napalm' Conner spc at conman.org
Sat Mar 26 15:53:54 CST 2005


It was thus said that the Great Alexander Schreiber once stated:
> 
> > They demo'd an example that "can not possibly be solved in ANY way
> > but recursion". 
> 
> If they claim any such bullshit then they obviously weren't paying 
> attention during class. Any recursive algorithm can be implemented
> as an iterative solution. At worst by emulation of the recursion 
> stack, but usually much better. Recursive algorithms are often more
> elegant and easier to implement. Unfortunately they tend to blow up the
> stack if one throws sufficiently large datasets at them. At which point
> one switches to a non-recursive implementation ;-)

  Scheme is required to recognize tail recursion (where the last thing the
function does is call itself) and convert it into a loop.  I personally felt
that recursion was always oversold and that there were very *few* occasions
where it was needed (but where it was needed, it was very elegant).  I felt
that way mainly because of the examples used to teach recursion---they were
always the Fibonacci sequence or some other trivial example that would work
just as well with loops.  A much better example (I felt) was expression
parsing:

	<expr>   := <term> '+' <term>
	<term>   := <factor> '*' <factor>
	<factor> := <number> | '(' <expr> ')'
	<number> := '0' ... '9'

  But sadly, that was only taught during compilers class.

  -spc (The example above could be done in a loop ... )




More information about the cctech mailing list