learn recursion with me

if you wanna be able to solve those dynamic programming leetcode problems you have to be able to think recursively but don't worry I got you I am Tara I'm a senior software engineer and I used to teach computer science at Carnegie Mellon today we are gonna learn the basics of recursion consider the problem of factorial so that we know that the definition of factorial of five would be equal to five times four times three times two times one right but what about factorial of four so if I bring down factorial of four I know the factorial of four is four times three times two times one you'll notice something interesting that the definition of factorial of five actually contains factorial four so we can actually just say you know what let's just define factorial five as five times factorial four and so how would we actually generalize this what is factorial of n well factorial of n is equal to n times factorial of n minus 1 recursion sounds really scary but really at its heart it's just solving a problem by first going off and solving a smaller version of that problem and then using that answer with the current step that you're on to come up with the whole answer for a factorial of five it's like okay we don't know what factorial of five is but what if I told you I did know what factorial of four was and if I gave you that answer could you figure out what factorial of five is of course you could cause you just know that it's five times factorial of four the way that I like to think about it and the way that I used to teach it was you have this almost magical oracle that's like hey I know how to solve the subproblem I don't know how to solve factorial of n but I do know how to solve factorial of n minus 1 and if I give you that answer can you use it to figure out factorial n let's write the code for factorial so we just covered in our definition over there that factorial of n is equal to n times the factorial of n minus 1 and the really beautiful thing about writing a recursive function is it almost feels like you're just writing math that's literally the same thing as the code I can literally just say return this return n times factorial of n minus 1 and yes this function is calling itself this is not a typo when I say factorial of n minus 1 here I am calling the same function that we are writing right now that does trip people up sometimes alright are we done not quite we're so close if you were just to run this it would loop forever we would just keep subtracting and minus 1 minus 1 minus 1 forever and ever and ever that's not good that's one of the scariest bugs that you can write so what we've actually written here is called the recursive case and we definitely need this recursive case but what we are missing is something called the base case the base case tells us when to stop it's essentially the smallest version of the problem for which we don't need to do any extra computation and so what is factorial of zero it's actually just one and what's the factorial of one it's also just one we just know that right off the top of our head we didn't have to do any extra multiplication to get there so that's a hint that those are our base cases so we can say if n is less than or equal to one return one and there you go what a beautiful elegant solution and this is why I actually really love recursion now you have some building blocks for understanding dynamic programming which is what we're going to be doing next I will show you how to spot a dynamic programming problem in the wild so stay tuned for that