Language for the ages

Sean 'Captain Napalm' Conner spc at conman.org
Thu Oct 20 14:22:39 CDT 2005


It was thus said that the Great John R. Hogerhuis once stated:
> 
> A recursive algorithm can be quite elegant and easier to understand in a
> limited, useless educational example. But once you start adding all the
> little bells and whistles (like, say, exception handling) it quickly
> becomes a hairy mess.

  I used to think that recursion was useless, due to the examples given in
school, like multiplication, the Fibonacci sequence or the Towers of Hanoi,
but in the past few years, I've found a few places (only a few) where it
does lead to a clean implementation, usually dealing with tree-structured
data, like a file system:

	process(dir)
	{
		foreach entry in (dir)
		{
			if (entry isa file)
			then
				munge(entry)
			else if (entry isa directory)
				process(entry)
		}
	}

  But with that exception, I rarely use recursion.

  Also, modern languages tend to convert tail-recursion into loops.  For
instanace, in Erlang [1]:

	fib(N) -> fibitr(1,0,N).

	fibitr(_,B,0)     -> B;
	fibitr(A,B,Count) -> fibitr(A + B,A,Count - 1).

  The Erland compiler can convert the recursive function fibitr/3 [2] into a
version that loops.  The naive version:

	fib(0)	-> 0;
	fib(1)	-> 1;
	fib(N)	-> fib(N-1) + fib(N-2).

  Is *MUCH* slower, since it isn't tail recursive.

  -spc (Erlang *might* be on topic ... )

[1]	A Language developed by Ericcson to run their phone switches.  It's
	an interesting language

[2]	the fibitr function that takes three parameters.  And in Erland, 
	variables don't have types, values do. [3]

[3]	Ick.  But hey, it's what all the modern lanaguages are doing
	nowadays.



More information about the cctalk mailing list