Recursion Simply Explained

[Music] what is going on guys welcome back in today's video we're going to talk about recursion now this is a very important topic to understand especially for intermediate programmers because you're going to encounter it everywhere however a lot of people have a hard time wrapping their mind around this concept because it's kind of abstract and confusing especially for beginners so in today's video i want to give you a simple straightforward and easy to understand introduction into recursion recursive thinking and recursive programming in general for this we're going to start by looking at the theoretical foundation we're going to talk about the theoretical structure of recursive functions then we're going to talk about advantages and limitations of recursion and then we're going to look at a couple of examples of functions implemented iteratively and recursively we're going to compare the two ways and we're going to talk about advantages and disadvantages all right so what i want to mention right away is that every function every algorithm can be implemented iteratively and recursively so one paradigm is not more powerful than the other one we cannot do something iteratively that we cannot do recursively and vice versa every iterative function can be rewritten in a recursive way and vice versa sometimes one paradigm is going to be more suited to a specific task but basically they're equally powerful now recursion is essentially when a function calls itself so if i have a function my function and this function inside of the function block calls itself this is recursion so in python and this is by the way language independent so recursion is not a principle in python you can do that in java or you will need that in java in c plus c php javascript whatever so if i say def my function [Music] and inside of that function i have some code for example print hello and then i call this function this function calls itself this is recursion so i have the function my function and inside of that function it calls itself this is recursion now in this case it's an endless recursion and that has a certain uh problem and this is a stack overflow error now in python we're not going to get a stack overflow error because in python we have a recursion depth limit so think about it when my function calls itself it calls itself which means that it's going to call itself all the time because the thing that it calls is itself and this thing calls itself again so there's no end to that and if i run this you will see that we will get an error we're not going to get a stack overflow error we're going to get a recursion error because the maximum recursion depth was exceeded now we can change that value we can manipulate that value and allow for more uh depth but however we're not going to be able to do this endlessly we're going to hit a limitation in other programming languages we don't have necessarily a limit we have a stack and this stack is basically a memory where we say where we save the jump back address every time we call a function we we put the return address onto the stack and once the function is done processing we're going to return to that however we only return to that if the function terminates at some point if we constantly keep calling and calling new functions without actually returning at some point we're going to fill up the stack with return addresses and then it's going to be full and it has to uh to break down causing a stack overflow basically so this is what the stack overflow era is and this can happen with recursion cannot happen with the iterative approach this is a limitation of recursion however an advantage of recursion is that oftentimes writing functions and algorithms in a recursive way is more intuitive it's more clear it's more elegant it's more mathematical you could say sometimes it leads to less debugging time and less development time and sometimes we can even reduce time complexity by using a recursive approach however sometimes we can also increase the time complexity and we're going to take a look at that in today's video as well when we look at the fibonacci sequence an example that i have shown on this channel uh quite a lot of times already and for some tasks like for example three traversals the recursive approach is just more intuitive and just better overall because it's more straightforward we see what it's doing so let's talk about the theoretical structure the theoretical foundations of recursion essentially a recursive function has to have a base case a base case a termination point if you want a point where after some recursive calls we get to a point where we can finally return so if we have a function again def my function and we do something in that function i have to have a case where if certain conditions are met i can finally return a static value so not return another function call but return something like one or maybe a larger number doesn't matter some value something that terminates some at some point i need to stop uh stop the recursive calls i need to to have this base case where i can say now i'm done now i'm at this point where i don't do any more recursive calls so i can go back and if you want unravel all the recursive calls return to all the addresses and return the final value so this is the base case then another principle is or the second principle there are only two two principles here the first one is the base case the second one is with each recursive call we need to be progressing towards that base case uh and those two statements might sound a little bit abstract and theoretical which is why they might be confusing what is the base case what does it mean to be progressing towards that base case so we're going to start with a very simple example let's say we want to have a function we're going to start with an iterative approach we're going to have a function that counts the zeros in a list of numbers so we're going to have a list of numbers up here my list and we're going to have a bunch of zeros in here and other values like that so here we have one two three four five six zeros now we're going to write the function count zeros we're going to pass a list here and iteratively this is kind of easy we're just saying the counter is going to be zero and no we're not going to use the count function of python obviously we're going to write it ourself uh we're going to say counter equals 0 and then 4n or 4x in list we're just gonna say if the value that i'm currently looking at is a zero we're going to increase the counter by one and once i'm done i'm going to return the counter so if i call count zero on my list i should get six as a result so let's no not debug this come on let's just run this of course we should print the results if we want to see it and there you go six is the result so this is a very simple iterative approach there is no recursion in here now we're going to implement the same function in a recursive way and for this we're going to call it count zeros recursive or recursively and we're going to pass a list here as well now we're not going to use any loops here we're going to use recursion and we can also not use in a meaningful way a local variable why because if i have something like counter equal zero think about it if i say counter equals zero and then i do some counter plus equals one or something and then i call the function uh so let's say i do it in in a certain case instead of iterating i do it recursively and then i increase the counter if i find something it doesn't work because when i call this function or when the function calls itself it's going to re-initialize that counter to zero so the only thing that we could do is we could use a global variable so we can say something like counter equal zero out here and then i can access this counter i can make it global and work with it but that's not really a clean recursive approach so we're going to do it without that we need to think of a different solution now the recursive approach here would be to process each element individually let's say we have the function already implemented how would it work so let's say this function works already we have to trust it what we would do is we would take this list here and we would say okay in order to count the zeros what i could do is i could just look at the first element and say either zero or one so a zero if it's not a zero and a one if it's uh if it's a zero so we count up but we count up by adding to the return value so what we do is we say okay take the first element if it's a zero add one to the to the final result otherwise add nothing or add 0 to the final result in this case it would be 0 plus call the function on the rest of the list so we remove that first element up until now we have 0 plus this function applied to that remaining list this again would do the same thing it would look at the first element in this case a 0 and say okay i have a 1 here plus whatever this function returns on the rest of the list so i remove again the first element here i would have a 0. then a 0 again because we have a 3 here and then we would have again a 1 and so on so we basically just look at one element and say zero or one depending on if it's a zero or not and then we just trust the function to accurately process the rest of the list however what do we do when we reach the last element this is where the base case comes into play because we need to have a terminating base case where we say okay now this is uh the point where we don't do any more recursive calls this is where we just return zero or one so in the end if we have a bunch of data so we have like plus one plus zero whatever plus one plus one plus zero and then in the end we have only one element left then instead of returning a function call we just return one or zero in this case zero because it's a two so let's get into the implementation before this gets too confusing what we wanna do as a general rule is we wanna define how is the counting going to happen and the counting is going to happen by just saying okay if the first element of the list so if list 0 if that equals to 0 all i'm going to return here as a result is i'm going to return 1 because i already found 1 0 plus the function applied to the rest of the list pause the video if you don't understand it think through it what we're doing here is we're looking at the first element if it's a zero i already found a zero so i add one to the return result and then i trust this function of course we need to to specify here that we're cutting off the first uh the first digit so what we're doing here is we're removing the first element that we already have here either zero or one and then we apply the same function here on the rest of the list and of course we need an else branch so if the value is not zero we're just going to return zero plus count zeros recursively list one until the end however instead of adding zero we can also remove that i'm going to leave it here just because it's a little bit more intuitive to understand what's happening this is the exact same thing but it might be a little bit confusing if you're already confused uh and not able to understand recursion those are basically the two branches we have the first element is zero so one plus count the zeros in the rest of the list the first element is not zero for example a two so zero plus count the rest of the list and of course when we call that function it's going to do the exact same thing the only thing that we need to do is we need to formulate a base case so that when the list is only having one last element we wanna have the case that okay the length of the list is equal to one so there's only one element left then we're going to return one if this element is equal to zero and else we're going to return zero this is just a ternary operator basically the same thing is saying if it's zero return one else return zero and one base case that might make sense not because we're going to reach it through recursion but because we might pass an empty list we can also formulate a base case for an empty list so then of course zero is the result this is optional you can you can ignore that if you are already confused so let's go through the process one more time we have this list we pass it to the recursive function what happens is it says okay the length of the list is not one because we have a couple of values in here so what we're going to do is we're just going to look at the first element is it a zero no it's not it's a two so let's go to this branch we have zero zeros plus whatever we have in the rest of the list so what we do is we call this again with the rest of the list this time is going to go into that branch and say okay it's 1. so this here is actually that statement here because we reached that statement we have a 0 already plus in this case would be that statement so that would be unraveled what we already have and this goes on and on and on until we finally reach the base case that returns one if the last remaining element is zero and else it returns zero this is the recursive approach for counting zeros we can call that function by saying count zeros recursively in my list and you can see that the result is six so it works the same way that the iterative approach works but it's a little bit more complicated so if you didn't understand that go back into the video pause it think about it what's happening we're just processing each element one by one and then we're trusting the function to be able to solve the problem the same problem for the rest of the list until we reach a base case and then once we reach that base case all these function calls are going to be replaced by the actual values that they're returned so it's going to be a chain of one plus zero plus zero plus one and so on uh and then it's going to be added up to the final result which is six in this case now the second example that we're going to look at is going to be a function that finds the minimum of a list and the iterative approach for this is quite simple we're going to say find min by the way i've changed the list a little bit so we have a little bit more diverse values we're going to pass a list here we're going to say the minimum is going to be assumed to be the first element of the list just because we're naive and we're going to believe that unless we find something else unless we find a counter example and then we're going to look for that counter example by saying 4x in uh in list if x is less than the minimum that we assumed we're going to just say that the new minimum is going to be x and then we're going to return that in the end so in this list the minimum is one so if i apply find min to my list we should get one as a result there you go we get one as a result so that's the iterative approach quite simple the recursive approach is um actually similar to the counting zeros approach we look at the first element and then we change the minimum function so what we're going to do not change we're going to chain the minimum function so what we're doing here is we're going to say find min recursive and essentially we can find the minimum of the whole list by just saying and this is going to be uh the actual progression towards the base case and this is just going to be the minimum of the first value and whatever minimum we get for the rest of the list so we're going to call recursively find min recursive and we're going to call this on list except for the first element by the way i didn't mention that for the first example this is the progression towards the base case because we said we need a progression towards the base case this is given because the base case and in this case it's also going to be the base case if the list if the length of the list is equal to one then we're going to just return the respective value as the minimum of the list this is the base case so the base case is that the length of the list is one and since we're constantly decreasing the list length by one this is a progression towards the base case this is given here we have a base case and we have the progression towards that base case uh here again we can of course say if the length of the list equals zero we're just going to return none because there are no elements in the list but this is the actual base case that we're progressing towards and what we're doing here essentially is we're saying okay the minimum of the list is going to be the minimum that i have here so 10 the first l the first element is the minimum of this this one value because it's just one value and then we have the rest of the list for which we're going to do the same thing so for that list 99 is going to be the minimum and if it stays the minimum the final uh unraveling of the recursions is going to be comparing 10 and 99 but from that list when we call this function over and over again the minimum that we're going to find is going to be one and then we're going to compare 1 to 10 in the last unraveling if you want to call it that in the last return uh to the to the main function call we're going to compare 1 and 10 and we're going to see that one is just a smaller value so we're going deeper and deeper and deeper and we're going to then compare 3 with 22 and 22 with 43 and so on we're going to go back until we reach the main function call and then we're going to see that one is the smallest value because it's going to be the one value that persists across all the minimum calls all right so let's run that i'm going to print find min recursive off my list come on and we're going to see that one is the result here as well now we're going to also talk about the fibonacci sequence and this is an example that i have shown you a couple of times on this channel already it's one of those cases where you should not use recursion because it's just inefficient so the fibonacci sequence is a sequence of numbers that starts with zero and one and every next number is the sum of the previous two numbers so in this case zero plus one would be one one plus one would be two one plus two would be three two plus three would be five three plus five eight and so on uh up until infinity and we can just make an iterative function just code an iterative function to calculate the nth fibonacci digit so we can just say def fibonacci n is going to be a and b are going to be the starting values and they're going to be initialized with 0 and one and then we're just gonna say four some counter variable that we don't really need in range n zero n we're going to just say a and b are going to be reset to a should be b so we're just going to shift it to the left and then the new b is going to be a plus b which is the basic definition and once we have all iterations done the result is going to be stored in a so we can print a couple of numbers here fibonacci uh digit 0 is going to be 0 then fibonacci digit one should be one and then we can do that for two as well and then we can do that for i don't know a hundred and you can see we have zero one one the next one would be two and so on and 100th fibonacci digit would be this one and you can see that this works quite well so i can also go with a thousand and it immediately calculates the result which is a huge number as you can see this is the iterative approach now the recursive approach is different the recursive approach uh is a little bit more intuitive because we understand what it does it's essentially fibonacci recursive and we're basically returning the fibonacci number before that so n minus 1 plus fibonacci recursive n minus 2 which is exactly the definition to get the nth fibonacci number all you have to do is you have to get the n minus one fibonacci number and the n minus two fibonacci number so you have to look at the previous two numbers to calculate the next number this is the definition this is as straightforward as it gets and of course we have the base cases because we need to know okay what is the first one and what is the zeroth one and for this we say if n equals zero we're just gonna return zero and if n equals 1 we're going to return 1. and in this case it's actually important to specify both base cases because we access n minus 1 and n minus 2. so if we pass 2 we're going to get one and zero at the same time and we need to have two base cases here in this case and of course we're progressing towards these main cases uh base cases because we're constantly subtracting numbers from n now the problem with that is the runtime complexity and before i explain to you if you don't know this already why this is the case let me just show you that it is the case so if i call fibonacci recursive on let's call it on small values first on zero on one on 2 and then maybe on 20 if i run this now you can see that we have the same result so i can get the digits i can also get the 20th digit but now let's try to get the 100th digit as we did before and now you can already see that this takes quite some time we still don't have the result as i'm talking here we still don't have the result we can wait quite a long time to get it and especially if i enter a thousand we can wait a very long time why is that the case this is the case because here we're not calling the fibonacci function recursively once we're calling it twice for each call which means that when i call it once the first function call calls itself two times those two function calls call themselves again two times and again two times two times each call calls itself two times or twice this means that we have two to the power of n function calls for the input parameter n and this is for those of you who know a little bit about algorithmic runtime complexity this is an exponential runtime complexity it's in big o of 2 to the power of n which is a horrible runtime complexity especially compared to this one which is in o of n which is a linear runtime complexity which is very desirable and nice to have we're not talking about quadratic here we're not talking about polynomial we're not talking about cubic we're talking about exponential runtime complexity which is a very bad complexity to have especially compared to linear so this this is not good this might be straightforward this might be mathematical and easy to understand it's a bad idea to do fibonacci that way uh what you can do to speed that up is you can use caching i have a video on this channel on this so you can type on my channel python caching and you can find a way to speed that up using caching but again the iterative approach is just better so this is not recommended here all right so last but not least i want to show you how you can set the recursion limit in python manually and for this we're going to have a sample function my function it's going to take a parameter n and all it's going to do it's going to print the numbers from 1 to n and n is going to be the variable of course that decides the maximum we're going to say if n equals zero this is going to be the base case we're just going to pass so to basically do nothing to return otherwise what we're going to do is we're going to print n and we're going to call the function with n minus one so progression towards the base case of course only if n is positive because if n is negative we're not progressing towards zero we're going up until we're down until negative infinity so you have to enter positive values here um and essentially what we can do here now is we can call my function on 10 and you will see that this essentially prints the numbers 10 down to one if i want to print if i want to count up all i need to do is i need to do the recursion before i print and then i'm going to reverse the order one two three four five and so on uh and of course i can do this with a hundred and i can do this with 200 but you're going to see that there's a problem if i try to do this on a thousand because we have a certain recursion depth limit there you go recursion error maximum depth exceeded i think the maximum value that it tolerates is 996 at least on my system if i want to change that what i want to do is i want to import sys and then i want to say sys.set recursion limit and for example i can set it to 5000. so if i change that now to 2000 it will work however we cannot do this uh without a limit because as i said we have a stack and the stack is limited so i think if i actually try to do 5000 i'm going to get an error but i'm not going to get the recursion error i'm going to get a stack overflow so python is just going to crash on me and i think it will take some time for this to happen but you can see that nothing is happening here and eventually it's going to crash and tell me that things didn't work out because i mean it's not going to say that it's a stack overflow but it's going to basically crash maybe if i try 4000 it's going to happen faster however we cannot go limitless i think there you go we got an error here uh this is basically because we did too many recursions i don't know what the actual practical maximum is maybe 3000 is going to work let's see uh doesn't seem like that is the case but you have to play around with that but if you want to set the recursion limit for some reason to go a little bit above the boundaries you can do that with cis dot set recursion limit so that's it for today's video if you enjoyed hope you learned something if so let me know by hitting the like button leaving a comment in the comment section down below and of course don't forget to subscribe to this channel and hit the notification bell to not miss a single future video for free other than that thank you so much for watching see you next video and bye [Music] you

Channel: NeuralNine

Views: 7,758

Keywords: recrusion simply explained, recursion simple explanation, recursion simple tutorial, recursion tutorial, recursion python, how to understand recursion, recursion easy explained, recursion easy tutorial, python recursion tutorial

Id: -Vq0bJf7GP4

Length: 27min 58sec (1678 seconds)

Published: Thu Oct 21 2021