I already understood the basics of recursive functions in programming, but this explanation was really well done. This man makes programming beautiful!
Context is this situation,not all iteration uses!!! Syntacts is particular too this instance of a use of a method that is part of a topping logo ,Unknown or aligned,not Omni quotes of all code uses,you need Godel Bolle,which in this Time is semantically impossible too refine a study of?
I took computer science in high school and got a great teacher who really cared a lot about what she was teaching and understood what was important. She taught us recursion when most schools skipped this lesson (because it was not mandate to be taught by the ministry). When my prof in uni began the lecture about recursion I could hear the confusion in the room. Luckily, I had decent grasp of the concept before hand.
Best explanation of recursion. The key thing for me was the visualization of the stack, it helped me unlock everything, the key point is really understanding that whenever you enter the call the function inside of itself, it is being put inside of a call stack, waiting for the other calls, until it reaches the ending call, then allowing it to make its way back to the first call that was on the stack. Sorry for my english, it is not my main language !
Very good explanation. I feel these two parts are especially essential. 04:48 I can't get the answer, so I need to jump back to the equation. 05:47 Demonstrate with a stack diagram.
So many recursion explanations out there without a visual and straightforward demonstration of the stack calls, but this one is an amazing exception. Thank you Computerphile and Prof. Brailsford, this is a lifesaver!
I can always count on Computerphile as a perfect precursor to learning about a topic with their general, yet savvy and well formed explanations. Thank you
mind-blowned me completely... I've been trying to find a clear and brief explanation to recursion while avoiding the hour lecture and this by far was the best analog I've come across. I wish he was my professor
U?K sixties constant repeater of reason why 'they're tired billions of Eins ago,post punch card formation of not too ACT out Bletchlys Trump ten from WoodenHut tourist postcard ruling Govs war den Skoool system eddy race raiser obv?
to understand recursion first you need to understand recursion first you need to understand recursion first you need to understand recursion first you need to understand recursion first you need to understand recursion first you need.... exception fault, out of memory.
Wrong, defining recursion as recursion is a tail recursive statement, so in a language with tail call optimization it won't cause a stack overflow. It's just an infinite loop. If he had said: define recursion as printing hello world, wait one second, and return recursion, he'd have an infinite loop that printed hello world once per second for all eternity. ; )
I learned about recursion more than 25 years ago but it's still captivating listening to the Prof explaining how it works. One of the benefits of learning assembler languages is that you get to understand recursion and stacks pretty quickly because nothing is done for you.
I know my teacher expects us to already be familiar with the concept but this topic is very confusing for people whose brains don't work like computer scientists
He's such a nice man - laid back and reflective. I bet he's an excellent teacher. Lots of academics prefer to show how much they know, instead of trying to make sure people can learn as much as possible. Thank you Prof Brailsford.
I think recursion is one of those things that you either intuitively understand, or you'll have a great deal of trouble with... I can remember back in high school learning how to do a Quicksort in Pascal using recursion. The trick is to realize that every time you call the function, it's making a "copy" of itself. And that copy is completely unaware of the other "copies" of the function that have been called before. All that copy knows is that it was given some data on which it needs to do an operation and then return the results of that operation to whatever called it. It doesn't know that the thing that gave it the data was another copy of itself -- it doesn't need to know that. If, in the process of performing that operation, it needs to make another copy of the function, it will do so and wait for that copy to return whatever result it comes up with. And this can repeat over and over again until the computer runs out of memory (or stack-space, actually, since the stack is never 100% of the computer's memory.) Once you see it as copies making copies, ad infinitum, it's much easier to picture in your head. It's also easier to realize why you need something that will finally return an actual number instead of making another copy of the function -- without that final answer somewhere, you'd run out of memory quite quickly.
I feel like the meseeks in that one episode of Rick & Morty are a perfect representation of this. (Despite how it looks, this is not an intelligence related Rick & Morty joke)
Hey I would have loved if you discussed what the benefits of recursively programming are. I mean in this case, my first thought was to do a while loop and multiply. This video gave me a new idea but failed to discuss benefit of it over the iterative method.
You probably don't care anymore, but I'm here so I'm giving opinions. Recursion generally has worse efficiency than iteration, but in many cases makes the programmer's intent more obvious.
I love the programming community because all the comments always make everything easier to understand. This explanation in the video was excellent, but seeing the comments about "for understanding recursion, you must understand recursion" really made it clear. Thanks everyone.
2:12 OH MY GOD, the eureka moment. I never understood what was going on because people would say it's: factorial(4) *3 * 2 * 1 And I was thinking no... it's not. You're multiplying by a function, not the actual number. But how you've explained it makes sense finally! Thank you thank you, I can tick recursion off my avoid-at-all-costs list now.
Another excellent video!!! Years of understanding needed to create such a simple explanation. Always enlightening, listening to first-person recounts from "veterans" in the trenches at the beginning stages of the computer "war." Unique perspective. Thank you. One suggestion on your model: perhaps two rods might help visually. One rod is "the called func" while the 2nd rod is the stack. White 4! first is on rod 1, can't be evaluated, then is moved to Rod 2. It then calls the n-1, new white disk, on Rod 1 (which can't be solved either, yet, so it moves to wait on Rod 2 and now calls new n-2 White disk onto Rod 1) .... At 1!, it can be evaluated so that white disk is replaced with its Black finished version. Now 2! White disk (2x1!) can be moved back to Rod 1 and with the Black disk can now be evaluated into its Black finished version. And so on. To me, it helps ground the different "n" values/iterations to something. Just your coming up with the Rod visualization was 99% of the hard work. Once again, Thank you very much for making your videos.
Thank you for the clear description showing why recursion needs a stack. A lot of novice programmers have no idea that recursive functions build and use a forward stack that it has to unwind itself on the back way out. However, even today, stack sizes can be limited unless explicitly increased. For example, Linux's default stack is still not that big, but can be increased. Depending on how many steps of recursion is needed to resolve an answer and unless you plan ahead, you could end up running out of stack at the most inopportune time. Iterative routines don't need stack amounts like this, but may need a whole lot more code writing. It wasn't so much that recursion isn't helpful in writing far less amounts of code for some use cases, it's that it's much more difficult to gauge just how much stack a function might require. If you underestimate the stack needed, you're now knee deep into the bog of debugging.
Richard Smith No no no and again no. Did you not read this thread? Nothing, absolutely nothing, says that the second example has to cause a stack overflow. A compiler is free to output code that looks exactly the same as the first example. Please, this is a very basic thing and I'm not going to argue with you about it.
Jason Wilkins Not sure what compiler optimization has to do with anything. A train ride is not flying if sometimes your flight is grounded and you have to take a train... If the compiler does exactly what you tell it to, it will cause a stack overflow, because this is what endless recursion does. Any argument against that by adding layers of abstraction or correction is beside the point. If the compiler makes it iterative... well, its not recursive anymore is it? They are critically different in how exactly you are intending them to evaluate, getting the same answer is beside the point. Another analogy: If you were to say "I love my mom", autocorrect fixes it to"I make love to my mom" I can therefore assume this statement is the same as the one you were intending to make? Of course not, it changed it and no longer holds the same intention as the original. If you are doing something with the intention of it being recursive, then it being done on a stack is also implied. When it does not, then that specific language changed the intention of your code, which would very much be over zealous optimization, but it still is changing the intent of your original code.
FYI, the actual canonical end of the factorial is fractorial(0) = 1. If 0! is not defined, formulas break. I take it no Numberphile people were involved in the making of this video. ;)
Sir, just wanted to say thanks for this video. I swear when it comes to straight forwardness with engineering we miss the mark at times. This was a clear and concise explanation of recursion and what occurs in memory!
'Guy' is the word as example recalls memories of long ago(whether this bloke exsist said now or not)as was shown TH-cam videos of the when OunchCards were input for UK dis effect of constant WoodShed LIVE at live in sixths non repulsive soup ER fighter war den but of order or fake strong were King men non kid cowpoke gun launch emself top of telegraph pole as miss star Xmas red robe judge you all too be killed hat red Unknown hoo haha Philadelphia Cheese program of no chat with that loon out sussee fake not n border create outsiders of war back pub line daily red war non mushroom fakes trump ten bakes hang lines of no give in total gift off boss said no you,pays???!
I wish Professor Brailsford would have been my CS teacher. He certainly is a worthy man. Best explanation I've ever come across and Thank You Computerphile. Your content is always awesome.
This looks so much nicer in haskell fac 1 = 1 fac n = n * fac (n - 1) but of course, a much more idiomatic approach would be to just say fac n = product [1..n]
For some weird reason I can't see the replies to this comment, so sorry if someone already said the same thing. Not only does Haskell look nicer for these kind of things, but it also includes tail recursion optimisations, meaning no unnecessary stacking will be made.
Iteration is then web net cause algorithm riff err a? The=Quoter ,Java Oracle Main Frame X(25)Y bin light semantic rhythms syntactic,note key if C,knows?
This took my computer science teacher a month and a half to explain, and for me to fully understand. This video just did it in 10 minutes. Great video. I am sure people will find this useful.
Actually, a better way would be to make factorial(0) = 1, otherwise factorial(0) fails with a stack overflow. Also, you need to check n >= 0 or otherwise handle those exception cases. But, he is clearly just using this as an example. I just wanted to be clear that 0! = 1 is an important case that must be handled.
Of course, a real factorial function, given a negative number, should throw an exception, if it's imperative style, or return a special monadic value, such as Either, if it's functional.
An imperative language can also return an error number (a quite common practice even these days). Now, of course, if we wanted to implement a Roman factorial instead, then all integer values would be valid so long as the data type can handle them. Exceptions or other error handling methods can be used in the case where you also want to catch potential stack overflows before they occur and handle them (if implemented recursively) or to limit the range of the factorial to valid values. However, in general, overuse of exceptions, while quite popular these days, can lead to extremely inefficient code, which is often not feasible in practice. In most practical design it is better to leave exceptions for things that actually are exceptions and handle errors directly.
I love recursion cause it's great to use in algorithms and programming competitions but in the real world besides these premade functions like mergesort, quicksort, dfs, bfs, etc. is there any need to make one's own recursive algorithm?
Recursion is a neat way to handle path finding, which I would argue is a real world application. For instance you can query surrounding routes and have those routes query routes surrounding them and so on. Eventually when you're location is found it feeds itself back up the stack, tacking on a reference to each route object along the way. This is a terrible way to do path finding, and I can't remember the better way at the moment, but I do recall that I ended up using recursion either way. Some sort of recursive function feeding off of a location vector maybe, but with ordered priorities to check near before far.
Definitely. I'm working on a code editor with commands and I've used recursion several times to parse a string into an S-expression (think lisp). Really useful.
An example use for recursion is to navigate a directory tree including all subdirectories. For example, the total size of a directory is equal to the total size of all of the files and all of the subdirectories inside that directory. You can also use it to search for files, hash check all of the files inside a directory, etc. Some commonly used tools include grep, find, ls, du, rsync, cp, tar, etc. just for the example of filesystem navigation alone.
Hurrrrrrrrrrly I can tell if you are trolling. Nobody could honestly hold that opinion. If I was a hiring manager and heard you make that remark your resume would go into the trash incredibly fast.
Wow I was struggling with this for a few days but the visuals + commentary within 5:45 and onward pretty much just solidified the concept in my mind thank you so much!
In general, yes. There is a way to work around it, which isn't supported by all compilers. If you change your code so it looks more like fac(n) = go(1, n) go(a, n) = if (n == 1) then a else go(a*n, n-1) (which does the exact same thing), then some compilers can optimize out the tail call, and don't require a stack. Tail call means that in the recursive else clause, the outermost function you call is the recursive function itself. If you write fac(n) = n * fac(n-1) then the outermost function you call is *, so it doesn't work. But as you can see, we had to replace the stack with a second parameter in the recursive function.
Celrador Doubles go to 10^308, iirc, and long doubles almost 10^5k. unsigned long int go to 4.2b minimum, stored in 4 bytes. 18 quintillion for a long long (8 byte/64bit). 22! is 1.1e21 (110 quintillion) but is 10^9000 And with tail recursion, you can have infinite recursions, so yes. That is very likely the case.
Wow this is probably the most clear explanation of this that I have ever found and I've been struggling to wrap my brain around this practically (as opposed to conceptually - I've understood it more or less conceptually for a while) since High School, second year of computer science which was, not even joking, 2008. 10 years! And so many explanations of recursion I've found include this Towers of Hanoi style stack example but don't quite explain it in the very concise and clear way that you do here. I really really appreciate this and I honestly feel like a huge weight has been lifted from my shoulders.
I do not find recursion difficult to understand at all (maybe because I code in Python, which is very easy to understand). But in case you don't understand recursion by the way it was explained here is an easy example. Recursion is mostly used when a number is compounding on itself (exponential growth usually). So say we start with a single bacteria and this bacteria will double its population every hour. In order to find how many bacteria there would be on the 6th hour you would use recursion. Hour 1 = 1 bacteria Hour 2 = 2 bacteria (Hour 1*2) Hour 3 = 4 bacteria (Hour 2*2) Hour 4 = 8 bacteria (Hour 3*2) Hour 5 = 16 bacteria (Hour 4*2) Hour 6 = 32 bacteria (Hour 5*2) In order to find how many bacteria there would be on any given hour, you would take the previous term and multiply by 2.
Benjamin Tapia Explain the recursive implementation of solving Hanoi perfectly??? As a programmer, that definition is barely true true and the word 'mostly' is horribly wrong. REALLY REALLY REALLY REALLY wrong. It's used whenever an iterative is impossible(since most languages do recursive a bit slower) and bad using memoization(a lot of things in a single recursive call). But it's really much more fundamental than change a number.
Benjamin Tapia If you say you don't find recursion difficult, it's probably because you don't understand it very well. Also, your explanation is wrong. Better not spread incorrect explanations like this online. Actually, better not spread any explanation of any technical subject unless you have a PhD or at least a Master's degree in that or a related subject.
This is a great way of explaining how factorials actually work! This concept is often times tough to understand when first learning about the recursion. It's great to see how much more efficient recursion can be.
Dig a hole,beware,the Christian come two tea cheer you up an you will yell 'o,you made me talk I've been down this hole for billions of Eins for no utter known reason produce or worth work non known riding bicycles round the hole is not re curses pyramid is over there..)Eh? Python MonTeas..
Good example of why software is so buggy the example assumes the function will not be passed a negative number, which could lock up the computer until the stack overflows
***** I don't agree with tzkelley in that I don't think it's bad design to not check, because it's legitimate to have it fail if you pass in the wrong answer. But I disagree with you String.Epsilon, you're on the opposite side of it. Who says you shouldn't check in the operation? It's common practice I agree, but not necessarily correct. What's wrong with say checking, and throwing an exception or something... so as to keep from the stack overflowing. You still have the error, but you don't choke on it in the process.
It really depends on the specific operation and the application you're using it for. In this case, it's simply an example to show how recursion works, so it's entirely reasonable to avoid unnecessary distractions like error checking and just assume that the input is valid. In some other cases, you might be using your factorial function as part of some other larger program and already KNOW that the function which is calling factorial will only so do with a positive integer(such a function which counted the number of items in some other set) and therefore not need to check for that again. In most cases though, you would want to include some sort of error checking in the function itself so that the code can be more easily reused elsewhere rather than having to rewrite that error checking code separately for each time you want to use it. For something as trivial as a factorial function, this may not be much of an issue, but for more complicated functions, it might. Also, the base case used in the video is technically wrong. It should be defining 0! = 1, not 1!
James Coyle - agreed ***** - yes, you prefer it. My point for posting was because you phrased your statement not as how you prefer it, but as how it should be done.
Hey what's the deal about your background? I translated some to text, It's: T¬$ªdƒ¯•+ It doesn't seem so random tho, as the pattern of &#, 3-Digit number, ; appears all throughout. Plz answer
שגיא קרמן If there is any meaning, it might rely on translating the other text which might provide formatting clues or necessary context. My guess is that they converted a HTML entity table into binary. I get that from the proximity of 172, 170 and 175, but it could just be random html entities converted to binary for the lulz. Difficult to say on the small sample we have I guess.
שגיא קרמן I hate to spoil your fun but when this was originally designed I was short of time so I simply leaned and tapped on the keyboard and probably because I'm a drummer that's could be why there are similar patterns in it (I did also do some cut & paste of the output of my leanings) -> having said that, there is a background on one film which was created from scratch, and you may have more fun looking for that one as I don't think anyone has spotted the message(s) yet.... the clue is that it was created from scratch for the film >Sean
You sir are the man! I now fully understand recursion :) I've been trying to learn this for ages. Thank you so much for this straight forward and clear explanation.
I understood this when I was 16 years old, working in DOS 3.0... it's really not as difficult as described... but I understand why he did it the way he did.
lErssikeke lol! Programming in general can make potholes in your brain. I've had WTF moments with my own code i.e. not understanding my own legacy code.
The problem is you NEED to know it. If, for example, I ask you to make a calculator, how will you teach it the order of operations? (Exponentiation > Multiplication & Division > Addition and Subtraction). You will need to use a parser, which is a type of recursive function. Another example: I ask you to make an AI for tic tac toe. You'll need to use minimax: A recursive algorithm.
One technical issue that isn't quite made clear is that it does depend on the implementation of the computer language being defined. C has it specified that all calls to a function have to have their own stack frame, so that's why it works. In a language (like a primitive microcomputer Basic, for instance) might not have this specification, so that when the function is called recursively, the language only operates a single execution of the function. The function does get called repeatedly as it goes down the values, but after the bottom one returns its "1", it drops out to nothing because each call that contained the previous call, doesn't exist any more. Each n got wiped out by a new version of n. Of course, this really isn't a problem any more, but it's a thing to remember in any new language design and specification. Like a Javascript engine in a new browser.
That's the calmest explanation I've ever seen. He's explaining 'factorial', but it sounds like: The world is not coming to an end; all will be well; verdant ever after.
Why easy spy skitso read your mind invade dark side copywrited you out send you back too work no known uses,beeeznest of livers supported by you will now get rid of techno as roosters spy act invade live off you in great common agreements,get too work,pays?
4:52 The sound a compiler makes when executing a recursion call.
lol'd a little harder than I should've
I'm laughing at this for 2 straight minutes now
HAHAHA
Except that compiler doesn't perform recursive calls due to some recursive code it's compiling.
I just learned about this and I read this comment and was like "only lvl 2 monkey brain can understand why this joke is so funny"
This is the clearest explanation I came across! Thanks so much! 👏
^ came here to say the same thing: This was the only video I found that was concise. I think a number of other videos missed the linking finale of it.
i felt the same
same here
When there is a need to use recursion???
@@frankynakamoto2308 Prolog makes use of recursion extensively
I'm sad you didn't put a link to this video in the description.
DES(ooo,Sad,wait 4 that nit,Nat,nag)
finally someone understood recursion.
Exept its a different video 1 second shorter
@@Xnoob545 haha
??
Honestly speaking, this is the best recursion explanation I've ever heard.
false.
I already understood the basics of recursive functions in programming, but this explanation was really well done. This man makes programming beautiful!
Yep
Context is this situation,not all iteration uses!!! Syntacts is particular too this instance of a use of a method that is part of a topping logo ,Unknown or aligned,not Omni quotes of all code uses,you need Godel Bolle,which in this Time is semantically impossible too refine a study of?
mr neural network?@@stevebez2767
false.
Google "recursion"... did you mean "recursion"?
seems like google has got a bug
LOL
It's not a bug. It was done intentionally by Google because of what recursion means.
lol as if this subject wasn't confusing enough google makes a joke and makes it more confusing in the process.
Awe didn't work. Would've been funny!
I took computer science in high school and got a great teacher who really cared a lot about what she was teaching and understood what was important. She taught us recursion when most schools skipped this lesson (because it was not mandate to be taught by the ministry). When my prof in uni began the lecture about recursion I could hear the confusion in the room. Luckily, I had decent grasp of the concept before hand.
ok?
*Thank you! Well explained!!!*
??
This is like the best recursion explanation of all time.
false.
Best explanation of recursion. The key thing for me was the visualization of the stack, it helped me unlock everything, the key point is really understanding that whenever you enter the call the function inside of itself, it is being put inside of a call stack, waiting for the other calls, until it reaches the ending call, then allowing it to make its way back to the first call that was on the stack. Sorry for my english, it is not my main language !
Very good explanation. I feel these two parts are especially essential.
04:48 I can't get the answer, so I need to jump back to the equation.
05:47 Demonstrate with a stack diagram.
??
So many recursion explanations out there without a visual and straightforward demonstration of the stack calls, but this one is an amazing exception. Thank you Computerphile and Prof. Brailsford, this is a lifesaver!
It's always exciting to discover a professor that can actually teach. Great intro to recursion.
this is literally the best explanation of recursion I've seen yet. everyone seems to miss that critical part (pending multiply). thanks for this gem.
I really wish these videos were out when I was learning programming at uni. This is such a concise explanation. Thankyou!
Where in life are you right now ?
Reviewing this concept a year later, Prof Barilsford's teaching style is still really one of the best
I can always count on Computerphile as a perfect precursor to learning about a topic with their general, yet savvy and well formed explanations. Thank you
??
@@Triantalex how am I supposed to know what I meant 5 years go
I must say, I now wish that you were a professor at my university. The simplicity and explanation is flawless. Thank you.
Great explanation made by a true master.
This is by far the best explanation in youtube as to how recursion works. This recursion-thing is tricky.
Recursion; (noun) see: Recursion
??
@@Triantalex you clearly don't get it. I suggest you Google recursion
This is the most comprehensive illustration of Factorial I've ever seen.. brilliant, simple, elegant. Thank you!!!
This fellow deserves to be called an "educator".
??
mind-blowned me completely... I've been trying to find a clear and brief explanation to recursion while avoiding the hour lecture and this by far was the best analog I've come across. I wish he was my professor
I personally wouldn't trust the Comic Sans n to return the correct value.
kek
Personalities Few Char RISC tick tick interrupted read turns?
??
This explanation on recursion is the best I've seen. Using the stack and using each disk as a stackframe drove it home for me. I am an in awe.
Why can't you be my teacher.... for EVERYTHING
tried that and even wished it to Santa and it didn't happen.
+Reclaimer Halo 3 :D
U?K sixties constant repeater of reason why 'they're tired billions of Eins ago,post punch card formation of not too ACT out Bletchlys Trump ten from WoodenHut tourist postcard ruling Govs war den Skoool system eddy race raiser obv?
Even the dirty things in life?
@@MsJavaWolf no such things has dirty
This is the best-explained recursion ever. Thank you so much for making these videos available to the public. Hope you stay safe and well.
to understand recursion first you need to understand recursion first you need to understand recursion first you need to understand recursion first you need to understand recursion first you need to understand recursion first you need....
exception fault, out of memory.
Test your 0 statement better, jeez. Are you even qualified to use recursion? lol
Wrong, defining recursion as recursion is a tail recursive statement, so in a language with tail call optimization it won't cause a stack overflow. It's just an infinite loop.
If he had said: define recursion as printing hello world, wait one second, and return recursion, he'd have an infinite loop that printed hello world once per second for all eternity. ; )
7thChosen Segmentation fault, stack ran into the heap. ( ⚆ ͜ʖ ⚆)
@Prismic Kyubey hey hey, watch your mouth! there are kids here... lawlz
There's no base case, RIP
you've explained the concept really beautifully and elegantly. totally in love
I learned about recursion more than 25 years ago but it's still captivating listening to the Prof explaining how it works. One of the benefits of learning assembler languages is that you get to understand recursion and stacks pretty quickly because nothing is done for you.
ok?
Incredibly well and thoughtfully explained, with plenty of visual aid to better understand the concept. Many thanks!
Very helpful and useful for my CS class. Thanks a lot, a really informative video.
I know my teacher expects us to already be familiar with the concept but this topic is very confusing for people whose brains don't work like computer scientists
He's such a nice man - laid back and reflective. I bet he's an excellent teacher. Lots of academics prefer to show how much they know, instead of trying to make sure people can learn as much as possible. Thank you Prof Brailsford.
I really liked how the stack was explained as "people" waiting for other person to do their job
I think recursion is one of those things that you either intuitively understand, or you'll have a great deal of trouble with... I can remember back in high school learning how to do a Quicksort in Pascal using recursion.
The trick is to realize that every time you call the function, it's making a "copy" of itself. And that copy is completely unaware of the other "copies" of the function that have been called before. All that copy knows is that it was given some data on which it needs to do an operation and then return the results of that operation to whatever called it. It doesn't know that the thing that gave it the data was another copy of itself -- it doesn't need to know that. If, in the process of performing that operation, it needs to make another copy of the function, it will do so and wait for that copy to return whatever result it comes up with. And this can repeat over and over again until the computer runs out of memory (or stack-space, actually, since the stack is never 100% of the computer's memory.)
Once you see it as copies making copies, ad infinitum, it's much easier to picture in your head. It's also easier to realize why you need something that will finally return an actual number instead of making another copy of the function -- without that final answer somewhere, you'd run out of memory quite quickly.
I feel like the meseeks in that one episode of Rick & Morty are a perfect representation of this. (Despite how it looks, this is not an intelligence related Rick & Morty joke)
Wow, I think your actually pretty right.
I am wowed. I've fallen in love with Computerphile with this one video! This was as clear as day!
Hey I would have loved if you discussed what the benefits of recursively programming are. I mean in this case, my first thought was to do a while loop and multiply. This video gave me a new idea but failed to discuss benefit of it over the iterative method.
You probably don't care anymore, but I'm here so I'm giving opinions. Recursion generally has worse efficiency than iteration, but in many cases makes the programmer's intent more obvious.
I love the programming community because all the comments always make everything easier to understand. This explanation in the video was excellent, but seeing the comments about "for understanding recursion, you must understand recursion" really made it clear. Thanks everyone.
2:12 OH MY GOD, the eureka moment. I never understood what was going on because people would say it's:
factorial(4) *3 * 2 * 1
And I was thinking no... it's not. You're multiplying by a function, not the actual number. But how you've explained it makes sense finally! Thank you thank you, I can tick recursion off my avoid-at-all-costs list now.
cool :D
f(x) is a function (i.e., a rule for choosing the right number), whereas f(any specific x that someone chooses) is a number chosen using the function.
??
Another excellent video!!! Years of understanding needed to create such a simple explanation. Always enlightening, listening to first-person recounts from "veterans" in the trenches at the beginning stages of the computer "war." Unique perspective. Thank you.
One suggestion on your model: perhaps two rods might help visually. One rod is "the called func" while the 2nd rod is the stack.
White 4! first is on rod 1, can't be evaluated, then is moved to Rod 2. It then calls the n-1, new white disk, on Rod 1 (which can't be solved either, yet, so it moves to wait on Rod 2 and now calls new n-2 White disk onto Rod 1) ....
At 1!, it can be evaluated so that white disk is replaced with its Black finished version. Now 2! White disk (2x1!) can be moved back to Rod 1 and with the Black disk can now be evaluated into its Black finished version. And so on.
To me, it helps ground the different "n" values/iterations to something.
Just your coming up with the Rod visualization was 99% of the hard work.
Once again, Thank you very much for making your videos.
This is such a simple and to-the-point explanation.
??
Thank you for the clear description showing why recursion needs a stack. A lot of novice programmers have no idea that recursive functions build and use a forward stack that it has to unwind itself on the back way out. However, even today, stack sizes can be limited unless explicitly increased. For example, Linux's default stack is still not that big, but can be increased. Depending on how many steps of recursion is needed to resolve an answer and unless you plan ahead, you could end up running out of stack at the most inopportune time. Iterative routines don't need stack amounts like this, but may need a whole lot more code writing. It wasn't so much that recursion isn't helpful in writing far less amounts of code for some use cases, it's that it's much more difficult to gauge just how much stack a function might require. If you underestimate the stack needed, you're now knee deep into the bog of debugging.
So basically recursion is when a function calls itself.
Yes..like in those mandelbrot pattern, the basic equation for those is z = z2 + c, iterated a specified number of times.
Jason Wilkins iteration is not recursion. It is the same only in the way you evaluate it in your mind. For example...
while(true);
Richard Smith No no no and again no. Did you not read this thread? Nothing, absolutely nothing, says that the second example has to cause a stack overflow. A compiler is free to output code that looks exactly the same as the first example. Please, this is a very basic thing and I'm not going to argue with you about it.
Jason Wilkins Not sure what compiler optimization has to do with anything. A train ride is not flying if sometimes your flight is grounded and you have to take a train...
If the compiler does exactly what you tell it to, it will cause a stack overflow, because this is what endless recursion does. Any argument against that by adding layers of abstraction or correction is beside the point. If the compiler makes it iterative... well, its not recursive anymore is it? They are critically different in how exactly you are intending them to evaluate, getting the same answer is beside the point.
Another analogy:
If you were to say "I love my mom", autocorrect fixes it to"I make love to my mom" I can therefore assume this statement is the same as the one you were intending to make? Of course not, it changed it and no longer holds the same intention as the original. If you are doing something with the intention of it being recursive, then it being done on a stack is also implied. When it does not, then that specific language changed the intention of your code, which would very much be over zealous optimization, but it still is changing the intent of your original code.
I didn't say anything about compiler optimization.
The best video to explain recursion I found on TH-cam. Thank you!
Short answer: Recursion is the _best thing ever._
Professor Brailsford's knowledge and ability to explain concepts is phenomenal.
4:52 thought that he was about to kick the bucket lol
Thank you Professor Brailsford - for such an elegant explanation and also to the videographer for filming the video.
FYI, the actual canonical end of the factorial is fractorial(0) = 1. If 0! is not defined, formulas break. I take it no Numberphile people were involved in the making of this video. ;)
Fair point.
Sir, just wanted to say thanks for this video. I swear when it comes to straight forwardness with engineering we miss the mark at times. This was a clear and concise explanation of recursion and what occurs in memory!
my dream is to be as good as this guy
'Guy' is the word as example recalls memories of long ago(whether this bloke exsist said now or not)as was shown TH-cam videos of the when OunchCards were input for UK dis effect of constant WoodShed LIVE at live in sixths non repulsive soup ER fighter war den but of order or fake strong were King men non kid cowpoke gun launch emself top of telegraph pole as miss star Xmas red robe judge you all too be killed hat red Unknown hoo haha Philadelphia Cheese program of no chat with that loon out sussee fake not n border create outsiders of war back pub line daily red war non mushroom fakes trump ten bakes hang lines of no give in total gift off boss said no you,pays???!
Youbhave to be surpass him and make other people wanting to be like you. Than you reached what this man reached an more!
??
4 years later..... Still the best one on youtube!!!
This is hands the most straight forward explanation of recursion in the universe 😐
false.
I wish Professor Brailsford would have been my CS teacher. He certainly is a worthy man. Best explanation I've ever come across and Thank You Computerphile. Your content is always awesome.
This looks so much nicer in haskell
fac 1 = 1
fac n = n * fac (n - 1)
but of course, a much more idiomatic approach would be to just say
fac n = product [1..n]
For some weird reason I can't see the replies to this comment, so sorry if someone already said the same thing.
Not only does Haskell look nicer for these kind of things, but it also includes tail recursion optimisations, meaning no unnecessary stacking will be made.
Iteration is then web net cause algorithm riff err a? The=Quoter ,Java Oracle Main Frame X(25)Y bin light semantic rhythms syntactic,note key if C,knows?
false.
This took my computer science teacher a month and a half to explain, and for me to fully understand. This video just did it in 10 minutes. Great video. I am sure people will find this useful.
Actually, a better way would be to make factorial(0) = 1, otherwise factorial(0) fails with a stack overflow. Also, you need to check n >= 0 or otherwise handle those exception cases. But, he is clearly just using this as an example. I just wanted to be clear that 0! = 1 is an important case that must be handled.
Of course, a real factorial function, given a negative number, should throw an exception, if it's imperative style, or return a special monadic value, such as Either, if it's functional.
An imperative language can also return an error number (a quite common practice even these days). Now, of course, if we wanted to implement a Roman factorial instead, then all integer values would be valid so long as the data type can handle them. Exceptions or other error handling methods can be used in the case where you also want to catch potential stack overflows before they occur and handle them (if implemented recursively) or to limit the range of the factorial to valid values. However, in general, overuse of exceptions, while quite popular these days, can lead to extremely inefficient code, which is often not feasible in practice. In most practical design it is better to leave exceptions for things that actually are exceptions and handle errors directly.
what's the complexity of the function *factorial* ? n or 2n-1 ?
this is undoubtedly the best explanation video i have ever watched on youtube
I love recursion cause it's great to use in algorithms and programming competitions but in the real world besides these premade functions like mergesort, quicksort, dfs, bfs, etc. is there any need to make one's own recursive algorithm?
Recursion is a neat way to handle path finding, which I would argue is a real world application. For instance you can query surrounding routes and have those routes query routes surrounding them and so on. Eventually when you're location is found it feeds itself back up the stack, tacking on a reference to each route object along the way. This is a terrible way to do path finding, and I can't remember the better way at the moment, but I do recall that I ended up using recursion either way. Some sort of recursive function feeding off of a location vector maybe, but with ordered priorities to check near before far.
Of course. Any kind of parsing is recursive. Any kind of structure that can contain similar copies if itself (like HTML) requires recursion.
Definitely. I'm working on a code editor with commands and I've used recursion several times to parse a string into an S-expression (think lisp). Really useful.
An example use for recursion is to navigate a directory tree including all subdirectories. For example, the total size of a directory is equal to the total size of all of the files and all of the subdirectories inside that directory. You can also use it to search for files, hash check all of the files inside a directory, etc. Some commonly used tools include grep, find, ls, du, rsync, cp, tar, etc. just for the example of filesystem navigation alone.
Hurrrrrrrrrrly I can tell if you are trolling. Nobody could honestly hold that opinion. If I was a hiring manager and heard you make that remark your resume would go into the trash incredibly fast.
Wow I was struggling with this for a few days but the visuals + commentary within 5:45 and onward pretty much just solidified the concept in my mind thank you so much!
The professor has an ASMR-ish voice, close Bob Ross's. 💞
Watching your videos is such an easy way to learn English (both as programming), thank you guys!
Don't you get a stack overflow if you do this with a number to big though?
In general, yes.
There is a way to work around it, which isn't supported by all compilers. If you change your code so it looks more like
fac(n) = go(1, n)
go(a, n) = if (n == 1) then a else go(a*n, n-1)
(which does the exact same thing), then some compilers can optimize out the tail call, and don't require a stack. Tail call means that in the recursive else clause, the outermost function you call is the recursive function itself. If you write
fac(n) = n * fac(n-1)
then the outermost function you call is *, so it doesn't work.
But as you can see, we had to replace the stack with a second parameter in the recursive function.
yeah, but you can avoid that with tail calls
You'd hit problems with the number being too large before you hit stack overflow.
***** I wonder, if that also is the case for a long double. :o
Can't be arsed to research and calculate that now, though.
Celrador Doubles go to 10^308, iirc, and long doubles almost 10^5k. unsigned long int go to 4.2b minimum, stored in 4 bytes. 18 quintillion for a long long (8 byte/64bit).
22! is 1.1e21 (110 quintillion) but is 10^9000
And with tail recursion, you can have infinite recursions, so yes. That is very likely the case.
I just love this guys voice, Very soothing.
What would recursion be without a stack!
A: tail recursion
RedHat,Linux lie Nukes?
Wow this is probably the most clear explanation of this that I have ever found and I've been struggling to wrap my brain around this practically (as opposed to conceptually - I've understood it more or less conceptually for a while) since High School, second year of computer science which was, not even joking, 2008. 10 years! And so many explanations of recursion I've found include this Towers of Hanoi style stack example but don't quite explain it in the very concise and clear way that you do here. I really really appreciate this and I honestly feel like a huge weight has been lifted from my shoulders.
4:52 :)
Ah
This is the clearest explanation I've experienced. I always understood the calls, but this made the returns as simple as can be. Thank you.
The base case for factorial is actually 0! = 1
I was looking for this comment to see if anyone else caught that
Yes, but it really has no purpose in code.
I finally found someone he's thinking like me 💛
@@Mikey_in_Japan Me too :D
@@ivana4638 It certainly has.
Best recursion explanation,I have ever seen.Thanks @Computerphile for this video.
I do not find recursion difficult to understand at all (maybe because I code in Python, which is very easy to understand). But in case you don't understand recursion by the way it was explained here is an easy example.
Recursion is mostly used when a number is compounding on itself (exponential growth usually). So say we start with a single bacteria and this bacteria will double its population every hour. In order to find how many bacteria there would be on the 6th hour you would use recursion.
Hour 1 = 1 bacteria
Hour 2 = 2 bacteria (Hour 1*2)
Hour 3 = 4 bacteria (Hour 2*2)
Hour 4 = 8 bacteria (Hour 3*2)
Hour 5 = 16 bacteria (Hour 4*2)
Hour 6 = 32 bacteria (Hour 5*2)
In order to find how many bacteria there would be on any given hour, you would take the previous term and multiply by 2.
Well that's unnecessary in your example.
_Hour _*_x_*_ = 2(Hour _*_x_*_ - 1)_
Tommy59375 Both ways are great explanations.
Great explanation.
Benjamin Tapia
Explain the recursive implementation of solving Hanoi perfectly???
As a programmer, that definition is barely true true and the word 'mostly' is horribly wrong. REALLY REALLY REALLY REALLY wrong. It's used whenever an iterative is impossible(since most languages do recursive a bit slower) and bad using memoization(a lot of things in a single recursive call). But it's really much more fundamental than change a number.
Benjamin Tapia If you say you don't find recursion difficult, it's probably because you don't understand it very well.
Also, your explanation is wrong. Better not spread incorrect explanations like this online. Actually, better not spread any explanation of any technical subject unless you have a PhD or at least a Master's degree in that or a related subject.
This is a great way of explaining how factorials actually work! This concept is often times tough to understand when first learning about the recursion. It's great to see how much more efficient recursion can be.
Where can I learn to code with a marker and piece of paper
BorisMediaProds Make up your own pseudo-code or use existing pseudo-code and you're done!
Flumpanor I was making a joke lol
BorisMediaProds I wasn't xD
Flumpanor ah hahaha! [cheesy 80's music plays]
Dig a hole,beware,the Christian come two tea cheer you up an you will yell 'o,you made me talk I've been down this hole for billions of Eins for no utter known reason produce or worth work non known riding bicycles round the hole is not re curses pyramid is over there..)Eh? Python MonTeas..
Fantastic explanation. I really wanted to understand how a programming language dealt with recursion and this channel nailed it.
Good example of why software is so buggy the example assumes the function will not be passed a negative number, which could lock up the computer until the stack overflows
*****
I don't agree with tzkelley in that I don't think it's bad design to not check, because it's legitimate to have it fail if you pass in the wrong answer.
But I disagree with you String.Epsilon, you're on the opposite side of it. Who says you shouldn't check in the operation? It's common practice I agree, but not necessarily correct.
What's wrong with say checking, and throwing an exception or something... so as to keep from the stack overflowing. You still have the error, but you don't choke on it in the process.
It really depends on the specific operation and the application you're using it for. In this case, it's simply an example to show how recursion works, so it's entirely reasonable to avoid unnecessary distractions like error checking and just assume that the input is valid. In some other cases, you might be using your factorial function as part of some other larger program and already KNOW that the function which is calling factorial will only so do with a positive integer(such a function which counted the number of items in some other set) and therefore not need to check for that again.
In most cases though, you would want to include some sort of error checking in the function itself so that the code can be more easily reused elsewhere rather than having to rewrite that error checking code separately for each time you want to use it. For something as trivial as a factorial function, this may not be much of an issue, but for more complicated functions, it might.
Also, the base case used in the video is technically wrong. It should be defining 0! = 1, not 1!
Any competent programmer would handle that. The code here is simplified so it is easier for non-programmers to understand.
lordofduct It should be handled by throwing an out of range exception rather than letting the code execute until it fails.
James Coyle - agreed
***** - yes, you prefer it. My point for posting was because you phrased your statement not as how you prefer it, but as how it should be done.
5 years later and this is still the best explanation ever. Understand the stack is a key fundamental.
Hey what's the deal about your background? I translated some to text, It's:
T¬$ªdƒ¯•+
It doesn't seem so random tho, as the pattern of &#, 3-Digit number, ; appears all throughout.
Plz answer
שגיא קרמן Illuminati confirmed!
שגיא קרמן T¬?$ªdƒ¯•+
mod prime I know now but what do they mean?
שגיא קרמן If there is any meaning, it might rely on translating the other text which might provide formatting clues or necessary context. My guess is that they converted a HTML entity table into binary. I get that from the proximity of 172, 170 and 175, but it could just be random html entities converted to binary for the lulz. Difficult to say on the small sample we have I guess.
שגיא קרמן I hate to spoil your fun but when this was originally designed I was short of time so I simply leaned and tapped on the keyboard and probably because I'm a drummer that's could be why there are similar patterns in it (I did also do some cut & paste of the output of my leanings)
-> having said that, there is a background on one film which was created from scratch, and you may have more fun looking for that one as I don't think anyone has spotted the message(s) yet.... the clue is that it was created from scratch for the film >Sean
One of the best teachers I’ve ever seen. Well done
Make a video about net neutrality.
??
You sir are the man! I now fully understand recursion :) I've been trying to learn this for ages. Thank you so much for this straight forward and clear explanation.
I understood this when I was 16 years old, working in DOS 3.0... it's really not as difficult as described... but I understand why he did it the way he did.
This professor is very talented, his explanations are clear as crystal
recursion:
see recursion
??
Professor Brailsford is an excellent teacher, especially like the visual explanation toward the end of the video.
recursion is a whole disgusting evil thing you never want to touch it will only end in tears
too late.
I heard it doesn't make sense until a while after you learn it, then it clicks. Don't give up just because something's hard
lErssikeke lol! Programming in general can make potholes in your brain. I've had WTF moments with my own code i.e. not understanding my own legacy code.
noooo it's awsome ! you just need to be friends with it
The problem is you NEED to know it. If, for example, I ask you to make a calculator, how will you teach it the order of operations? (Exponentiation > Multiplication & Division > Addition and Subtraction). You will need to use a parser, which is a type of recursive function.
Another example: I ask you to make an AI for tic tac toe. You'll need to use minimax: A recursive algorithm.
One technical issue that isn't quite made clear is that it does depend on the implementation of the computer language being defined. C has it specified that all calls to a function have to have their own stack frame, so that's why it works. In a language (like a primitive microcomputer Basic, for instance) might not have this specification, so that when the function is called recursively, the language only operates a single execution of the function. The function does get called repeatedly as it goes down the values, but after the bottom one returns its "1", it drops out to nothing because each call that contained the previous call, doesn't exist any more. Each n got wiped out by a new version of n. Of course, this really isn't a problem any more, but it's a thing to remember in any new language design and specification. Like a Javascript engine in a new browser.
I half-expected this to be a 10-minute video of him just repeating "recursion is recursion is recursion is...".
So clear explanation, I haven't even learned trees & graphs but I already understood the basics of recursion thanks to computerphile!!
Recursion can only be understood if you understand what recursion is.
That's the calmest explanation I've ever seen. He's explaining 'factorial', but it sounds like: The world is not coming to an end; all will be well; verdant ever after.
to understand what recusion is, you must first understand recursion.
These explainations are amazing, thank you so much Computerphile team ❤️
Recursion isn't hard at all, it's pretty simple.
tabularasa0606 *Triggered*
No, removed comments. Also necro-post
tabularasa0606 I was joking that I was triggered lel
it seems recursion is factorial, factorial is recursion;)
Why easy spy skitso read your mind invade dark side copywrited you out send you back too work no known uses,beeeznest of livers supported by you will now get rid of techno as roosters spy act invade live off you in great common agreements,get too work,pays?
Hands down the best explanation I have ever seen on recursion. Great vid.
Now time to explain how to make a computer do it iteratively? :D
??
This, right here, is hands down the best and clear explanation of recursion on internet.
i dont like recursion when programming, gets out of control way too fast. i prefer cycles, far more reliable.
What are "cycles"?
As under control ,do you view presidents on TV?
Of course. Recursive definitions are for a better understanding. In code however they may lead to a horrible runtime and memory usage.
??
Best recursion explanation ive seen online. Well done, subscribed!