Fibonacci Programming - Computerphile

Following on from our film on recursion, Professor Brailsford uses the Fibonacci Sequence as a further demonstration of recursive programming.

Fibononacci on Numberphile

This video was filmed and edited by Sean Riley.

[BewilderedBird]

No joke, this channel, and, in particular, this man, Professor Brailsford, are very significant factors in my decision to go back to college at age 30 and get my bachelor's degree in Computer Science. I am now halfway done with my degree, and I have a perfect 4.0. I never wrote a line of code until I was 29, but the programming bug bit me hard. Thank you for inspiring my love of computer science, Professor!

[underpaidnurse]

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!

[BenjaminAlexander]

We're going to cover 'recursion' again?  I see what you did there....

[jmlassen]

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!

[MarcoMeerman]

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.

[aserhassan]

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

[keen]

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!

[Pterryreal]

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]

[chkhd]

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 :)

[JoshLathamTutorials]

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! :D

[GreenJalapenjo]

Tail recursive Fibonacci in Erlang:

fib(N) -> fib(N, 1, 0).

fib(0, Acc, _) -> Acc;
fib(N, Acc, Tmp) -> fib(N-1, Acc+Tmp, Acc).

[Lttlemoi]

The most beautiful definition of the Fibonacci sequence I have seen is still this Haskell one liner:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

[PvblivsAelivs]

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.

[PressStartLetsPlay]

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))

[tomc.]

It feels like Winnie the Pooh is teaching me maths!

[JavierRuizGonzalez]

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)

[TheAlison]

6:05 very convenient how the lighting turned dark as he was saying this

[michaelwoodhams]

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').

[Gimbar]

Haskell:
fib 0 = 0
fib 1 = 1
fib n = fib ( n - 1 ) + fib ( n - 2 )

[Orxenhorf]

It's much less computationally intensive if you define f(n) = 2 * f(n-2) + f(n-3).
You do need to define one more special case though:  f(1)=1 f(2)=1 and f(3)=2.

f(10) would then take 17 function calls instead of 55, and f(20) would take 301 instead of 6, 765.