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

[@docopoper]

I'm sad you didn't put a link to this video in the description.

[@stevebez2767]

DES(ooo,Sad,wait 4 that nit,Nat,nag)

[@aloktiwari2732]

finally someone understood recursion.

[@Xnoob545]

Exept its a different video 1 second shorter

[@thezionjohnson3590]

@@Xnoob545 haha

[@Misterz3r0]

4:52 The sound a compiler makes when executing a recursion call.

[@Newborn228]

lol'd a little harder than I should've

[@norbertmarko6479]

I'm laughing at this for 2 straight minutes now

[@ChunkyChest]

HAHAHA

[@yashsvidixit7169]

Except that compiler doesn't perform recursive calls due to some recursive code it's compiling.

[@davidflores1645]

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"

[@Ronenlahat]

Google "recursion"... did you mean "recursion"?

[@PraveenNelsonv6]

seems like google has got a bug

[@themeeman]

LOL

[@ShethBhavik]

It's not a bug. It was done intentionally by Google because of what recursion means.

[@Spee2k12]

lol as if this subject wasn't confusing enough google makes a joke and makes it more confusing in the process.

[@Secretzstolen]

Awe didn't work. Would've been funny!

[@funastacia]

This is the clearest explanation I came across! Thanks so much! 👏

[@geeves21312]

^ 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]

i felt the same

[@siddhantjha6649]

same here

[@frankynakamoto2308]

When there is a need to use recursion???

[@tonyaltass30]

@@frankynakamoto2308 Prolog makes use of recursion extensively

[@NikolajLepka]

Recursion; (noun) see: Recursion

[@newbie6036]

Honestly speaking, this is the best recursion explanation I've ever heard.

[@alvaroplol]

I already understood the basics of recursive functions in programming, but this explanation was really well done. This man makes programming beautiful!

[@sirbottoms1998]

Yep

[@stevebez2767]

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]

mr neural network?@@stevebez2767

[@X_Baron]

I personally wouldn't trust the Comic Sans n to return the correct value.

[@zamfofex]

kek

[@stevebez2767]

Personalities Few Char RISC tick tick interrupted read turns?

[@uexp4]

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.

[@colza1025]

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.

[@averagegiuseppe5640]

This fellow deserves to be called an "educator".

[@khiryshank4930]

This is like the best recursion explanation of all time.

[@SnedzTheBricklayer]

This is hands the most straight forward explanation of recursion in the universe 😐

[@SeventhChosen]

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]

Test your 0 statement better, jeez. Are you even qualified to use recursion? lol

[@BosonCollider]

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]

7thChosen Segmentation fault, stack ran into the heap. ( ⚆ ͜ʖ ⚆)

[@SeventhChosen]

@Prismic Kyubey hey hey, watch your mouth! there are kids here... lawlz

[@philspaghet]

There's no base case, RIP

[@greeneightball]

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

[@unreciever_]

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!

[@Sone418]

Why can't you be my teacher.... for EVERYTHING

[@AlexRubio]

tried that and even wished it to Santa and it didn't happen.

[@theflaggeddragon9472]

+Reclaimer Halo 3 :D

[@stevebez2767]

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]

Even the dirty things in life?

[@thezionjohnson3590]

@@MsJavaWolf no such things has dirty

[@tobortine]

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.

[@zeusthecunnyabductor9425]

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 !

[@EsotericArnold]

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.

[@anand26shweta]

This is such a simple and to-the-point explanation.

[@yaweno9555]

It's always exciting to discover a professor that can actually teach. Great intro to recursion.

[@sejinmajnaric2884]

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.

[@LMacNeill]

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.

[@75IFFY]

I really wish these videos were out when I was learning programming at uni. This is such a concise explanation. Thankyou!

[@theundeadforever3300]

Where in life are you right now ?

[@TomsMucenieks]

*Thank you! Well explained!!!*

[@benphua]

Reviewing this concept a year later, Prof Barilsford's teaching style is still really one of the best

[@jiyoungyun7494]

you've explained the concept really beautifully and elegantly. totally in love

[@madghostek3026]

I really liked how the stack was explained as "people" waiting for other person to do their job

[@petrockspiracy3120]

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]

cool :D

[@diablominero]

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.

[@takatakboy]

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.

[@s-code-b]

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.

[@mberoakoko24]

my dream is to be as good as this guy

[@stevebez2767]

'Guy' is the word as example recalls memories of long ago(whether this bloke exsist said now or not)as was shown KZbin 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]

Youbhave to be surpass him and make other people wanting to be like you. Than you reached what this man reached an more!

[@mrbitbot]

So basically recursion is when a function calls itself.

[@metafis2490]

Yes..like in those mandelbrot pattern, the basic equation for those is z = z2 + c, iterated a specified number of times.

[@rich1051414]

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]

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]

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]

I didn't say anything about compiler optimization.

[@mjrupprecht6458]

I must say, I now wish that you were a professor at my university. The simplicity and explanation is flawless. Thank you.

[@litoxcas]

A book I read taught me all I needed to know about recursion in the index: Recursion: See recursive Functions, Recursive Functions: See Recursion.

[@HandyAndyTechTips]

Very helpful and useful for my CS class. Thanks a lot, a really informative video.

[@sirbottoms1998]

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

[@viralpatelify]

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]

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.

[@runeheidt]

This is by far the best explanation in youtube as to how recursion works. This recursion-thing is tricky.

[@osvaldorendallevora8215]

This is the most comprehensive illustration of Factorial I've ever seen.. brilliant, simple, elegant. Thank you!!!

[@NNOTM]

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]

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]

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?

[@DragoniteSpam]

Short answer: Recursion is the _best thing ever._

[@MeleeChannel]

Incredibly well and thoughtfully explained, with plenty of visual aid to better understand the concept. Many thanks!

[@KamiYugure]

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.

[@EmilMacko]

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]

Wow, I think your actually pretty right.

[@JoffreyB]

4:52 thought that he was about to kick the bucket lol

[@jodn4435]

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

[@francisaiello6197]

Thank you Professor Brailsford - for such an elegant explanation and also to the videographer for filming the video.

[@ghelyar]

The base case for factorial is actually 0! = 1

[@Mikey_in_Japan]

I was looking for this comment to see if anyone else caught that

[@ivana4638]

Yes, but it really has no purpose in code.

[@7s9n]

I finally found someone he's thinking like me 💛

[@MichaelLehnGermany]

@@Mikey_in_Japan Me too :D

[@MichaelLehnGermany]

@@ivana4638 It certainly has.

[@JohnSmith-ut5th]

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]

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]

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]

what's the complexity of the function *factorial* ? n or 2n-1 ?

[@TheOneMattWilkinson]

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.

[@jamais412]

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!

[@ZipplyZane]

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]

Fair point.

[@callumrocksyoursocks]

def understandRecursion(mind): if mind.understands == True: return else: understandRecursion(mind)

[@Saharayeti]

Ist ist still running?

[@boko7654]

@@Saharayeti Nein, ist sinking

[@Saharayeti]

@@boko7654 scheiß Autokorrektur, I am sinking about turning it off

[@danieltubonemi5882]

I am wowed. I've fallen in love with Computerphile with this one video! This was as clear as day!

[@barcelosm6395]

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

[@AleksandrVasilenko93]

Make a video about net neutrality.

[@MrStrongholdpro]

recursion: see recursion

[@normanfrankiv5512]

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.

[@zxkelxz]

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!

[@mumtahinarahman1075]

The professor has an ASMR-ish voice, close Bob Ross's. 💞

[@BenjaminRavenstone]

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]

Well that's unnecessary in your example. _Hour _*_x_*_ = 2(Hour _*_x_*_ - 1)_

[@anthonyalbertorio5180]

Tommy59375 Both ways are great explanations.

[@anthonyalbertorio5180]

Great explanation.

[@trppmdm]

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]

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.

[@shehzan9263]

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.

[@dharma6662013]

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.

[@sagiksp4979]

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]

שגיא קרמן Illuminati confirmed!

[@ModKijko]

שגיא קרמן T¬?$ªdƒ¯•+

[@sagiksp4979]

mod prime I know now but what do they mean?

[@ModKijko]

שגיא קרמן 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]

שגיא קרמן 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

[@kinnikuchu]

Great explanation made by a true master.

[@luckhappy888]

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.

[@BAMBAMBAMBAMBAM-]

These explainations are amazing, thank you so much Computerphile team ❤️

[@TheSlimyDog]

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]

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]

Of course. Any kind of parsing is recursive. Any kind of structure that can contain similar copies if itself (like HTML) requires recursion.

[@CrateMuncher]

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]

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]

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.

[@eagleeye1975]

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.

[@rolandfisher]

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.

[@evghend1714]

Watching your videos is such an easy way to learn English (both as programming), thank you guys!

[@GaryKildall]

What would recursion be without a stack!

[@AaronSeigo]

A: tail recursion

[@stevebez2767]

RedHat,Linux lie Nukes?

[@tzkelley]

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]

***** 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]

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]

Any competent programmer would handle that. The code here is simplified so it is easier for non-programmers to understand.

[@JamesCoyle95]

lordofduct It should be handled by throwing an out of range exception rather than letting the code execute until it fails.

[@lordofduct]

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.

[@moniruzzamanmoni676]

Best recursion explanation,I have ever seen.Thanks @Computerphile for this video.

[@Dekoded]

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

[@bobmandude9889]

Don't you get a stack overflow if you do this with a number to big though?

[@NNOTM]

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]

yeah, but you can avoid that with tail calls

[@murphy54000]

You'd hit problems with the number being too large before you hit stack overflow.

[@Celrador]

***** 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]

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.

[@PressStartLetsPlay]

4:52 :)

[@llspadrllllytll9248]

Ah

[@TomJez100]

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.

[@Submersed24]

Thank you for going over this!!! My teacher went over this in 5 seconds and expected everyone to get it... the problem is I'm ADHD.

[@IceMetalPunk]

I half-expected this to be a 10-minute video of him just repeating "recursion is recursion is recursion is...".

[@BorisMediaProds]

Where can I learn to code with a marker and piece of paper

[@UnordEntertainment]

BorisMediaProds Make up your own pseudo-code or use existing pseudo-code and you're done!

[@BorisMediaProds]

Flumpanor I was making a joke lol

[@UnordEntertainment]

BorisMediaProds I wasn't xD

[@fuppetti]

Flumpanor ah hahaha! [cheesy 80's music plays]

[@stevebez2767]

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

[@RedEyedJedi]

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.

[@joshuaplain6993]

4 years later..... Still the best one on youtube!!!

[@sporkafife]

Now time to explain how to make a computer do it iteratively? :D

[@FennecTECH]

recursion is a whole disgusting evil thing you never want to touch it will only end in tears

[@agentsmidt3209]

too late.

[@slamislife74]

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]

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]

noooo it's awsome ! you just need to be friends with it

[@beri4138]

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.

[@paulscott2502]

Professor Brailsford's knowledge and ability to explain concepts is phenomenal.

[@ufotofu9]

I just love this guys voice, Very soothing.

[@BryanMeadows011235]

He been coding so long he uses a " * " instead of an " x " for multiplication wait maybe he's an AI.

[@EDToasty]

using * in writing is totally acceptable too, I use it all the time (same with / )

[@smmoom1212]

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]

Makes sense. It would be confusing if he used x imo

[@YoungDen]

Especially when simulating a program

[@fadetounforgiven]

Recursion can only be understood if you understand what recursion is.

[@chiamakanwosu6831]

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

[@LordCucumber77]

Thank you professor, this really made me understand! I had this in class the other day and I found it to be a bit mind boggling, but this visual representation helped me a great deal!

[@Rob-bh9gt]

to understand what recusion is, you must first understand recursion.

[@tabularasa0606]

Recursion isn't hard at all, it's pretty simple.

[@prismickyubey1185]

tabularasa0606 *Triggered*

[@tabularasa0606]

No, removed comments. Also necro-post

[@prismickyubey1185]

tabularasa0606 I was joking that I was triggered lel

[@LaVivien]

it seems recursion is factorial, factorial is recursion;)

[@stevebez2767]

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?

[@chadking272]

Hands down the best explanation I have ever seen on recursion. Great vid.

[@ekkamailax]

One of the best teachers I’ve ever seen. Well done

[@Nekotamer]

i dont like recursion when programming, gets out of control way too fast. i prefer cycles, far more reliable.

[@beri4138]

What are "cycles"?

[@stevebez2767]

As under control ,do you view presidents on TV?

[@MrCmon113]

Of course. Recursive definitions are for a better understanding. In code however they may lead to a horrible runtime and memory usage.

[@user-bf1zg6tx6u]

What about factorial(0)? This guy's implementation will crash, lol. Some bad programming there. Or bad math.

[@ConnorKuehl]

Алексей Салихов 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]

***** 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]

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]

if(n

[@richardwalker3760]

Antarez And extending your logic, you feel that using full recursion to calculate factorial is ... what? ... efficient? Think about it.

[@LukiaTheTrue]

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 !

[@alexitopro9635]

Fantastic explanation. I really wanted to understand how a programming language dealt with recursion and this channel nailed it.