Welcome everybody, you're watching mr fugu data science. Today we're doing recursion.
Thank you to the recent subscribers and viewers, i greatly appreciate it. Feel free to stop by:
buy me a coffee and show some support to help this channel. Let's get started.
What really is recursion? It's when you have a function that directly or indirectly calls itself.
And when should you use it? Consider if you have a task that needs to be broken up into sub
routines. When the results of one step can be used in a previous step. Well what are some of
the considerations of using recursion? Well if you have a loop that can achieve the same thing,
consider using the loop. You have to take into account memory management. Depending on how nested
the variables and parameters are, this can become a computation hog. Think about this: each instance
produces a new variable to store, and use. So each instance is stored in memory as a copy.
A new copy. Time can be an issue. Debugging can be difficult. You have issues where you can calculate
redundant events, such as doing the fibonacci sequence. Three common issues with recursion:
not setting up a base case, you're not progressing towards the base case, and the amount of resources
that you're actually using for each function call outweighs any benefit. With that being said, you
say well maybe i shouldn't even use recursion? Not exactly. The circumstances where it's beneficial,
you have to consider memory allocation and your stack. When using recursion remember that when
you call a function the memory is allocated on the stack and a stack works by last in, first
out. Remember the LIFO or lifo principle that you would have seen in data structures. And these.
There'll be an area or location where the data will be reserved on the stack. Now, when you call
your function for recursion, a place in memory is stored with a copy of your local variables.
Then when the base case is reached you remove the allocated memory and the value is returned. Think
of using pop. So you're popping something from the stack. Otherwise, you continue until the parent
function is reached. And you have to remember that this stack is consistently growing for each number
of recursive calls that you have. So how are we going to use it? First you need to establish
your base case. You're doing this because, you're trying to avoid having an infinite loop. You need
to next make sure that you're moving towards this base case. Because if not you'll be deviating from
the solution. Then you're going to have a call for your function which is doing your recursive step.
Essentially, what is going on, you're making a call to your function that is remembering
where you are at for the previous step. Then you are moving forward to approach your base case,
if all goes to plan. Let's look at a couple examples of where this can fail.
For instance, you could forget to add your base case. If we were summing some numbers,
and we forget to put a base case, here somewhere. For instance we would have an issue because we
want to know where to stop. If we wanted to get close to the base case. The next example:
what if we do declare a base case here. And we have our recursive call here which is calling this
sum once again. You have to notice that we have an issue. We're never getting close to the base
case because, we're consistently increasing our values. So we're just raising our values and never
approach the base case. You have to remember that as well. Remember recursion is used to subdivide
a problem into smaller sub problems to get close to some result that you're looking for. You could
have issues where you're not allocating resources effectively okay. You could arbitrarily start
doing other operations like maybe non-essential towards actually calling your recursive function,
such as making print statements and in separate lists storing irrelevant data
that may be unnecessary. You have to be careful with that. Let's look at two examples of the
fibonacci sequence and consider iteration versus recursion to get an idea of what can go wrong.
For instance the fibonacci sequence. We need to evaluate some form of a base case we could
start by something like this all right. Because we remember that if we're dealing with the factorial
zero and one factorial just equal themselves. And what essentially are we doing is taking the last
step and the second to last step and adding those together. And this is what the sequence starts
to look like when we print it off after a few iterations. Now let's look at some of the code
during the recursion process we're gonna start with our case of; if it's less than zero we need
to input a new value. And we're starting with our base cases here which are a little dubious.
But that's what we're starting with to get the sequence going. And then we have to recursively
call here, to add our last step and the step before that together to get our next step. And if
we time this for the fibonacci of 30 going up to 30 values we're gonna notice that this is in the
milliseconds here. When you start increasing this number let's say like a hundred or a thousand it
will get huge in seconds . You also have an issue where when you're doing recursion you have to
consider a recursion depth. The more nested you go the longer the recursion steps are,
the more resources you're going to have and issues with your memory. And you're going to
receive an error. That brings us to caching and recursion depth errors. We need to remember that
caching is using a temporary location to store our data. It's good because, the data less access
is fast. The problem is that memory is expensive, and if it's not in the cache memory. You have to
decide where to store it. And this can be tricky. The amount of cache memory that you have is also
limited, so you have to manage these resources effectively. There's something called lru cache.
And that's dealing with accessing recently used events for your data, and getting rid of anything
that hasn't been used recently. It's a trick that you can use for recursion which is hogging
up your memory and your resources. A benefit of using this, is the fact that you're not having to
restore or recompute every step of the recursion with this. If you're using python it's good for
you to call this lru cache. It's a decorator that's allowing you to run the code from above,
not run every instance. And speed up your process. You have to consider one thing though, when you're
doing this its dealing with dictionaries, all right. And if you have a function,
you have to make sure that whatever you're calling is hashable. When i mention you have
this recursion depth exceeded error, which is really annoying. You could try importing something
like this and put a number inside of here. Let's put a number inside of here let's pretty big.
You have to understand that this is affecting the way that your data types are being handled with
your garbage collection. And the problem is that you're creating unnecessary copies. For instance,
with your immutable objects. And lastly something you should take into account: python doesn't have
a way to optimize tail recursion. For instance tail recursion, just think of your very last step
is calling your function call for the recursion and you're not doing any other operations within
your function other than setting it up to do the recursive call. If we run the same function for
the fibonacci and use our good old lru cache with our decorator we'll notice that we're
in the microseconds, instead of milliseconds now which helped us out. Because of this, think about
if we were using ff5 for the fibonacci sequence. Meaning that we wanted to return the fifth number
from the fibonacci sequence. Meaning that we have to go through this tree-like structure and at each
step we're splitting it in half, and splitting it in half. And if you notice something with the blue
lines, this is creating our duplicates and we're creating triplicates here. So your n minus 1 are
creating duplicates from our f, and our n minus 2 which is these is creating our triplicates. You
could avoid this right here. This, this whole computation. If you set this up differently.
For instance, you can use dynamic programming for this. But, we're not going to get into that today.
Let's look into doing some looping with the same thing. For instance why would we use
recursion versus looping? Sometimes you just have a situation where it's almost impossible
or extremely difficult to run the loop, and it's more favorable to do recursion. In this case
looping would be far better. If we look at the printout here, we're doing the same type of setup
our initial values here. And we're iterating through our numbers adding them together,
and just doing an update statement. And then getting the totals. While this simplifies our
process and completely speeds it up; let's look at some time complexity and space complexity for the
fibonacci sequence to get some ideas real quick. For instance in the recursive case we end up with
the big o notation of an exponential function. With the space complexity being linear and this
is because, of the split the splitting that you have for the branching okay. And the n, is coming
from the function call itself. No matter what we do with the iterating it's going to be linear. And
the great thing is; the space complexity is going to be constant no matter what. Like i said before,
if you wanted to make the recursion portion better: consider dynamic programming. I left
a link for this as always remember the code will be in the link in description below for my Github.
We can look at another example of doing sorting a list here. The base case is kind of hidden. But
it's inferred it's either a zero or a one. for your base case being true, and then we're calling in the
sorted portion to evaluate if our list is indeed sorted or not. To run through it if we haven't
reached the base case yet. Now i printed out two examples here, to show you how this is working
and it's just evaluating this simply. We can look at doing merge sort. Where the base case doesn't
seem like it's a straightforward event. But if anything is less than one, that's where the base
case happens merge which is nice. Because, at the division step you have a log n. Because at each
step you're cutting it in half. Basically, you're breaking it up or dividing partitioning your data
in half. And then iterating over each one of those pieces, and when you're recombining you're doing
an n comparisons. So you have an n log n for your worst case scenario. For the merge sort,
the base case you need at least one. And the recursive step, you're running the merge sort on
the left and right hand sides of your data. This right here, isn't the actual code. Just think of
it as like how the algorithm is kind of set up. Almost like pseudo code. We're calling in our
base case, we have our recursive calls here, where we're trying to sort each side the left and right
hand side of our list. Typically, you won't have to do this motivation by hand unless you're taking
an algorithms class. And you'll have to probably implement this as a class. Other than that,
this gives you an idea of how this can be used in the real world. And gives you a way to think about
some of the scenarios you can have this come up and kind of how you should approach it. I did an
example in a previous video where i had to parse some data, and i showed how you can use
a recursion function to deal with some json data. Such as this, where we were looking to see do we
have a dictionary. Do we have a list if we have it run a particular function and iterate through it,
for each one of those append everything together and call our new formed list with our data. And in
essence what we are doing is going through each level of the nested json data, and storing it
as every single key with the dot notation and then calling back or value that corresponds
to it. Because, when you're dealing with very nested data: sometimes you may want or need the
full extension for what you're dealing with. Just depends on your circumstance. But i wanted to just
express briefly some of the uses and ideas behind recursion and give you an idea of what to look
for what to avoid, how to implement. I hope this brought utility to someone. Please like,
share and subscribe. And if you subscribe turn on that notification bell. Hit me up on
instagram and twitter and if you thought this was useful considering going to buy me a coffee and
hitting up my name to help support this channel. I appreciate it, i'll see you in the next video. Bye