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!
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!
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.
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 :)
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]
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!
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
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!
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.
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!
***** Theres are quite a few proofs of this formula, I can think of 3 off the top of my head. It works perfectly fine and can cumpute any nth fib number (the golden ratio isnt anything special to do with the fib numbers by the way, check out the brady numbers numberphile video)
That is not only incorrect, its a classic example of a wrong algorithm in many algorithms first lessons in Universities. You simply can not store Square root of 5 in a machine with finite amount of memory. Even tho the formula is correct It is not a correct algorithm.
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.
This desn't improve the overall computational complexity however. The number of calls is still proportional to r raised to the power of n, where r is the Golden Ratio. There is a way to calculate Fibonacci in linear time. See www.geeksforgeeks.org/dynamic-programming-set-1/
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
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').
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
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()
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
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.
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 :D
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.
... 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
I wrote a recursive program in c++ to find the Fibonacci sequence at varying steps and included the number of iterations of the function it take to get from one member of the set to the next.... The first, like, ten members took a couple hundred iterations each. It ground to a near halt around the 50th member of the sequence... That's because it took 25 billion iterations of fib() to get from the 49th to the 50th member... 😳... If anyone wants the code, I'll gladly paste it.
Here's an example. it calculates the first 93 Fibonacci numbers almost instantly (caching previous values for performance).. Incidentally, 'theAnswer' = 12200160415121876738. I'll leave you to check manually if it is correct.numeric overflow started occurring just after 93 on my 64-bit PC. using System.Collections.Generic; namespace Fibbers { class Program { private static Dictionary _fibs = new Dictionary(); static void Main(string[] args) { _fibs.Add(1UL, 1UL); _fibs.Add(2UL, 1UL); ulong theAnswer = Fib(93); } private static ulong Fib(ulong i) { if (_fibs.ContainsKey(i)) return _fibs[i]; _fibs.Add(i, Fib(i - 1) + Fib(i - 2)); return _fibs[i]; } } }
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.
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.
Some clever languages like Haskell let you define an operator that automatically memoizes (i.e. stores prior results in a list) for any function, which is a top down approach.
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.
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?
10 лет назад
Y sigo teniendo demostraciones de que mi tatto es un EXCELENTE Y MUY BIEN ELEGIDO TATTO algo de lo que nunca me arrepentiré
Saying the Fibonacci sequence is recursive is a little misleading. That is, on a Turing machine, the operation would be fine, but in reality, when you get up to the 50th or so number, it begins to call the function far too many times, looking for answers it's already computed an upteenth number of times. I believe it's an O(n^n) function. By storing results in an array, you can decrease the running time to O(1), which is so infinitely better. It's the difference between a microprocessor and a supercomputer.
It being recursive has nothing to do with the capabilities of computers, but with how it is defined. Also it can easily be calculated in linear time. O(1) can only be achieved, if the array is filled beforehand or if you use the formula (((1+sqrt(5))/2)^n+((1-sqrt(5))/2)^n)/sqrt(5). Edit: The other answers weren't shown to me before oO
I think the answer is in maths. As Fibonacci sequence is a recurrent sequence of order 2 you can in fact simplify it's expression by something which looks like Un = A.(r1)^n + B.(r2)^n ; r1,r2 being the roots of the r^2=r+1 equation(fibonacci recurrence definition) which is r^2-r-1=0. A and B are factors that depends on the initial values of the sequence. Here U(0)=1 and U(1)=1. It is in fact similar to solving a differential equation in the end.
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.
Someone could say me if there's a reproduction list about recursion or the videos that talk about it? I'm doing an important work about it to enter for the university and it would be useful
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.
"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."
I think a small error slipped into this video. You can write every recursive function without using recursion. However for some functions simple for-loops are not powerful enough. Simple for-loops meaning, that they can only loop a finite number of times.
I'm not sure for all languages, but you can't do recursion forever either. Python for instance will return RuntimeError: maximum recursion depth exceeded after 995 recursions.
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.
Thanks, I think I got it. Basically every time a recursion goes one level down it creates a stack frame with it's own local variables and waiting for a return.
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
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. jsfiddle.net/syntaxerrorforbearer/yjjbxhve/ - optimized (not using the stack), and 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.
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.
Yeah, I was surprised he didn't even talk about that. By the way, strictly speaking it's more the breadth of the recursion than its depth that's the issue here
Got a little programing challenge for anyone interested. You have to find a way to swap the values of two integers. Sounds simple doesn't, But the catch is you can't use a third temporary integr.
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.
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?)
why is it not f(1)=2 f(2)=-1? that would create the same aswell 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21... see the problem? there are infinitely many possible starting points, the inventor just wanted them to be 1,1
