Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!att!tut.cis.ohio-state.edu!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!dkuug!diku!torbenm
From: torbenm@diku.dk (Torben [gidius Mogensen)
Newsgroups: comp.benchmarks
Subject: BYTE and benchmarks (anecdote)
Message-ID: <1991Jan8.101912.15157@odin.diku.dk>
Date: 8 Jan 91 10:19:12 GMT
Sender: news@odin.diku.dk (Netnews System)
Distribution: comp
Organization: Institute of Computer Science, U of Copenhagen
Lines: 46


Sometime in '88, BYTE published a special issue on benchmarks. I don't
have the issue handy, so I can't tell you which month it was.

One of the articles was an overview and discussion of popular
benchmarks that was in use or had been in use previously.

During this overview, the author (I can't recall his name) came to a
then popular Pascal benchmark suite, containing a recursive Fibonacci
number program to test the speed of recursive function calls. In a
moment of inspiration the author had the marvelous idea that he would
write Fibonacci in a non-recursive style, to compare the speeds. To
his amazement, the recursive program used several thousand times as
much time as the non-recursive program to evaluate Fibonacci(20). His
conclusion was that recursive function calls must be very expensive
indeed :-)

What really happened must have been this: the recursive program was
written in the "naive" fashion:

	function Fibonacci(n : integer) : integer;
	var result : integer;
	begin
	  if n<2 then
	    result := n
	  else
	    result := Fibonacci(n-1) + Fibonacci(n-2);
	  Fibonacci := result
	end;

which is known to use exponential time. The non-recursive program was
propably written using a for-loop:

	a := 0;
	b := 1;
	for i := 1 to n do begin
	  t := a+b;
	  a := b;
	  b := t
	end;
	Fibonacci := a;

which uses linear time. Using this comparison, you can conclude that
recursive calls are arbitrarily more expensive than a for loop :-)

	Torben Mogensen (torbenm@diku.dk)