Hello all and welcome back.
So in this module we are now going to start with a new topic.
And the topic name is recursion.
Now recursion is going to be the most important topic in your data structures and algorithm journey.
This is the topic in which most students face a problem, because it is little different from the traditional
coding, which we have been doing till now, where we were given a particular problem.
And for that problem we used to write a function to get the answer.
The flow was very straightforward in front of us, something which we can imagine.
Now coming to recursion.
This is where I feel the real DSA journey starts, because using recursion we will be implementing lots
of data structures.
Going forward.
We will use recursion in linked list stack queues for all of your tree.
Most of the problem will be solved using recursion.
Along with that.
The second reason it is very important is that the topic dynamic programming question from which are
asked in many good companies like Google, Amazon, Goldman do ask questions from that.
And the base idea about dynamic programming also lies in recursion.
Now, many students face issue in dynamic programming.
The reason is that they have not understood recursion properly.
So my aim going forward in this module and the next three four module, which I'm going to specifically
discuss on recursion, is to make sure that I am able to get the whole idea of recursion across to you
by using lots of awesome visualization, helping you to dry run the code, helping you to understand
that what exactly happens behind the scene so that towards the end you will have no problem in solving
any question which is given on recursion, and your journey moving forward will be a lot smoother.
Okay, so great everyone!
Now let us start with this one thing which I would like to add here.
Initially, it might happen that you will face a little bit problem in understanding recursion, though
I have tried lots of him like things and have come up with the best way to explain recursion.
So don't give up.
Okay, these are the four modules which you have to make sure that you do.
Recursion is not a topic for anyone that it will be clear in the first go.
Okay, great.
So with that out everyone, now let us discuss.
Start our discussion on recursion.
Let me write that as well because I want all of you to remember this.
The most.
Important.
Topic.
Great.
So now let us start by discussing recursion.
Everyone.
But before we jump into recursion, I would like to just discuss or like explain you something about
functions.
So let us see the overall idea behind functions.
So let us.
Understand.
Few concepts.
On function.
And for that let us go to VS code once again.
So let me just write a code for this.
Now everyone, we have been writing lots of functions till now.
I'm pretty sure that you have been solving all those coding exercises in all of them.
You have to write a overall function where it gets called and some work gets done.
The basic idea behind function is to make sure that we can create a reusable block, okay, so that
we don't have to write the logic again and again, right?
So let us go to the code everyone.
And now what I have to do is I am writing a function def print.
NUM five okay I will be sending you something.
Sending you a number.
And what we have to do is print this number.
Right.
And now when I do print five.
So till now what I have done, I have just defined this particular function def print number five.
It just print whatever you send to it.
Print number five okay I'm just calling this overall simple function.
Now let us run this and we are able to see the output as five.
Now what I want to now change in this code is this particular thing to just use above function and a
single print statement.
To print out numbers from 5 to 1.
Okay, so I will repeat in a easy language.
I just want to now print from 5 to 1.
But I cannot change anything in this function.
You have to use this function only and you cannot print everything in this particular line.
No, I want to just use a single print statement.
Okay.
now, many of you might be thinking that we can do something like this.
So let me just use print number 543.
Okay.
Something like this all the way to one.
So let us have two.
Let us have one.
And now if I run this on the right side we can see the output is 54321.
But I just want to call this function once okay.
So I just want to call this function once.
So if I'm calling this without changing anything in this function right I just want to understand if
we can just get this output.
Great.
So maybe you can pause the video and think a little bit on this the way I would like to do this.
Okay.
You have asked me that I cannot change anything in this function.
Right?
But you have not said that I cannot define new function.
So nowhere I said that hey, don't define new function.
So what I'm going to do?
Everyone pay attention.
I'm just going to copy this whole function and paste it five times.
Okay.
So now we have five functions.
Let me just name them properly.
So for.
NUM three.
Two.
One okay.
And print number in each one of them.
Okay.
Let us just have one print num zero as well.
Okay.
Here we don't do anything.
We are just returning.
Great.
So there is a concept which I want all of you to explain.
It is that I can call a function within inside another function.
Right.
So I can make it num minus one.
I can make this three Okay now minus one.
Then I can do this.
Two num minus one.
Let me zoom it out so we can see the code.
Yeah.
One.
The minus one.
And finally, uh, maybe we can remove this.
I'm not calling anything.
Okay, so I will explain you what exactly happened.
Everyone.
So two things.
Actually, we have changed.
There was a condition, right?
There was a condition that I cannot use or call this function multiple times and just use a single print
statement.
So for that, what I did was I defined multiple functions.
As you can see in each of these function I called another function from inside okay.
This is something which we have been doing.
We can call a function from inside of another function.
Right.
That is something which we do all the time.
Even if you use this print, this print is also a function, right?
You are using it inside another function.
So now what I've done.
Everyone pay attention.
I have created these five functions.
Print them five all the way to one, 5 to 4, 5 to 2.
They each call another function in that.
And finally once get call.
Okay so let us run this and we are able to.
Let me just move everything.
We are able to get the same output 54321.
Maybe I can just clear this output once.
So let us have first this output clear.
And now if I just uncomment this yet you are able to see this overall output.
Okay great.
So that's the very first thing which we are able to do.
Everyone we just made some function call within a function.
Why I have done all this thing.
Because I want to make sure in your mind that you are comfortable that a function can call another function
from inside.
Great.
So let us talk a little bit more on what exactly would have happened, the way function flow or the
overall python would have worked right?
We have called this print num five.
So in the memory.
In the memory we would have created a this particular call to print num five.
The blocks get created for print number five.
It prints this particular number whichever you are giving it and then calls to four okay.
Then it calls to four.
Four again prints the number.
Then it calls two three.
One thing which I want all of you to understand is that five is still in the memory when it makes this
particular call, when it make this particular call, it still waits that whatever work this particular
print number four has to do, let it do.
And then I will go out of the memory, because if you remember each and every function, it just get
deleted from the memory when its work is done right.
So before that function stays in the memory.
So this last line, this overall last line, it is pushing the flow to another function.
Okay.
So to explain this in a very good manner, let us go to Python Tutor and see how exactly this will happen.
So let us code or just paste this everyone here.
And let us try to visualize this okay.
So let me just make the visualization.
So it is able to load okay.
Now let us see what exactly will the flow be.
This line first will get executed like all the functions are above.
So my code will have an idea that okay, a reference to this print number five function.
This function will still not get created in the memory, right?
So let us see that everyone let me just print next see in the global frame print num five, we have
this print num five that it knows Python has an idea that hey sum function print five is there.
Let us move forward.
Then let us move forward more in the end.
Right?
These five functions are defined.
Now I am calling print number five with the argument or parameter five.
Let us see this now everyone.
Now finally, this overall function gets created in the memory.
Print number five.
It will print the number.
As you will see.
It will print the number.
And now it's calling print num four.
But the thing which I want each and every one of you to understand, okay, is that this is still in
the memory.
This doesn't get deleted.
The reason for that, the simple reason for that is just that.
Let me zoom it in.
Simple reason is it work is not completed.
If a function work is not completed, then it stays in the memory, right?
Let us move forward and see what exactly will happen now.
So next three.
Then we will have two.
And finally we will have one.
Okay.
So we can see the one here as well.
See these are the five overall functions which I have called via My code when I call this function.
First five got invoked, so a block is created in the memory.
Then this call this print number four and it stays in the memory waiting for number four function to
complete its work.
Again, very important to understand this concept.
If you understand this once that hey, yes, the function remains in the memory until its work is done
and a function can call another function.
These are the two major getaways from this particular code.
Then you will have a good understanding of recursion going forward.
Now if I just move forward everyone because num one has completed its work, it is saying that I will
return none because again, we are not returning anything.
We just print it and it will get removed from the memory.
See, it got removed.
Now num two is saying okay, whatever work this particular function or line has to do, it has been
done.
My whole work is also completed so I can get deleted.
Three again is going to say the same thing.
Three gets deleted.
Four again going to see the same thing for gets deleted.
And now in the end, the last function getting deleted is the first one we called, which is print num
five.
It was waiting in the memory for print num four to do the work for was waiting on three three on two.
And we can just now come out.
And finally our flow is here and all the functions have done their work.
Okay, so pretty sure that this thing will be a lot clearer when we are just calling multiple functions
from a chain of functions, right?
So each and every function is calling another function and just waiting there.
Okay.
Great.
So if this thing is clear then there is another question.
Don't you think that we are doing a very similar work in each and every one of them?
Like if you will see, we are printing a number and we are just printing then calling another function.
Okay.
Which kind of does the same thing.
Okay.
So that's one more give one more get away from this particular thing.
So let us just write down few things which we have understood.
First.
We can call a function.
Function.
From inside.
Of another function.
Right, everyone.
That's the very first takeaway.
Second.
A function.
Stays.
In the memory.
Until it gets fully executed.
Okay.
All the things we have seen via visualization right now.
What I'm saying is I have two things.
First.
We are doing.
Almost similar.
Work in each of those functions.
Right?
Each of those function.
So can I say that okay, if it is doing the same work.
And I know that in programming I should not be repeating d I y principle.
Okay, there is a d I y principle which say do not repeat yourself.
Okay, on that note, if a function is doing the same thing, can I just call it again?
So that's the question which we need to understand.
Can a function.
Call itself.
Okay.
That's the function.
That's the question which we have to answer everyone something which we are going to discuss in the
next video.
But pretty sure that you get the idea that how the overall flow with respect to function is happening.