Fibonacci Numbers, Recursion, And Terrible Examples

Goto Considered Appropriate In Some Cases

One of the most referenced papers in software development has to be Dijkstra’s seminal paper titled “Goto Statement Considered Harmful”.

Dijkstra didn’t actually author the title, but instead it was the creation of an editor en route to being printed in an ACM publication. It was changed from its original title of “A case against the goto statement”.

While the core essence of the essay is indeed that the goto statement can be harmful, Djikstra wasn’t making an absolute statement (as is commonly claimed, and which is an absolutism tendency of far too many in this industry), but instead was commenting on the abuse of goto that was occurring in the industry, calling for a sober evaluation of where it is appropriate, but more importantly where it is not.

Nonetheless, the meme was created and has been reused and abused in innumerable {$X} Considered Harmful declarations since.

So…how does a C# 3.0 implementation of Fibonacci
differ from a C# 2.0 version?

A month or so back the development webosphere was awash with references to Scott
‘s excellent blog, all excitedly linking (rel=”titillating”?) to his piece titled The
Weekly Source Code 13 – Fibonacci Edition”. This was particularly common in the .NET community, with many linkers describing it as an elucidating example of the many advantages of .NET 3.5 / C# 3.0.

I perused the entry, always eager to absorb that sort of information, but found it less than perfect. I withheld critical comment, hoping it would all just blow away.

Then this morning I opened up Visual Studio and happened to notice a link to his entry on the Start page.

Maybe it’s been there for a while (the last date is pretty old) and I just didn’t notice it before, but the title used on the Start page pushed me over the edge, coercing me to comment.

Recursion Considered Harmful

There are several issues I have with Scott’s Fibonacci entry.

First, the C# 2.0 (henceforth I’m dumping the subversion precision on the language versions) version is oddly dumbed down: C# 2 also has ternary comparisons, and it even has anonymous functions (including closure functionality). Yet the demonstrations
given contrast the simplest possible C# 2 implementation with the most obtuse C# 3 example.

Basically the only novel difference with the C# 3 example is that it uses a lambda, though of course it would be an absolutely terrible thing to use a lambda for.

It’s not a very good example of the implementation differences between the versions, which is the claim made by the Visual Studio start page, and was the description often used during the dissemination of this piece.

I like C# 3, but this isn’t a good demonstration of any advantage of the language.

Worse yet, the only place you’ll ever see recursion used to calculate Fibonacci numbers is in “Recursion for Dummies“type examples. To understand why that is, consider Scott’s C# 3 example, which he leads into with the statement “Now, here’s a
great way using C# 3.0

Here’s a logarithmic-scaled chart of the number of function calls necessary to calculate Fibonacci numbers in the C# 3 example Scott gave.

Obviously it gets unusable pretty quickly. Try calculating the 90th Fibonacci number using recursive algorithms…

In the same way that Goto can be harmful, the use of recursion is often a sign of badness, and this is no exception. Epic inefficiency is used instead of the obviously simple approach.

long CalcFibonacciNumber(long n)
    long current = 1, previous = 0, swapholder;
    while (n-- > 1)
        swapholder = previous;
        previous = current;
        current += swapholder;
    return current;

(Ignoring mathematical shortcuts)

Unrealistic Examples Considered Harmful

A lot of readers will be rolling their eyes right about now, muttering something along the lines of “Awww, come on…you didn’t seriously think anyone thought that recursion was a good way to calculate Fibonacci numbers, did you This is beginner’s stuff, and no one really thinks that’s the right way to do it!

I’m optimistic about the profession, so no, I didn’t really think it was a serious example (though I do think it nonetheless deserves some serious warnings to ensure no one becomes misled).

Instead it’s a sample of “here’s a demonstration of how to do something absolutely terrible — almost felony worthy — in a variety of programming languages….”.

This is still a serious problem.

The example given is so very wrong — even if it is what’s used in Recursion for Dummies books — that it makes it close to impossible to focus on the actual point being made, even if it had used comparable features of each language to demonstrate how the same task could be accomplished in each.

It reminds me of many early web service tutorials and advocacy pieces: Many used absurd examples like “a web service to add two numbers” (and amazing variations such as subtract two numbers, multiply two numbers, divide two numbers, compute the Log10 of a number, and so on. You get my point — things for which a web service would be entirely unsuited).

Stop it!

Stop with the ridiculous no-one-would-(or rather should)-ever-do-it-this-way examples. It completely undermines the value of the examples.

Surely there are realistic examples that would be more appropriate for demonstrating the advantages of lambdas (recursion {is recursion}; [goto {is recursion}], so there isn’t much
enlightenment provided there). How about “how to build a rudimentary regular expression parser in a variety of languages”, or for a web service “pulling weather data from a remote weather station”.

Something that a developer isn’t going to have to slog through with their brain fighting them on every line, demanding an explanation for the terrible design or algorithm they’re supposed to accept at face value.