Original subtitles

All right, all right.

Welcome back, ladies and gentlemen, to another very, very interesting topic in our programming course.

And these topic is called Recursions.

So maybe some of you heard of these scary terminology during different different lectures in school

or a college or university.

I don't know.

It doesn't really matter because together we are going to study and to learn from scratch and we are

going to solve plenty of examples to make sure that this concept is clear to us and that we are ready

to solve different exercises on our own.

OK, so no worries about it, guys.

What I want to ask you is very, very simple thing.

OK, I want you to stay calm.

I want you to relax.

I want you to take three breaths, OK?

So take a deep breath and breathe it out and do these two more times.

So in and out and once again, in and out, OK, because these can really be intimidating.

And I don't want you to panic.

It's going to be all right.

So get yourself ready and let's start our journey with the recursions concept.

Let's go.

So first of all, what is a recursion?

OK, so what is a recursion first?

Basically in recursion is just a concept, OK?

It is not some sort of a variable and it's not some data structure.

It simply is a concept.

Think of it as a new approach or a new way to solve different problems or different questions.

In most in most cases, this will be done also in fewer lines of code.

OK, so this is just a method for solving problems.

OK, a new method.

And as simple as it may sound, the idea of recursion is not so easy to understand at first, since

it's not common for our minds.

So that's exactly why I've decided to take some time and, you know, like to think about and trying

to figure out how can I teach you guys this topic in such a way that you will not have to cry or break

anything during the process.

And I think I've found some way to how we can make some visualizations and general explanations so that

now it will be much easier for you and much more fun for you to learn recursions.

OK, so I've also been a student once and this process and this concept was not the easiest one.

And I don't want you to like to have here a lot of hard time because I really think that things are

not so complicated if they are being taught right.

OK, so let's go.

Let us proceed and OK, so we said that it's not common for our minds, but basically all of that is

kind of nice, but how to think about it?

I want you to start with a simple example.

Suppose we've got some problem, let's call it.

I don't know, the original problem, some question or problem that we simply want to solve.

For example, we want to find the sum of all integer numbers from one up to some given em.

OK, so if M, for example, is five, OK, if an equals to five, then we are looking to find the sum

of all numbers starting from one.

OK, up to a given N which is currently in this example is just five.

And that means that we need to calculate this sum of one plus two plus three plus four plus five, which

will give us a total of 15, correct.

And now let's consider and think of these problem, OK?

Because currently these problem can be also cold is the regional problem or the main problem and call

it as some up to five.

OK, that's the naming for these problem.

OK, well, simply naming it just some up to five, some all integer numbers from one up to five.

Is that clear so far.

So in order to solve the sum up to five problem, which is the original problem, the bigger problem,

in order to calculate all the numbers from one up to five, we are basically going to sum up one and

two, OK, and then take the sum of them, which is three.

In sum it up with the number three, which will give us a total of six.

And then once again, we will take this sum so far.

OK, the sum that we have so far and add to it for OK, which will be a total of ten.

So we know that the sum of all the numbers between one up to four will give us a total of ten and then

we will add five and we will get the total of five, which is the sum of all integer numbers from one

up to five.

OK, so that's probably how most of us would have solved this question in their mind.

OK, so let me just show you this once again.

Where is this Pam?

Let me get it light blue and let's get the pen done.

OK, so that's basically.

Oops, come again, again, again.

So there is the pen.

So that's basically sum up to one.

OK, so I will call it, I don't know, s for one.

And that's the sum up to two, right?

So as up to two, and that's to sum up to three.

So if you've noticed, like in this example right here, that basically what happened here is that what

was done is that we simply divided the main problem, which is some up to five, the bigger problem

into solving some smaller Isaw problems.

OK, so first of all, we found out what is the sum of sum up to one.

And then we use this results to find the sum up to two, which simply was like take the sum up to one

and add two.

And then we found out the sum up to three, which simply relied on the fact that we have to take the

sum up to two, which is the fraction, and add three to it.

OK, so simply dividing the main problem of sum up to five into some smaller sub problems.

OK, so that's how we did it.

Now we will try to think of a way to divide these original problems into some smaller problems, OK?

And that's basically the whole new method of thinking.

OK, let me show you in more depth exactly what I mean.

Basically, that's the point where most of the students get stuck.

OK, while they are starting recursion.

So please concentrate very much on what I'm about to say right now, because it has a crucial influence

on your understanding of this topic for from beginners level to the expert level.

So we have to think about the following question, OK, when working with recursions, can we solve

the original problem?

The bigger problem, if we were to have divided and solve some smaller problems.

OK, and if we can, can we do it on some regular basis?

I mean, if we can divide our original problem into some smaller sub problems and these smaller solve

problems into further some problems and so on and based on the result of each of the sub problems,

it will simply help us to conclude and construct the result for the bigger problem.

OK, so if we can do it, that means we can use a recursion as a solution.

So we will take some problem and start dividing it into smaller and smaller sub problems.

And if we could do this, this division thing, until this problem gets to the point where the solution

can be found kind of trivially, OK, if we have trivial solution, then if we reach to this point,

we can start building our way up and conclude different conclusions.

And different calculations are results that will help us with finding the result for your regional problem.

OK, don't worry, guys.

We will soon see some examples and everything will become more clear to you.

OK, I'm just trying to build our way up and make sure that none of you will will basically have difficulties

here.

OK, so just one node for what I mean when I'm saving saying trivial solution is they are basically

trivial or a straightforward solution simply means that some bigger problem was divided into some smaller

problems and these smaller solve problems were divided, so on and so forth.

And basically it has come to a point where these some small problem so trivial that the solution is

like, I can give you the answer right away, OK?

So, for example, sum up to one from one, you know that it's so trivial that the result is one, but

some up to five or some up to 10 is not so trivial.

You have to make some calculations and it's a process that can be divided to some smaller sub problems.

Awesome.

So these were the main things for understanding recursion.

It is simply a process of dividing our problem into sub problems and these are problems into sub sub

problems and so on until we reach some terminating mostly trivial condition.

So we can say that the recursion can be used whenever a problem can be solved by dividing it into smaller

problems and repeating some similar process for the smaller problems.

And now let us see a couple of cool Real-Life examples that demonstrate at least somewhat of a usage

of recursions, although that's not proper programming, it's also nice to take a look at it.

So, first of all, let's talk about the Russian doll.

OK, Sue, who is not familiar with the Russian doll, that's a classic example to recursions.

You simply have the bigger doll, OK?

And if you want to find out how many subadults, how many smaller dolls there are within it, you simply

start to unpack two smaller dolls, OK, to smaller sub problems.

And this is done until you reach some point where you cannot divide the Russian doll anymore, which

is basically considered to be the trivial solution.

So that's an example, number one.

OK, so we have the bigger problem and we also have some smaller problems until we reach some trivial

solution where we can not divide it any further.

And we know that, OK, now we have like one and let's build our way up, OK?

And a second option is like a dream inside a dream.

You know, the times when you dream, a dream where you dream, a dream where you dream, a dream and

so on in some recursive manner.

OK, so that's also kind of an example.

Also, we have like counting folders in the computer.

OK, so there is a folder inside, a folder inside of folder until you reach some folders that don't

have any folders inside of them.

Also, something that you can also try is simply writing down recursion in Google.

OK, so write down recursion.

OK, my bad here.

I forgot to add these parentheses.

Here are a parentheses, I'm saying.

So basically go go to Google and type down recursion, a link that opens the same page over and over.

That's what you're going to see.

It's a cool feature of Google, at least for the moment that I recorded this video.

And there was a lot of other interesting problems that remind us of the recursion concept.

But for now, simply remember the main of the main idea, the main understanding of recursions, that

it has a bigger problem.

This bigger problem can be divided into smaller problems.

And yeah, and basically when you divide it into smaller problems, there is at least there should be

some stopping conditions, some trivial solution that from this point on this mechanism should start

stop making these calls for the division of sub problems and it should basically build its way up and

build the result for the final problem based on the results of the sub problems.

So that's about the theory.

And now I think we can take a look at a couple of examples and to see how they will look like when we

are going to work with practical examples and code.

So I hope you are ready, guys, because here we go.