What on Earth is Recursion? - Computerphile
Audible Free Book: www.audible.com/computerphile
Recursion; like something from the film "Inception". Even Professor Brailsford says it can be hard to get your head around - watch him make it much easier to understand...
EXTRA BITS: • EXTRA BITS: Recursion ...
Opening up the Original Mac: • Opening up the 30yr ol...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradychannels
Пікірлер: 1 300
4:52 The sound a compiler makes when executing a recursion call.
@Newborn228
7 жыл бұрын
lol'd a little harder than I should've
@norbertmarko6479
4 жыл бұрын
I'm laughing at this for 2 straight minutes now
@ChunkyChest
4 жыл бұрын
HAHAHA
@yashsvidixit7169
4 жыл бұрын
Except that compiler doesn't perform recursive calls due to some recursive code it's compiling.
@davidflores1645
4 жыл бұрын
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"
I'm sad you didn't put a link to this video in the description.
@stevebez2767
6 жыл бұрын
DES(ooo,Sad,wait 4 that nit,Nat,nag)
@aloktiwari2732
4 жыл бұрын
finally someone understood recursion.
@Xnoob545
4 жыл бұрын
Exept its a different video 1 second shorter
@thezionjohnson3590
2 жыл бұрын
@@Xnoob545 haha
This is the clearest explanation I came across! Thanks so much! 👏
@geeves21312
5 жыл бұрын
^ 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.
@unda25
5 жыл бұрын
i felt the same
@siddhantjha6649
4 жыл бұрын
same here
@frankynakamoto2308
4 жыл бұрын
When there is a need to use recursion???
@tonyaltass30
4 жыл бұрын
@@frankynakamoto2308 Prolog makes use of recursion extensively
Google "recursion"... did you mean "recursion"?
@PraveenNelsonv6
8 жыл бұрын
seems like google has got a bug
@themeeman
8 жыл бұрын
LOL
@ShethBhavik
8 жыл бұрын
It's not a bug. It was done intentionally by Google because of what recursion means.
@Spee2k12
7 жыл бұрын
lol as if this subject wasn't confusing enough google makes a joke and makes it more confusing in the process.
@Secretzstolen
6 жыл бұрын
Awe didn't work. Would've been funny!
Honestly speaking, this is the best recursion explanation I've ever heard.
I already understood the basics of recursive functions in programming, but this explanation was really well done. This man makes programming beautiful!
@sirbottoms1998
8 жыл бұрын
Yep
@stevebez2767
6 жыл бұрын
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?
@ddmuzyk
8 ай бұрын
mr neural network?@@stevebez2767
Recursion; (noun) see: Recursion
I personally wouldn't trust the Comic Sans n to return the correct value.
@zamfofex
9 жыл бұрын
kek
@stevebez2767
6 жыл бұрын
Personalities Few Char RISC tick tick interrupted read turns?
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.
This fellow deserves to be called an "educator".
This is like the best recursion explanation of all time.
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.
*Thank you! Well explained!!!*
This is hands the most straight forward explanation of recursion in the universe 😐
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
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.
This is such a simple and to-the-point explanation.
Why can't you be my teacher.... for EVERYTHING
@AlexRubio
8 жыл бұрын
tried that and even wished it to Santa and it didn't happen.
@theflaggeddragon9472
8 жыл бұрын
+Reclaimer Halo 3 :D
@stevebez2767
6 жыл бұрын
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?
@MsJavaWolf
6 жыл бұрын
Even the dirty things in life?
@thezionjohnson3590
2 жыл бұрын
@@MsJavaWolf no such things has dirty
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!
Reviewing this concept a year later, Prof Barilsford's teaching style is still really one of the best
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.
It's always exciting to discover a professor that can actually teach. Great intro to recursion.
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.
I must say, I now wish that you were a professor at my university. The simplicity and explanation is flawless. Thank you.
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.
@alexandersnell4550
7 жыл бұрын
Test your 0 statement better, jeez. Are you even qualified to use recursion? lol
@BosonCollider
7 жыл бұрын
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. ; )
@prismickyubey1185
7 жыл бұрын
7thChosen Segmentation fault, stack ran into the heap. ( ⚆ ͜ʖ ⚆)
@SeventhChosen
7 жыл бұрын
@Prismic Kyubey hey hey, watch your mouth! there are kids here... lawlz
@philspaghet
7 жыл бұрын
There's no base case, RIP
I really wish these videos were out when I was learning programming at uni. This is such a concise explanation. Thankyou!
@theundeadforever3300
3 жыл бұрын
Where in life are you right now ?
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.
This is by far the best explanation in youtube as to how recursion works. This recursion-thing is tricky.
Very helpful and useful for my CS class. Thanks a lot, a really informative video.
@sirbottoms1998
8 жыл бұрын
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
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.
@Summer9604
5 жыл бұрын
cool :D
@diablominero
3 жыл бұрын
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.
you've explained the concept really beautifully and elegantly. totally in love
Incredibly well and thoughtfully explained, with plenty of visual aid to better understand the concept. Many thanks!
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]
@JeyPeyy
7 жыл бұрын
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.
@stevebez2767
6 жыл бұрын
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?
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.
@diablominero
3 жыл бұрын
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.
Thank you Professor Brailsford - for such an elegant explanation and also to the videographer for filming the video.
This is the most comprehensive illustration of Factorial I've ever seen.. brilliant, simple, elegant. Thank you!!!
So basically recursion is when a function calls itself.
@metafis2490
9 жыл бұрын
Yes..like in those mandelbrot pattern, the basic equation for those is z = z2 + c, iterated a specified number of times.
@rich1051414
9 жыл бұрын
Jason Wilkins iteration is not recursion. It is the same only in the way you evaluate it in your mind. For example... while(true);
@Tupster
9 жыл бұрын
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.
@rich1051414
9 жыл бұрын
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.
@Tupster
9 жыл бұрын
I didn't say anything about compiler optimization.
I really liked how the stack was explained as "people" waiting for other person to do their job
This video was what finally made me understand the concept. So well explained...This in terms of knowledge, is almost a recursion itself, endless potential!! Thanks to the Professor and to who made the little graphic while he explained the stack working!!
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.
my dream is to be as good as this guy
@stevebez2767
6 жыл бұрын
'Guy' is the word as example recalls memories of long ago(whether this bloke exsist said now or not)as was shown KZread 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???!
@derschwarzejulian7201
4 жыл бұрын
Youbhave to be surpass him and make other people wanting to be like you. Than you reached what this man reached an more!
Great explanation made by a true master.
Professor Brailsford's knowledge and ability to explain concepts is phenomenal.
I am wowed. I've fallen in love with Computerphile with this one video! This was as clear as day!
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)
@jetison333
3 жыл бұрын
Wow, I think your actually pretty right.
def understandRecursion(mind): if mind.understands == True: return else: understandRecursion(mind)
@Saharayeti
4 жыл бұрын
Ist ist still running?
@boko7654
4 жыл бұрын
@@Saharayeti Nein, ist sinking
@Saharayeti
4 жыл бұрын
@@boko7654 scheiß Autokorrektur, I am sinking about turning it off
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
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!
Short answer: Recursion is the _best thing ever._
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.
@bytefu
7 жыл бұрын
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.
@JohnSmith-ut5th
7 жыл бұрын
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.
@LunarySSF2
7 жыл бұрын
what's the complexity of the function *factorial* ? n or 2n-1 ?
Best recursion explanation,I have ever seen.Thanks @Computerphile for 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!
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
@devanjith
9 жыл бұрын
שגיא קרמן Illuminati confirmed!
@ModKijko
9 жыл бұрын
שגיא קרמן T¬?$ªdƒ¯•+
@sagiksp4979
9 жыл бұрын
mod prime I know now but what do they mean?
@ModKijko
9 жыл бұрын
שגיא קרמן 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.
@Computerphile
9 жыл бұрын
שגיא קרמן 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
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.
@TCWordz
9 жыл бұрын
Well that's unnecessary in your example. _Hour _*_x_*_ = 2(Hour _*_x_*_ - 1)_
@anthonyalbertorio5180
9 жыл бұрын
Tommy59375 Both ways are great explanations.
@anthonyalbertorio5180
9 жыл бұрын
Great explanation.
@trppmdm
9 жыл бұрын
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.
@xXxBladeStormxXx
9 жыл бұрын
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.
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.
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.
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. ;)
@natangurfinkel
5 жыл бұрын
Fair point.
Make a video about net neutrality.
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 just love this guys voice, Very soothing.
4:52 thought that he was about to kick the bucket lol
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.
Watching your videos is such an easy way to learn English (both as programming), thank you guys!
5 years later and this is still the best explanation ever. Understand the stack is a key fundamental.
The base case for factorial is actually 0! = 1
@Mikey_in_Japan
4 жыл бұрын
I was looking for this comment to see if anyone else caught that
@ivana4638
4 жыл бұрын
Yes, but it really has no purpose in code.
@7s9n
3 жыл бұрын
I finally found someone he's thinking like me 💛
@MichaelLehnGermany
3 жыл бұрын
@@Mikey_in_Japan Me too :D
@MichaelLehnGermany
3 жыл бұрын
@@ivana4638 It certainly has.
recursion: see recursion
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 !
4 years later..... Still the best one on youtube!!!
The professor has an ASMR-ish voice, close Bob Ross's. 💞
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?
@outcastorange
10 жыл бұрын
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.
@Tupster
10 жыл бұрын
Of course. Any kind of parsing is recursive. Any kind of structure that can contain similar copies if itself (like HTML) requires recursion.
@CrateMuncher
10 жыл бұрын
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.
@ghelyar
10 жыл бұрын
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.
@Tupster
10 жыл бұрын
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.
Wonderful explanation! I read articles and watch a couple of videos on the definition of recursion and this is by far the easiest to understand. Thank you.
This professor is very talented, his explanations are clear as crystal
What would recursion be without a stack!
@AaronSeigo
10 жыл бұрын
A: tail recursion
@stevebez2767
6 жыл бұрын
RedHat,Linux lie Nukes?
Don't you get a stack overflow if you do this with a number to big though?
@NNOTM
10 жыл бұрын
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.
@SevenDaysify
10 жыл бұрын
yeah, but you can avoid that with tail calls
@murphy54000
10 жыл бұрын
You'd hit problems with the number being too large before you hit stack overflow.
@Celrador
10 жыл бұрын
***** I wonder, if that also is the case for a long double. :o Can't be arsed to research and calculate that now, though.
@murphy54000
10 жыл бұрын
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.
This is such a good explanation. Went to recreate this in JS and it makes perfect sense. The way I like to picture it is as each number that gets recursed is its own scope, and the value of n will always be shadowed until it hits back to the global scope, where n is the lexical value
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.
4:52 :)
@llspadrllllytll9248
5 жыл бұрын
Ah
Where can I learn to code with a marker and piece of paper
@UnordEntertainment
9 жыл бұрын
BorisMediaProds Make up your own pseudo-code or use existing pseudo-code and you're done!
@BorisMediaProds
9 жыл бұрын
Flumpanor I was making a joke lol
@UnordEntertainment
9 жыл бұрын
BorisMediaProds I wasn't xD
@fuppetti
9 жыл бұрын
Flumpanor ah hahaha! [cheesy 80's music plays]
@stevebez2767
6 жыл бұрын
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..
Thank you professor Brailsford, I've never been in school to have the developper job I have, but I would have you as a teacher. The concept of the stack and "different ns" helps me to better understand what I code everyday !
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
@lordofduct
10 жыл бұрын
***** 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.
@SkyrimHod
10 жыл бұрын
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!
@JamesCoyle95
10 жыл бұрын
Any competent programmer would handle that. The code here is simplified so it is easier for non-programmers to understand.
@JamesCoyle95
10 жыл бұрын
lordofduct It should be handled by throwing an out of range exception rather than letting the code execute until it fails.
@lordofduct
10 жыл бұрын
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.
I half-expected this to be a 10-minute video of him just repeating "recursion is recursion is recursion is...".
this is undoubtedly the best explanation video i have ever watched on youtube
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.
Now time to explain how to make a computer do it iteratively? :D
recursion is a whole disgusting evil thing you never want to touch it will only end in tears
@agentsmidt3209
7 жыл бұрын
too late.
@slamislife74
7 жыл бұрын
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
@agentsmidt3209
7 жыл бұрын
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.
@user-assia
7 жыл бұрын
noooo it's awsome ! you just need to be friends with it
@beri4138
6 жыл бұрын
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.
Thanks Prof. You simplified this concept and made it very understandable. This is hands-down the best explanation on factorial that I have seen yet!! Thanks you Sir
Hands down the best explanation I have ever seen on recursion. Great vid.
Recursion can only be understood if you understand what recursion is.
to understand what recusion is, you must first understand recursion.
A clean and clear explanation, plus the Professor seems to be a great guy.
These explainations are amazing, thank you so much Computerphile team ❤️
He been coding so long he uses a " * " instead of an " x " for multiplication wait maybe he's an AI.
@EDToasty
9 жыл бұрын
using * in writing is totally acceptable too, I use it all the time (same with / )
@smmoom1212
9 жыл бұрын
ClassicPork Not to mention its what you use in coding lol, if you typed x for multiplication, you'd end up with an error saying x isn't a known variable lol
@ryno4ever433
5 жыл бұрын
Makes sense. It would be confusing if he used x imo
@YoungDen
4 жыл бұрын
Especially when simulating a program
i dont like recursion when programming, gets out of control way too fast. i prefer cycles, far more reliable.
@beri4138
6 жыл бұрын
What are "cycles"?
@stevebez2767
6 жыл бұрын
As under control ,do you view presidents on TV?
@MrCmon113
6 жыл бұрын
Of course. Recursive definitions are for a better understanding. In code however they may lead to a horrible runtime and memory usage.
So clear explanation, I haven't even learned trees & graphs but I already understood the basics of recursion thanks to computerphile!!
This is a brilliant explanation of recursion. Thank you! You have done what my professor could not.
Recursion isn't hard at all, it's pretty simple.
@prismickyubey1185
7 жыл бұрын
tabularasa0606 *Triggered*
@tabularasa0606
7 жыл бұрын
No, removed comments. Also necro-post
@prismickyubey1185
7 жыл бұрын
tabularasa0606 I was joking that I was triggered lel
@LaVivien
6 жыл бұрын
it seems recursion is factorial, factorial is recursion;)
@stevebez2767
6 жыл бұрын
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?
What about factorial(0)? This guy's implementation will crash, lol. Some bad programming there. Or bad math.
@ConnorKuehl
9 жыл бұрын
Алексей Салихов An input of 0 would be handled when reading in what the user would want to find the factorial of. His program is fine.
@PressStartLetsPlay
9 жыл бұрын
***** You are exactly right. You would check if the input is 0 or 1, and if so, return a value of 1. Otherwise, run through the rest of the code.
@ConnorKuehl
9 жыл бұрын
AntarezGames Making a comparison with EVERY recursive call to make sure that you're handling valid input is certainly not more efficient than having ONE comparison in a wrapper function and then the recursive call.
@BorisMediaProds
9 жыл бұрын
if(n
@richardwalker3760
9 жыл бұрын
Antarez And extending your logic, you feel that using full recursion to calculate factorial is ... what? ... efficient? Think about it.
Professor Brailsford is an excellent teacher, especially like the visual explanation toward the end of the video.
I thought of this as being different instances of the function(n) and was very pleased that he literally described it that way. Thanks