This video we are going to talk about a
very important concept in computer
science called recursion
and I will explain it in a way that even
a high school student can understand it
easily. We'll go over some theory and
then we'll write
some recursion code in python. So let's
start let's say there are a couple of
people waiting
outside pizza store for their pizza
delivery.
Now the owner of the store Roberto
realizes that people are getting bored
standing in the queue
so he offers garlic bread to each of
them
as a compliment. The first person in the
queue gets 1 garlic bread,
second person gets 2 garlic bread, I
don't know why Roberto came up with this
rule.
but maybe he thought that person
standing in the end
will be more bored so maybe give them
more reward.
Now his chefs are working very hard but
still there is a delay
so Roberto offers one more discount
saying that
you know let me ask these people to do
some activity or some puzzle so that
they don't get bored waiting in the
queue. So he will say okay
every person in the queue needs to count
total number of breads
that are in front of them including
their own breads.
Once you give that answer you will get
10% discount.
So for example for ro it will be 6
because he has 3 breads there are 2 so 3
and 2 5
and 1 6. it's a simple math basically
simple sum of
all the breads which are prior to you so
for Shayla it will be
4 and 3 7 and 2 9 and
1 10 so
4, 3, 2, 1 you just do a simple
sum.
So then these people can do this some
and on 10%
discount. Now Meera is actually very
smart.
she's smart as well as lazy. She's like
who's gonna do
all the sum you know 5, 4, 3.
Who's gonna do all of that
so let me ask Shayla for her answer.
So Meera will ask Shayla for her
answer
and then she can add her breads into
that.
And that will do the trick correct? She
can say 5
plus Shayla's answer which is a sum of all
these answers
that will be her final answer.
so then she goes "hey Shayla what is your
answer?"
then Shayla realizes oh that's a nice
trick!
Let me do that trick as well so she will
ask Aarav here are our body what's your
answer?
and same thing everyone will repeat
until Yana
and she'll be like "hey Madhav what is
your answer?" Now for Madhav it's pretty
straightforward. He has one bread
so Madhav's answer is one bread.
Now Yana can take the answer and then
she can add her breads into it.
So 1 plus 2 is 3. Then Aarav kid
they can take Yana's answer add his
breads.
3 plus 3 6. Simple math guys
and Gayle's
Meera can say 10 and plus my
my five breads 15. So
this approach of solving a
problem is called recursion. Yo!
you got it it's a very important concept
in computer science.
You are basically doing three steps in
this approach in the first step you
divided a bigger problem into
smaller and simpler problem. For Meera the
problem is simpler because
all she has to do is take ready-made
answer from Shayla
and add five breads into it same way
Shayla
take readymade answer from Aarav add
four breads to it.
And so on the criteria number 2
for recursion is the base condition so
here
Madhav's answer is 1 because Madhav
doesn't have any
anyone in in front of him so he can
just give his answer in a second. He's
like okay my answer is 1.
so that's the base condition with a
simple answer. So in recursion you
need you need to have that base
condition
and the third point here is once you
have the answer with base condition you
roll back that answer to all the way up
in the chain.
So now Yana will take Madhav's answer
which is one
she will add her two breads that is
3.
Aarav will add take Yana's answer which is
3 add his breads 3
6 and so on all the way till Meera
finds
her solution. So just to summarize
there are three steps into recursion. So
here
we solve a very basic math problem which
is
summing up all number from 1 to n
here n was 5 so to sum that up
you could have used iterative approach
which is 1 plus 2 plus 3 plus 4 over 5
but you have to do a lot of computation.
Instead, here you say
5 plus find the sum of all numbers
between 1 to 4.
then the second step is okay 4 plus find
sum of numbers between
1 to 3. Until you find a base condition
which is find a sum of
numbers from 1 to 1 and that's pretty
straightforward it is 1
Obviously. and once you have the answer
you roll back.
Now see here look at this line carefully
okay? Find sum of numbers 1 to 1 what is
it
well it is 1. substitute that 3
all right 3 is my answer. Now find the
sum of numbers 1 to 2.
what is it well it is this 3 so
substitute this 3
here at top you get 6. You keep on doing
that
till you get 15. Now let's write python
code for
same. I have opened my python community
edition and I have
this basic program that finds you the
sum of
all numbers from 1 to n. So for
5 we already saw in the presentation the
sum will be
15. Okay but this function is using
iterative approach it is not using a
recursion
so what I'm going to do is, first I will
go into my
meditation mode and then I will
write this same function using a
recursion okay?
so just to summarize this function can
be written in
two ways one is iterative approach which
is what you see on the screen
second is recursive approach, okay? So now
let's write that function what we saw
in recursive function was two criterias
one is the repetitive task that you are
doing and you are reducing the problem
to smaller and smaller problem
and the second one is the base condition
which will terminate your recursion.
So let's tackle the recursive
criteria first
so sum of n number is nothing but
n plus find sum of
n minus one right so we saw
Meera like her bread count is
her breads which is her answer is her
breads which is n
and then the answer that Shayla had you
know previously
so that is this condition now if you
just run the score it's gonna of course
go into infinite loop because you're not
terminating.
So you need base condition to terminate
now what is base condition. Well
one if n is equal to one
then you return one. Okay
so next let's run this code see
it executed it fine.
If you say 6
now the beauty about this code is it is
so simple and very intuitive to read.
It's just that you to be little careful
about infinite conditions when you are
writing recursive code
often if you are stuck in some problem
of what helps
is debugging. So let me just debug this
code
okay so I will do it for let's say 4
okay and if I run right click debug
it will show you the first call for n
equal to 4.
okay now watch this area this area the
stack will grow. So if you do f10
what will happen is now it will call
find some function for n equal to three
you see n equal to 3.
and you see two calls now here the first
call was n equal to 4
second call is n equal to 3.
When you go deep down it will keep on
calling it.
See I have enough four calls in my stack
n equal to 4, 3, 2, 1. Now when I
hit
1, i'm hitting a base condition and it
will return from here.
So when it returns now I'm unwinding my
stack.
This is called stack unwinding. Okay? And
this function would have returned value
one so now I have n equal to two
so two and one so I'll get 3. Okay?
Then I go back again so I'm
unwinding okay now I'm back to 4 so
back to 4.
so 4. and the find some value of 3
will be what?
3 2 5 and 1 6 so 6
and 4 10 so now when I go back here
10 is printed
let's look at Fibonacci series problem
so f=Fibonacci series starts with 0 and 1
and then you generate new numbers using
the sum of last two numbers. So what is
the sum of 0 and 1
1 okay what is sum of 1 and 1
2 last two numbers you have to add so 2
and 1 is 3
2 and 3 is 4 2 and 3 is 5. Sorry
that's Fibonacci series and if you talk
about the indexes
okay so this is an index 0 this is 1
this is like error index
3 4 5 6
Okay so this will be fine 3 8
now i'm going to write a function called
Fib which will take n so this is the
Fibonacci number at
nth position okay so for example
if I do OOPs
so if I do fib so if I do
fib6 for example
at position 6. I have number eight so
this function should return me 8.
Okay so that's what we are going to do
now fibonacci series also is a recursive
problem because
at every step you are repeating the same
solution which is at any given position
you want to find out the sum of
previous two numbers and what is my base
condition.
Well my base condition is if fib
of n is zero then it is 0 if
n is 1 then it is 1 so let's take care
of
that condition so if n is 0 or
n is equal to 1 then you want to return
n okay
so if you call this function for
zero and one it's gonna print see it
printed zero for zero it printed zero
for one it will print one so my base
condition is satisfied
satisfied now let's write a recursive
condition which is
fibonacci number again is a number of
previous two numbers
which means n minus 1
plus n minus 2
and when i do 6 here
voila see 8. okay if I give 4.
I should get three so let's give 4.
You can run it for any number let's say
10 number. Like 10th number will be like
55.
Okay so you saw that the code looks
so simple and very intuitive you just
need to take care of infinite conditions
and all that
but otherwise the code is very intuitive
and in
computer science interviews they
generally ask
recursive questions so if you want to
become a good program or a crack
computer science interview you need to
have a very good understanding of
a recursive recursion.
Now I have this complete python data
structure and algorithm tutorial
playlist
where I covered actually binary search
okay?
And binary search can be solved using
recursion so if you
watch this video properly you will
get to know how binary search can be
solved using recursion so I'm gonna
quickly show you that code as well so
this is for binary search
using recursion so here you see binary
search
recursive. I'm calling it I'm calling the
same function within that same function
okay.
Binary search can be done using
iterative approach as well
but recursion is a second approach
that you can take
now if you don't know about binary
search I can I can quickly go
I mean I will suggest you watch that
video but it's simple like
you have a sorted array this is a sorted
array you want to find any number let's
say I'm searching for 32.
You start in the middle then you say
okay
21 is it less than 32 or greater than.
Okay it is less than
which means my number 32 has to be on
the right hand side
so my left hand side is ruled out see
they are all gray
then whatever arrow is left on the right
hand side.
You again take the middle and you
compare okay 32 is left or right
well it is on right so again left hand
side is ruled out
and then you find next citation you find
this number 32 and you realize that this
is also a recursive problem.
And for that reason we can use the
recursive methodology to solve this
problem easily.
Now i want you to work on some exercises
So i'm going to provide a link
of these exercises in video description
below w3 resources is a very good
website where you can practice the
python
or recursive problems. So here there are
various recursive problems given along
with the solution
but do not look at solution you know
what's going to happen if you look at
the solution directly.
It will create bad things you know on
your computer
your computer will have virus so
try to solve the problem on your own
first and then look at the solution
coding is like swimming if you just
watch my video you're not going to learn
it. You have to practice
so practice practice practice there are
11 exercises
so you practice those. And in the video
comment below
let me know if you have any question I
hope you like this simple video on
recursion.
If you did please give me that give me a
thumbs up that's my fees for this
session.
And share it with your friends who also
want to know about recursion.
Thank You