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

Just love the Prof!

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.

(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?

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)

Is there a term for something like 1+2+3+4+5+6+7 etc ?

So, did he actually explain what kind of operations can´t be de-recursed?

Could you do a video on prolog?

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

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?

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

/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!

also known as "the golden spiral"

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

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…

And now the Ackermann function, please 🙂

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!

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.

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

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.

I have an itchy Fibonacci

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!

Do a Computerphile or Numberphile or both on the Mandelbrot set!

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.

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

Possible to do this at O(log n), by squaring matrix transforms.

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.

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)

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.

Would love to see more videos on recursion!

de-re-cursed 🙂

Aaaaand…. cliffhanger…

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

(defun fibrec(n &key (a 0) (b 1))

(if (= n 0)

a

(if (= n 1)

b

(fibrec (1- n) :a b :b (+ a b))

)

)

)

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 😀

You sent me here from the university of Nottingham open day.

wow, i don't understand shit

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! 😀

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.

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]

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

Interesting

"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."

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.

fibonacci easy as 1,1,2,3

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

Please make a video about polymorphism

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.

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!

This fibonacci programming they used in building of Pyramids.

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

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

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

Really liked that =)

0:20 no annotation?

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!

What code line(s) should I change to make it calculate more? I found that Notepad++ can modify its code.

i dont comment much but Professor Brailsford has to be related to hannibal lecter

what is the formula of logarithmic spiral approximated by Fibonacci spiral?

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.

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!

Python:

fib (x) = (1/(5*

.5))((((1+(5*.5))/2)**x)~~(((1~~(5*.5))/2)**x))PROFESSOR BRAILSFORD

CAN YOU PLS BE MY COMP SCI PROFESSOR

YOU ARE LEGEND IN SOUTH KOREA

Stack frames?! I need a video on it, professor!

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

who uses post script for programming? LOL.

Postscript reminds me of FORTH

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

So I assume that F1=1 and F2=1, so therefore F0=0 yes?

Fib on a c ha ha 😎

I love writing recursive programs. They're so elegant! (If occasionally inefficient)

Am I the only one who, if I made a movie about recursion, would have it link to itself?

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 🙂

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.

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)

i can't find a problem with youtube website design 😈😈😈😈

Rumor has it professor Brailford dreams about recursion

4:33 this sounds like a name for some kind of a world replacement meme video…

loving the scrap paper 😉

<?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;

}

?>

#GPC – 2017

x, y = 1, 1

while True:

print(y)

x, y = y, x+y

I thought that all recursive programs could be written iteratively.

NOPE! Lucas sequence is still better.

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.

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

And what's wrong with Courier font? Proportional fonts are a boon for coding.

um, is this java? i think i need a comment for a code in javascript, but ya ill make one dont worry 🙂

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;

awful way of ending that video 🙁

Why not explain Fibonacci using matrix exponentiation?

Recursive Fibonacci is the worst

… 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

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

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

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

Fizzbuzznacci

Ok, maybe this would have been the place to put 'Puff the Fractal Dragon', but it's a little late now.

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.

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.

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

But, is it a true spiral he made? It looks like circular arcs that approximate a spiral.

Can i buy lifetime of videos with this gentleman talking about algorithms. Please take my money