Path: utzoo!attcan!uunet!zaphod.mps.ohio-state.edu!usc!ucsd!nosc!marlin!aburto
From: aburto@marlin.NOSC.MIL (Alfred A. Aburto)
Newsgroups: comp.benchmarks
Subject: Re: BYTE and benchmarks (anecdote)
Message-ID: <1689@marlin.NOSC.MIL>
Date: 9 Jan 91 17:50:52 GMT
References: <1991Jan8.101912.15157@odin.diku.dk>
Reply-To: aburto@marlin.nosc.mil.UUCP (Alfred A. Aburto)
Distribution: comp
Organization: Naval Ocean Systems Center, San Diego
Lines: 44

In article <1991Jan8.101912.15157@odin.diku.dk> torbenm@diku.dk (Torben [gidius Mogensen) writes:
>
>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 :-)
>

Yes, this fellow sure did fall on his sword.  I seem to remember a number
of 'letters to the editor' on this subject.  In fact this fellow won
the Byte Magazine 'BOMB' award for receiving the most letters that
month. Yes, one wonders what tree this fellow fell out of :-)

A little thought (or a counter in the Fibonacci routine) would have
shown that the recursive Fibonacci requires 92735 calls to itself inorder
to calculate Fibonacci(24) whereas the non-recursive 'for' loop takes only
24 interations (loops)!  The overhead involved in the procedure (function)
call is, in this case, not very significant at all.  In other situations
it might be, but not in this one.

Actually, the number of recursive function calls is itself a Fibonacci
like (like) number.  The number of calls is equal to the sum of the
two previous sums plus one.  That is, the number of function calls for
Fibonacci(n), n = 0, 1, 2, 3, ..., is given by:

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, ..., s(n), ....

s(0) = 1
s(1) = 1
s(n) = s(n-1) + s(n-2) + 1, n > 1 .

Al Aburto
aburto@marlin.nosc.mil