The subject kinda says it all.
I know Fibonacci numbers are important and deeply embedded in the natural world (and other places too like finance).
But, did Fibonacci come to the sequence because of other math and/or observations which suggested it or was he just bored one day and wrote it down and only after that did people find it had a deeper significance and wide application?
I mean, the sequence itself seems something a bored kid in school could come up with while sitting in class.
He was studying the (idealized) population dynamics of rabbits (or at least, that’s the story I heard):
I did exactly that, in a boring history class. I also invented calculus. I had no idea these things had any practical use.
Fibonacci sequence I could see myself doing (but only as just a thing to do with no comprehension of its uses).
Calculus…nope.
I used to make grids of sequential numbers and figure out their sums and differences repeatedly. These would lead to interesting patterns but I doubt they ever had any mathematical significance and I always assumed some mathematician figured out the same centuries earlier.
As to calculus… by the time I started studying it in high school it seemed so alien to me that I don’ t know how I would ever have conceived of it on my own. Even today after taking the full sequence in college I still marvel at how it can be used to associate position, velocity, and acceleration with one another (as functions of time).
[hijack]
I wonder if Al Gore invented the internet while bored in class?
[\hijack]
Clearly you would find some fun with The On-Line Encyclopedia of Integer Sequences.
In order to teach recursive programming in an intro class, I start off stating very matter-of-factly that today’s lecture is about SEX. That really wakes the students up. Then I introduce how a population of animals can grow, resulting in the Fibonacci sequence (I use cattle instead of rabbits though). Then I bring up Fibonacci’s Wikipedia page with the rabbits, showing I didn’t just make up the story about it having to do with sex.
You can also draw squares, first one unit, then another one next to it, and then on their sides a square of two units, etc. Keep turning where each new square goes, and the inside corners forms a spiral. I wonder if he discovered this as well, or did someone else.
BTW, don’t use a recursive routine, it’s a really poor performer.
Its been a while since compilers can optimize “Tail recursion” to fix that for you.
Just ensure the return is unconditional and at the end of the function. (but it can optomise various little conditions to the return to, to turn it to unconditional tail recursion… which it then optimises… )
Not all compilers will do this though. AFAIK Java does NOT support any tail recursion optimization, yet Kotlin and Scala, both of which run on Java’s JVM, do. Python does not, though I am not sure if this is because most implementations are interpreted, or because it has been deemed not “pythonic” enough.
How is tail recursion not pythonic? Pythons are all tail!
All except the bit that bites (or bytes) you …
Fibonacci recursion is easy to teach, but I don’t talk about tail recursion at all with these neophyte programmers, some of whom are non-majors. It’s also an easy way to write an Android app that shows ANR Application Not Responding, at about the 12th Fibonacci number. Ugh!
This is only just now fully sinking in to me… I’m used to the textbook example of recursion being factorial. Which is inefficient, because recursion in general is inefficient (you’re effectively using the stack of function calls in place of a loop variable), but it’s still only linear in the number of arithmetic operations.
But a naive recursive implementation of Fibonacci would be exponential, with every function call making two more function calls. Effectively, to compute fibonacci(n), you’d end up calling fibonacci(1) a number of times equal to fibonacci(n), and adding them all up. Plus all of the calls with intermediate arguments.
Just for the record, I will mention that the efficient way to compute the f_n is as the nearest integer to \frac{1}{\sqrt5}(\frac{1+\sqrt5}2)^n.
From a mathematician’s PoV, that’s probably right. But considering there’s a square root and an exponent plus a couple floating point divisions there, for a computer, it’s probably faster to just do the additions. Especially if the result fits in the computer’s register and you don’t have to do arbitrary precision arithmetic.
Thinking about it some more, even if you don’t do the square root, and instead just input the two constants precomputed, it still is quicker to do the additions. One has n+1 floating multiplications and the other has n integer additions.
You don’t need to do n-1 multiplications to compute a^n. For large n, it’s cheaper to compute it as exp(n*ln(a)), using an efficient library like CORDIC or BKM to compute the exp and ln functions.
Or compute successive squares of a (i.e. a^2, a^4=a^2^2, a^8=a^2^2^2) up until the smallest power of two less than or equal to n, then multiply together the powers of a whose exponents correspond to ones in the binary expansion of n. At most 2lg(n) multiplications.
I discovered the Koch Curve about 80 years after Koch did.
I had a job interview about 20 years ago where I was asked to write a function which returned the nth number in the Fibonacci sequence. I wrote an iterative version, not recursive. It was good enough; I got the job.
Some years later I happened across the Wikipedia page (I think) for the Fibonacci sequence and was rather surprised to find there was a non-iterative way to calculate it, too. I wrote a very simple Python program for it, just to prove to myself that it worked, I guess.
The Fibonacci sequence was the first mainframe program I wrote, in COBOL when I was 14.
Then (by dividing the current sequence number by the previous one), I discovered the golden ratio (φ).
That led to a summer job converting COBOL (ICL) to COBOL (not ICL) - once I figured out global search and replace for PIC definitions, I ripped through the conversion.