Fibonacci Programming – Computerphile

Fibonacci Programming – Computerphile


Today we’re going to carry on the
recursion story a little more. Many of you, I hope, have seen my initial effort
in this direction which is the Recursion video. It’s featured stack frames – how
recursion is actually done – and the answer delivered back by ‘factorial’ will
be an integer answer. So, I thought what we’d do today is move on to another
example much beloved of Brady [Haran]. It’s called the Fibonacci sequence. He was an
Italian gentleman – that’s not his real name that was the nickname he was given –
I’ll try and stick to mathematical notation here the n+1 Fibonacci number is defined to be the nth Fibonacci number plus the n – 1th
Fibonacci number. Whereas with factorial it just followed itself
recursively round one strand a recursion here you’re adding in a second strand of
recursion. So this is sometimes called Multiply Recursive, whereas ‘factorial’
will be called Singly Recursive. But like all recursive definitions of functions
you do need an escape route at the bottom. If you keep on calling yourself
you could go on to infinity. But as you can see here, everything’s fine
so long as you write down what the first Fibonacci number is and the second one.
The second Fibonacci number and the first Fibonacci number are both defined
to be 1, We can now write down the Fibonacci sequence because it starts off
with a 1 for the first number, a 1 for the second number. So if I want F(3)
then I’m got to make n be 2 there. 2 + 1 is 3. So Fibonacci of 3 [F(3)]is the same as
Fibonacci of 2 [F(2)] plus Fibonacci of 1 [F(1),] Both [are] 1. So, the answer for F(3) is 2.
Every Fibonacci number is the sum of the two that immediately precede it. So the
next one, then, is going to be 2 + 1 [i.e.] 3. The one after that 3 + 2
5, 8, 13, 21. You might think: “Well, very interesting but what does that apply to?
Why should that be so fascinating?” Well, it’s fascinating first of all, for
the simple reason that in the Computerphile / Numberphile family, some of you will
know that the wonderful ‘Godfather’ Brady has already made and got ahead of the
game, a video about Fibonacci. He actually had a Fibonacci Tartan designed and had it made up!

>>Brady: … and the rows and the threads that have been used to create this
design are based on the Fibonacci sequence.>>DFB: Heaven knows how much it cost him to get
it made up! But there it is.
>>Sean: As computer scientists why do we care about Fibonacci?!
>>DFB: The reason I’m doing this with you is the following:
Like ‘factorial’, ‘Fibonacci’ is a recursive function that can be de-recursed. You
could do it in ‘for’ loops – things that can be de-recursed are called Primitive
Recursive, so Fibonacci is just another one. It enables us also to draw pretty
pictures, which we’ll do in a minute and I rather like doing that. But having done
Fibonacci and factorial – but this will have to be in a separate video – you then want to
say: “Well, not everything can have the recursion taken out of it. Some things
really are recursive. I’ve actually written a PostScript program that will
print out the Fibonacci numbers for you up to the value of ‘fib(10)’ being 55. We’ll
put out a link to this program and those of you who’ve got Ghostview, or Ghostscript
set up, try running it. You should get this coming out all right.
I can only apologize it I’ve done it in Helvetica. The thing you’ve got to be
prepared for in PostScript is you’re at the mercy of the fonts you have
available in your interpreter. Don’t blame me if it comes out in boring
Courier. That tends to be the default when it doesn’t have access to the font
that’s asked for.
>>Sean: Comic Sans! >>DFB: It’s more likeely to be Courier actually!
When you look inside the program for that and I will do, very briefly, but absolutely
not in detail … First of all, here is my definition of Fibonacci ‘/fib’
is going to end ‘def’. That’s the definition of the Fibonacci function. To
head off trouble at the pass I’ve even put error messages in it. What I made it
do, to get those numbers to come out, is go round a ‘for’ loop ten times and every
time it goes around it calls up ‘fib’ but every time it goes into ‘fib’ it calls
itself recursively. It gets straight back inside itself and, there we are, out it
comes. It does work absolutely fine but if you’re going to start doing recursive
stuff in PostScript then, by definition, you’ve got to have something that
corresponds to stack frames, right? And we now have C and Java and things to do it;
they do it automatically. What about in PostScript? Well, PostScript is wonderful it makes you make your own stack frames but it
gives you a fabulously – what’s the word – versatile, way of doing it. Basically in
the second line here this thing ’10 dict begin’ and what that means is: “Get me a
dictionary with ten spaces in it”. And if you think that that ’10 dict’ is [also] like
saying: “Give me a stack frame with 10 spaces in it because I’m going to use it
and put values in it – to manipulate them all on my own”. You’ll remember when you
look back at the stack frame story in the Recursion video. It’s great C does
it for you. But the penalty, if you like, is you’ve
got to accept the way it handles the stack frame. unless you want to get into
some most appalling hacking you’d better not mess with your stack frames. You
could end up in an awful mess. Whereas PostScript is basically doing its usual thing.
Y’know: “You’re a serious program with tons of experience. If you get messed up
you’ll soon sort yourself out I’ll let you manipulate the stack frame every
time we go around recursively into ‘fib’ ” It basically hits ’10 dict begin’ which
says: “Make me another stack frame”. I mean another recursive instance of Fibonacci.W
what other things can we do with Fibonacci that make it interesting for
mathematicians as well as computer scientists? Well, one of the things that I
set many years ago, in a Digital Documents course, was the
following. If you put Fibonacci-sized boxes together and group them properly
and then you join them up you can draw some most amazing shapes. This is the
Fibonacci spiral and if you look here you can see what I’m doing. Once I’ve got
the basic Fibonacci recursive function working I’ve built on top of it extra
routines. And this is the beauty of PostScript. You not only get the stack,
you get the recursion, you get the stack frames … but you can draw two
dimensional pictures as well! So, what I got it to do was to go round and every
time it visited ‘fib’ and got an answer like 1 [interpret this as]: “draw a box of unit size”.
And then the next box along, just to its left, is also of side 1. And of course the
secret is knowing where to attach the next box. I have attached the square of
side 2 direct to the south,as it were, of the two boxes of side 1 and then
the 3 box gets attached to the east side. And then it goes up north and then
it goes west. And as you go around you get 1, 1, 2, 3 When you’ve
stacked your boxes correctly you go into them and you draw an arc across each of
the boxes and I’ve chosen to do it, at this time, in an anti-clockwise direction
And you end up with this beautiful looking spiral – known as the Fibonacci
spiral. It’s an approximation to a well-known mathematical object called
the logarithmic spiral

100 thoughts on “Fibonacci Programming – Computerphile”

  1. Here's a little fact:

    Did you know the human hand follows the Fibonacci sequence? Start at the tip of any finger and measure the distance between the joints all the way to your wrist. Its actually what I go by when I'm 3D modeling a human hand to proportion.

  2. (phi^x-cos(pi*x)*phi^(-x)) / sqrt(5)
    where phi = (1+sqrt(5)) / 2
    this is a continuous version of the fibonacci sequence that does not use recursion
    i believe it is quicker for larger numbers

    could you maybe do a video on the ackermann function or hyperoperators?

  3. ZanderTheLegendary

    Haskell 🙂
    — Horrendous fibonacci algorithm
    fibonacci :: Int -> Int
    fibonacci 0 = 0
    fibonacci 1 = 1
    fibonacci n = fibonacci (n – 1) + fibonacci (n – 2)

    — Better version
    fib :: Int -> Integer
    fib n = fibs !! n
        where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

  4. Hugo Legorreta Moysén

    Y sigo teniendo demostraciones de que mi tatto es un EXCELENTE Y MUY BIEN ELEGIDO TATTO algo de lo que nunca me arrepentiré

  5. A non-recursive equation can be made for fibb(n).  What I have been trying to determine is if a non-recursive equation can be made if we scale the recursion to a third degree.
    If a1=1, a2=1, and a3=1, and a(n+1)=a(n)+a(n-1)+a(n-2)….
    can a non-recursive function be made?

  6. /facepalm Recursion in postscript. I'm nearly as advanced in years as the distinguished Prof. but I wouldn't go near postscript or recursion if you paid me. And people do pay me. For gods' sakes man, issue a disclaimer video before we have programmer TNG thinking postscript and recursion are good ideas. Please, I beg you. Before it's too late!

  7. Maybe you could use the Fibonacci sequence to introduce the concepts of Memoization and Dynamic Programming.

  8. Why is F(1)=1 and F(2)=1 and not F(1)=0 and F(2)=1? That would still reproduce the same sequence but begin with a digit earlier: 0 1 1 2 3 5 8 13…

  9. Computerphile has been literally posting the exact same material that I have been learning in my data structures class. It has been great for furthering my understanding!

  10. My assignment in class was to write a program that could handle calculating the Fibonacci sequence to the 1000th number. But we could not use any of the large number libraries. We had to build a linked list class that could add and store the numbers.

  11. The question is: Just by watching this video, can you determine if Computerphile will ever stop making videos about recursion?

  12. if you follow the fibonacci sequence in reverse, you get alternating positive and negative numbers of the same as forwards. just thought it was interesting.

  13. Note to self, don't watch University of Nottingham videos late at night. The sound of the train reminded me of scary movies and made me all paranoid of what's behind me!

  14. I remember reading that any recursive function can be converted into an iterative procedure (though it may require the use of a stack.)  This makes sense because assembly language (and I don't care what processor we are talking about; I've seen several and it holds for all of them) does not actually allow for recursion.

  15. Fibonacci Christmas Tree:

                    0
                1  1  
                1  0 -1
            2  1  1 -2  
            3  1  0 -1 -1
        5  2  1  1 -2  1
        8  3  1  0 -1 -1  2
    13 5  2  1  1 -2  1 -1
    21 8  3  1  0 -1 -1  2 -3 
                    1
                    0
                1  1 -2

  16. I see a few recursive functions in the comments, some call it a 'better' version, but they have probably never called those functions with high integer values… stack overflow imminent.

  17. Python FTW! 🙂

    def fib(n):
        if n < 0 or type(n) != int: raise ValueError
        if n < 3: return int(bool(n))
        return fib(n-1) + fib(n-2)

  18. For people who enjoy fun bits of trivia, the desks behind which the panellists sit on QI each have Fibonacci spirals on them. If you take adjacent pairs of Fibonacci numbers and divide them (1/1, 2/1, 3/2, 5/3, 8/5,…), you'll find yourself steadily getting closer to the quantity which is written behind Stephen Fry's right ear.

  19. That's just ashamingly basic. I'm getting an impression this channel is geared towards middle schoolers 🙂

  20. (defun fibrec(n &key (a 0) (b 1))
    (if (= n 0)
        a
      (if (= n 1)
          b
        (fibrec (1- n) :a b :b (+ a b))
    )
    )
    )

  21. You can also use Z Transform to get a formula for every nth number in the fibonacci sequence. You get F(z) = z/(z^2-z-1). Inverse Z transform gives, F(n)=(-(1/2 (1 – Sqrt[5]))^n + (1/2 (1 + Sqrt[5]))^n)/Sqrt[5]. If you put in negative numbers, and plot a curve in the complex plane. Imaginary number as the y axis and real numbers as the x axis. you get a fine spiral too 🙂

    If you plot from 0 to 2, I really love the little loop the curve does to pass number 1 twice 😀

  22. Really enjoyed the talk you did on the open day for the university. It's where i'd like to come to study Computer Science. It was awesome to see you in the flesh haha Keep up the great work! 😀

  23. I can't understand, that every time the faculty and the fibonacci secence is used to explain recussion. At higher n this way is way too slow and most times impossible. Only a memoized recursion can slightly beat the iterative solution, because, it is basically the same. But there are better examples like the Euler Tour, actually recursion is extremly important for graphs, more examples in this directions please. Because what should I do with a simple recursion that didn't allow me to compute fac(100) or fib(55) because the recursion depth is way to deep for normal computers.

  24. By the way, the dynamic approch in python:
    memo = {}
    def fib(n):
        if n in memo:
            return memo[n]
        else:
            memo[n] = n if n < 2 else fib(n-2) + fib(n-1)
            return memo[n]

  25. F(n)=F(n-1)+F(n+2) and F(0)=F(1)=1
    int fibo(int n)
    {
               if(n<=1)
                       return 1;
               else 
                       return fibo(n-1)+fibo(n-2);
    }

    but the problom is how can i calcule exp(F(n)) in recursive fonction ???? 

  26. "The fact that this region of the universe has a limited observable range as the waves come from a distance radius.  . ..And the fact that the electron is a perfectly round sphere.. .  .Are two sides of the same + and – coin!!

    There exists only two combinations of these two spherical + and – electromagnetic sine waves, or wavefronts multiplying and dividing at right angles.. .  .They have opposite vectors and quantum spin forming the positron and electron wave centre.. .  .4pi R2=/N pi Re2.. .  .

    Or "the two energy states of Qubits" in quantum computing which can be such things as photons, trapped ions, atoms, electrons, and nuclear spins made of vibrating wavefronts called shells in particle physics, or spherical standing wave structures over a period of time.. .  .E2=mc2/c4+p2/c2.. .  .Only difference is time dilating Volume!!

    Their output was the negation of their input: 0 goes to 1/1 to 0.. .  .the start of a Fibonacci spiral.. .  .

    Therefore generation of any information exceeds radiation during the first half of the cycle.  . ..Radiation now exceeds generation during the second half of the cycle as the constant outward momentum of EMR (de-compression) repels like charged particles absorbing energy and emitting the density from the two previous vectors spiralling out the Fibonacci sequence seen everywhere in nature.. .  .

    Since centre is everywhere forming the total amplitude of sinusoidal waves at each and every point of space then mc2 represents the expansion of mass which is an opposite de-compression from the energy compression c4+ acting upon time dilating inertial ref-frames p2 at the expense of gravitational potential c2.. .  .

    Space is a division of solidity into entropy C2 the second law of thermodynamics.. .  .But also E2= a multiplication of volume at the expense of gravitational potential."
     

  27. Fibonacci's real name is Leonardo of Pisa.
    On a similar note, Da Vinci is Italian for "of Vinci", so it's not Leonardo Da Vinci's last name, rather, it's his birthplace.

  28. So I've skipped a couple a episodes. Has Brady lost a tremendous amount of weight or was he abducted by aliens and replaced by a lousy replica? (In other words: Who the hell is the guy in the end of the video?)

  29. Do all of the people posting their O(N) solution for the nth Fibonacci number know that there is a closed form for the nth Fibonacci number that uses the Golden Ratio. The nth Fibonacci can be computed in O(1) using this.

  30. I've been reading through the wizard book (The Structure and Interpretation of Computer Programs) recently, and another interesting thing about the tree recursion definition of Fibonacci(n) is it's order of growth. Because each time you want to compute a fibonacci number you have to compute the last two fibonacci numbers, the time it takes to compute a given fibonacci number is itself a fibonacci number.
    Fibonacci numbers are intricately linked to the golden ratio, and in fact a given fibonacci number is the closest integer that is a result of taking the golden ratio to the nth power, divided by the square root of five. So with respect to time, the order of growth is given by (phi^n / sqrt(5)), which we can put as Theta(phi^n) for simplicity's sake. This is an exponential order of growth, and so very bad if you want to compute large fibonacci numbers!

  31. With memoizing in Python:

    computed_fib = {1:1,2:1}

    def fib(n):
        if n in computed_fib:
             return computed_fib[n] 
        else: 
            computed_fib[n] = fib(n-1) + fib(n-2)
            return computed_fib[n]

    And the 2015 Fibonacci number would be:

    In [17]: print fib(2015)
    5762488896030140993970127447076792874336403418687476758848483166124324633496452225745760531625355769343572448331578223521805650643845496976578903145216445829111893577603290923340147837405958982446562955804144013677696770990394272037162587085666026561601045718910518761496231846434488662629501872606840106837782272291703369191403678479329790837646825844843416090881795139086749031394076973360344297117287140768030461857985

  32. this is the fibonacci programm in vb for an consoleapplication
    Module Module1
        Sub Main()
            Do
                Dim zähler As ULong = 2
                Dim index As ULong = 1
                Dim zwischenspeicher As ULong
                Dim fm1 As ULong = 1
                Dim limit As ULong
                Console.WriteLine("Write the limit, until wich number it should be calculated.")
                Do
                    Try
                        limit = Console.ReadLine()
                        Exit Do
                    Catch
                        Console.WriteLine("Please write a number greater or equal to 0")
                    End Try
                Loop
                Console.WriteLine("The value of fib 1 is 1")
                Try
                    Do Until index > limit
                        Console.WriteLine("The value of fib " & zähler & " is " & index)
                        zwischenspeicher = fm1 + index
                        fm1 = index
                        index = zwischenspeicher
                        zähler = zähler + 1
                    Loop
                Catch ex As Exception
                    Console.WriteLine("Error:")
                    Console.WriteLine(ex.Message)
                End Try
            Loop
        End Sub
    End Module

  33. MrCheaperCreeper

    There is also a formula to find out the nth position in the Fibonacci sequence.

    f(n) = ((1+√5)^n – (1-√5)^n) / (2^n(√5))

  34. Erika Mauersberger

    Dear Professor Brailsford,
    Thank you so much for this series, I"m a nurse whose gone back to school for web development and you just made a part of my program a success instead of a failure.
    Many thanks!

  35. This man is such a great teller, i found gold in this video's. Golden knowledge and am learning all of this. And I feel that you are making the world a better place with sharing this. Thank you.

  36. I absolutely love and admire this guy. Well, I don't think I haven't liked any of Numberphile or Computerphile's guests ever, they are all so smart and charismatic!

  37. Fibonacci spiral in python 3

    from time import sleep
    import turtle
    turtle.color("light blue")
    turtle.pencolor("dark blue")

    a, b = 0, 1
    for i in range (2000):
    c=(a+b)
    a= (b)
    b = c
    print (c)
    turtle.circle(c, 90)
    sleep (.05)
    input()

  38. OI! dont go dissing comic sans when in the recursive videos one of those n's was comic sans . . . but ye, comic sans . . . .

  39. Thank you computerphile, watching these videos I finally remembered what it was that made me choose programming as a profession. I feel like a 10 year old right now 🙂

  40. I just wrote a Fibonacci sequence using tail calls to optimize it so it doesn't use the stack. I think that would make an interesting video. Thanks for your work, I love the channel. Here's the links to my program, it's written in javaScript. https://jsfiddle.net/syntaxerrorforbearer/yjjbxhve/ – optimized (not using the stack), and https://jsfiddle.net/syntaxerrorforbearer/uku716z2/3/ – recursive version using the stack. If you put a large number in the recursive version the browser will crash because the stack gets overflowed, but the tail call version handles big numbers no problem because there are no pending computations between recursive calls.

  41. Just wrote up a script to calculate the Fibonacci in python. I just noticed once it gets to 13 digits(on every 60th iteration), the last digit starts over again. Goes on like this as far as I could tell. Nothing huge, just an interesting observation. Anyone got any ideas why?
    1548008755920 (0)
    2504730781961 (1)
    4052739537881 (1)
    6557470319842 (2)
    10610209857723 (3)
    17167680177565 (5)
    27777890035288 (8)
    44945570212853 (13)
    72723460248141 (21)
    117669030460994 (34)
    190392490709135 (55)
    308061521170129 (89)
    498454011879264 (144)
    806515533049393 (233)

  42. <?php
    $a = 1;
    $b = 1;
    $c = 1;
    $counter = 0 ;
    while ($counter <= 500){
    echo $c."<br />";
    $c = $a + $b;
    $a = $b ;
    $b = $c ;
    $counter = $counter+1;
    }
    ?>

  43. Doesn't a recursive approach lead to an exponential nightmare with larger values of n though? Unless you do something clever with a globally available array of already determined values set from previous function calls, you'll find an ever increasing number of cases where the function is called with the same arguments as one or more others, which is entirely pointless for a deterministic function.

  44. sometimes you need to trust your teacher or instructor to understand something, I looked up recursion online because I have difficulties to understand it, and then finally Professor Brailsford helped me and I got it, but I think the only reason is because he is the only one I trusted and for the first time I listened to the end, maybe because he is very much experienced and look very wise person to me

  45. i guess for javascript:

    var fibNum = 8; //Amount of numbers in the sequence (example: 6)
    var fibArr = [];
    fibArr[0] = 1,fibArr[1] = 1;
    var fibString = 'Fibonacci Sequence: 1, 1';
    var fibCn = 2;
    for(var i = 2; i < fibNum; i++) {
    fibArr[i]=fibArr[i-1]+fibArr[i-2];
    fibString = fibString + ', ' + fibArr[i];
    fibCn += fibArr[i];
    }
    var fibSum = 'Sum: ' + fibCn;
    var total = fibString + ' ' + fibSum;

  46. … and you can make it into an actual logarithmic spiral by using actual golden rectangles (GRs) from the start, each added square making the next larger GR out of the previous one; and continuously increasing the radius of curvature of the spiral, not just at each rectangle boundary crossing.
    Might be interesting to see those two sets of rectangles and spirals co-overlaid, maybe in contrasting colors.

    Fred

  47. About a year ago, I had a great Fibonacci sequence idea, which I call Fibinary notation. It turns out (not too unexpectedly) that not only was I not the first to think of the idea, I also wasn't the first to think of the name.

    If D is a sequence of binary digits (i.e. D_i = 0 or 1 for all i) then we can interpret it as an integer by
    value = Sum_i D_i F_{i+1}.
    (Smallest index is 1.) Compare to binary notation, where
    value = Sum_i D_i 2^{i-1}.
    (When we write D as a string of digits, we write it from highest index on left to lowest index on right.)

    One interesting outcome is that Fibinary notation is not always unique, e.g. 100 = 3, but 011=3 also. In fact, anywhere in the sequence you see '011', you can substitute '100' without changing the value (and vice versa.) I call it canonical form when there are no adjacent 1s.

    It isn't too hard to come up with an addition algorithm, although it would be hard to efficiently implement in logic gates because you don't know how many times you need to do 011 -> 100 substitutions. I looked at multiplication, threw up my hands in horror, and tried no further.

    Web search for 'fibinary' to find out more. There is also an academic paper on a generalization of fibinary notation, the citation to which I don't have on hand (as I recall, it did not use the name 'fibinary').

  48. Why mess with the dict stuff? Postscript already has an "easy" to use stack

    /fib {
    dup dup 1 eq exch 2 eq or
    { pop 1 }
    { 1 sub dup 1 sub fib exch fib add }
    ifelse
    } def

  49. that seems like an awful amount of code to produce fibonacci. This is in R
    fiboSeq<- c(1L,1L)

    for(i in 3:20){

    fiboSeq[i] <- fiboSeq[i-1] + fiboSeq[i-2]

    }

    fiboSeq

  50. It is a law of nature that computer scientists always count from 1, while mathematicians count from 0. Mathematicians who become computer programmers have to attend special indoctrination camps.

  51. Christina Eneroth

    Am I the only one thinking the Fibonacci spiral is terribly ugly? I can see every point where the radius changes almost as if it was a sharp corner. I would even call it the uncanny valley of sharp corners, as it looks off but it's hard put your finger on why until you learn about derivatives.

  52. why can't you declare an array and pass it to your c function and get the results in it??
    Isn't that the same thing??

Leave a Reply

Your email address will not be published. Required fields are marked *