Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
00:00:00,740 --> 00:00:02,660
All right, all right.
2
00:00:02,680 --> 00:00:10,630
Welcome back, ladies and gentlemen, to another very, very interesting topic in our programming course.
3
00:00:11,080 --> 00:00:14,110
And these topic is called Recursions.
4
00:00:14,710 --> 00:00:25,300
So maybe some of you heard of these scary terminology during different different lectures in school
5
00:00:25,300 --> 00:00:27,310
or a college or university.
6
00:00:27,310 --> 00:00:28,510
I don't know.
7
00:00:28,930 --> 00:00:36,280
It doesn't really matter because together we are going to study and to learn from scratch and we are
8
00:00:36,280 --> 00:00:43,780
going to solve plenty of examples to make sure that this concept is clear to us and that we are ready
9
00:00:44,020 --> 00:00:48,640
to solve different exercises on our own.
10
00:00:48,710 --> 00:00:51,080
OK, so no worries about it, guys.
11
00:00:51,460 --> 00:00:54,730
What I want to ask you is very, very simple thing.
12
00:00:54,740 --> 00:00:58,050
OK, I want you to stay calm.
13
00:00:58,450 --> 00:01:00,160
I want you to relax.
14
00:01:00,700 --> 00:01:04,180
I want you to take three breaths, OK?
15
00:01:04,180 --> 00:01:12,100
So take a deep breath and breathe it out and do these two more times.
16
00:01:13,780 --> 00:01:26,830
So in and out and once again, in and out, OK, because these can really be intimidating.
17
00:01:26,830 --> 00:01:28,690
And I don't want you to panic.
18
00:01:28,930 --> 00:01:31,360
It's going to be all right.
19
00:01:31,930 --> 00:01:38,890
So get yourself ready and let's start our journey with the recursions concept.
20
00:01:39,110 --> 00:01:39,940
Let's go.
21
00:01:41,140 --> 00:01:45,500
So first of all, what is a recursion?
22
00:01:45,550 --> 00:01:48,940
OK, so what is a recursion first?
23
00:01:49,810 --> 00:01:54,120
Basically in recursion is just a concept, OK?
24
00:01:54,550 --> 00:02:00,190
It is not some sort of a variable and it's not some data structure.
25
00:02:00,490 --> 00:02:03,070
It simply is a concept.
26
00:02:03,490 --> 00:02:10,540
Think of it as a new approach or a new way to solve different problems or different questions.
27
00:02:11,080 --> 00:02:17,260
In most in most cases, this will be done also in fewer lines of code.
28
00:02:17,860 --> 00:02:22,140
OK, so this is just a method for solving problems.
29
00:02:22,200 --> 00:02:23,860
OK, a new method.
30
00:02:24,860 --> 00:02:34,310
And as simple as it may sound, the idea of recursion is not so easy to understand at first, since
31
00:02:34,310 --> 00:02:36,880
it's not common for our minds.
32
00:02:37,610 --> 00:02:45,590
So that's exactly why I've decided to take some time and, you know, like to think about and trying
33
00:02:45,590 --> 00:02:54,110
to figure out how can I teach you guys this topic in such a way that you will not have to cry or break
34
00:02:54,110 --> 00:02:56,020
anything during the process.
35
00:02:56,660 --> 00:03:04,220
And I think I've found some way to how we can make some visualizations and general explanations so that
36
00:03:04,220 --> 00:03:11,180
now it will be much easier for you and much more fun for you to learn recursions.
37
00:03:11,330 --> 00:03:19,490
OK, so I've also been a student once and this process and this concept was not the easiest one.
38
00:03:19,820 --> 00:03:27,560
And I don't want you to like to have here a lot of hard time because I really think that things are
39
00:03:27,560 --> 00:03:32,290
not so complicated if they are being taught right.
40
00:03:32,520 --> 00:03:34,370
OK, so let's go.
41
00:03:35,700 --> 00:03:44,100
Let us proceed and OK, so we said that it's not common for our minds, but basically all of that is
42
00:03:44,100 --> 00:03:46,680
kind of nice, but how to think about it?
43
00:03:47,280 --> 00:03:49,650
I want you to start with a simple example.
44
00:03:50,070 --> 00:03:53,280
Suppose we've got some problem, let's call it.
45
00:03:53,280 --> 00:03:59,840
I don't know, the original problem, some question or problem that we simply want to solve.
46
00:04:00,570 --> 00:04:08,610
For example, we want to find the sum of all integer numbers from one up to some given em.
47
00:04:08,830 --> 00:04:19,140
OK, so if M, for example, is five, OK, if an equals to five, then we are looking to find the sum
48
00:04:19,140 --> 00:04:22,140
of all numbers starting from one.
49
00:04:22,320 --> 00:04:29,220
OK, up to a given N which is currently in this example is just five.
50
00:04:30,870 --> 00:04:40,350
And that means that we need to calculate this sum of one plus two plus three plus four plus five, which
51
00:04:40,350 --> 00:04:43,610
will give us a total of 15, correct.
52
00:04:44,640 --> 00:04:48,200
And now let's consider and think of these problem, OK?
53
00:04:48,210 --> 00:04:59,400
Because currently these problem can be also cold is the regional problem or the main problem and call
54
00:04:59,400 --> 00:05:02,020
it as some up to five.
55
00:05:02,040 --> 00:05:04,560
OK, that's the naming for these problem.
56
00:05:04,570 --> 00:05:10,820
OK, well, simply naming it just some up to five, some all integer numbers from one up to five.
57
00:05:11,310 --> 00:05:12,370
Is that clear so far.
58
00:05:13,050 --> 00:05:21,330
So in order to solve the sum up to five problem, which is the original problem, the bigger problem,
59
00:05:23,910 --> 00:05:31,980
in order to calculate all the numbers from one up to five, we are basically going to sum up one and
60
00:05:32,370 --> 00:05:36,480
two, OK, and then take the sum of them, which is three.
61
00:05:36,840 --> 00:05:41,940
In sum it up with the number three, which will give us a total of six.
62
00:05:42,330 --> 00:05:46,030
And then once again, we will take this sum so far.
63
00:05:46,080 --> 00:05:53,550
OK, the sum that we have so far and add to it for OK, which will be a total of ten.
64
00:05:54,090 --> 00:06:03,060
So we know that the sum of all the numbers between one up to four will give us a total of ten and then
65
00:06:03,090 --> 00:06:10,410
we will add five and we will get the total of five, which is the sum of all integer numbers from one
66
00:06:10,410 --> 00:06:11,190
up to five.
67
00:06:11,220 --> 00:06:18,010
OK, so that's probably how most of us would have solved this question in their mind.
68
00:06:18,080 --> 00:06:21,720
OK, so let me just show you this once again.
69
00:06:21,720 --> 00:06:23,320
Where is this Pam?
70
00:06:23,730 --> 00:06:26,940
Let me get it light blue and let's get the pen done.
71
00:06:26,970 --> 00:06:29,670
OK, so that's basically.
72
00:06:29,850 --> 00:06:32,750
Oops, come again, again, again.
73
00:06:32,760 --> 00:06:33,890
So there is the pen.
74
00:06:34,170 --> 00:06:36,620
So that's basically sum up to one.
75
00:06:36,630 --> 00:06:40,080
OK, so I will call it, I don't know, s for one.
76
00:06:41,280 --> 00:06:44,280
And that's the sum up to two, right?
77
00:06:44,300 --> 00:06:48,060
So as up to two, and that's to sum up to three.
78
00:06:49,010 --> 00:06:57,260
So if you've noticed, like in this example right here, that basically what happened here is that what
79
00:06:57,260 --> 00:07:04,910
was done is that we simply divided the main problem, which is some up to five, the bigger problem
80
00:07:04,910 --> 00:07:07,320
into solving some smaller Isaw problems.
81
00:07:07,340 --> 00:07:12,590
OK, so first of all, we found out what is the sum of sum up to one.
82
00:07:13,130 --> 00:07:19,100
And then we use this results to find the sum up to two, which simply was like take the sum up to one
83
00:07:19,430 --> 00:07:21,260
and add two.
84
00:07:21,680 --> 00:07:28,460
And then we found out the sum up to three, which simply relied on the fact that we have to take the
85
00:07:28,460 --> 00:07:32,900
sum up to two, which is the fraction, and add three to it.
86
00:07:32,930 --> 00:07:39,510
OK, so simply dividing the main problem of sum up to five into some smaller sub problems.
87
00:07:39,530 --> 00:07:41,690
OK, so that's how we did it.
88
00:07:43,010 --> 00:07:50,270
Now we will try to think of a way to divide these original problems into some smaller problems, OK?
89
00:07:51,200 --> 00:07:54,580
And that's basically the whole new method of thinking.
90
00:07:54,590 --> 00:07:57,740
OK, let me show you in more depth exactly what I mean.
91
00:07:58,640 --> 00:08:02,850
Basically, that's the point where most of the students get stuck.
92
00:08:02,900 --> 00:08:05,870
OK, while they are starting recursion.
93
00:08:06,290 --> 00:08:14,390
So please concentrate very much on what I'm about to say right now, because it has a crucial influence
94
00:08:14,390 --> 00:08:22,010
on your understanding of this topic for from beginners level to the expert level.
95
00:08:23,550 --> 00:08:31,650
So we have to think about the following question, OK, when working with recursions, can we solve
96
00:08:31,650 --> 00:08:33,300
the original problem?
97
00:08:33,300 --> 00:08:40,390
The bigger problem, if we were to have divided and solve some smaller problems.
98
00:08:40,660 --> 00:08:46,830
OK, and if we can, can we do it on some regular basis?
99
00:08:47,100 --> 00:08:55,950
I mean, if we can divide our original problem into some smaller sub problems and these smaller solve
100
00:08:55,950 --> 00:09:02,430
problems into further some problems and so on and based on the result of each of the sub problems,
101
00:09:02,850 --> 00:09:10,160
it will simply help us to conclude and construct the result for the bigger problem.
102
00:09:10,200 --> 00:09:16,500
OK, so if we can do it, that means we can use a recursion as a solution.
103
00:09:17,460 --> 00:09:24,000
So we will take some problem and start dividing it into smaller and smaller sub problems.
104
00:09:25,260 --> 00:09:32,970
And if we could do this, this division thing, until this problem gets to the point where the solution
105
00:09:32,970 --> 00:09:40,440
can be found kind of trivially, OK, if we have trivial solution, then if we reach to this point,
106
00:09:40,470 --> 00:09:45,690
we can start building our way up and conclude different conclusions.
107
00:09:45,690 --> 00:09:53,250
And different calculations are results that will help us with finding the result for your regional problem.
108
00:09:53,860 --> 00:09:55,770
OK, don't worry, guys.
109
00:09:55,770 --> 00:10:00,730
We will soon see some examples and everything will become more clear to you.
110
00:10:00,750 --> 00:10:12,180
OK, I'm just trying to build our way up and make sure that none of you will will basically have difficulties
111
00:10:12,180 --> 00:10:12,560
here.
112
00:10:12,670 --> 00:10:21,330
OK, so just one node for what I mean when I'm saving saying trivial solution is they are basically
113
00:10:21,330 --> 00:10:29,700
trivial or a straightforward solution simply means that some bigger problem was divided into some smaller
114
00:10:29,700 --> 00:10:36,900
problems and these smaller solve problems were divided, so on and so forth.
115
00:10:37,200 --> 00:10:47,180
And basically it has come to a point where these some small problem so trivial that the solution is
116
00:10:47,240 --> 00:10:49,960
like, I can give you the answer right away, OK?
117
00:10:49,980 --> 00:10:57,000
So, for example, sum up to one from one, you know that it's so trivial that the result is one, but
118
00:10:57,000 --> 00:11:00,870
some up to five or some up to 10 is not so trivial.
119
00:11:00,870 --> 00:11:08,590
You have to make some calculations and it's a process that can be divided to some smaller sub problems.
120
00:11:09,690 --> 00:11:10,270
Awesome.
121
00:11:10,320 --> 00:11:13,880
So these were the main things for understanding recursion.
122
00:11:14,460 --> 00:11:22,020
It is simply a process of dividing our problem into sub problems and these are problems into sub sub
123
00:11:22,020 --> 00:11:27,450
problems and so on until we reach some terminating mostly trivial condition.
124
00:11:28,260 --> 00:11:34,410
So we can say that the recursion can be used whenever a problem can be solved by dividing it into smaller
125
00:11:34,410 --> 00:11:40,230
problems and repeating some similar process for the smaller problems.
126
00:11:41,520 --> 00:11:50,640
And now let us see a couple of cool Real-Life examples that demonstrate at least somewhat of a usage
127
00:11:50,640 --> 00:11:57,450
of recursions, although that's not proper programming, it's also nice to take a look at it.
128
00:11:58,170 --> 00:12:01,560
So, first of all, let's talk about the Russian doll.
129
00:12:01,600 --> 00:12:09,240
OK, Sue, who is not familiar with the Russian doll, that's a classic example to recursions.
130
00:12:09,390 --> 00:12:12,200
You simply have the bigger doll, OK?
131
00:12:12,570 --> 00:12:20,100
And if you want to find out how many subadults, how many smaller dolls there are within it, you simply
132
00:12:20,100 --> 00:12:26,100
start to unpack two smaller dolls, OK, to smaller sub problems.
133
00:12:26,760 --> 00:12:34,320
And this is done until you reach some point where you cannot divide the Russian doll anymore, which
134
00:12:34,320 --> 00:12:38,290
is basically considered to be the trivial solution.
135
00:12:39,150 --> 00:12:41,510
So that's an example, number one.
136
00:12:41,540 --> 00:12:48,390
OK, so we have the bigger problem and we also have some smaller problems until we reach some trivial
137
00:12:48,390 --> 00:12:50,720
solution where we can not divide it any further.
138
00:12:50,940 --> 00:12:56,460
And we know that, OK, now we have like one and let's build our way up, OK?
139
00:12:57,000 --> 00:13:00,530
And a second option is like a dream inside a dream.
140
00:13:00,540 --> 00:13:05,580
You know, the times when you dream, a dream where you dream, a dream where you dream, a dream and
141
00:13:05,580 --> 00:13:08,130
so on in some recursive manner.
142
00:13:08,260 --> 00:13:12,450
OK, so that's also kind of an example.
143
00:13:12,870 --> 00:13:17,360
Also, we have like counting folders in the computer.
144
00:13:17,730 --> 00:13:24,270
OK, so there is a folder inside, a folder inside of folder until you reach some folders that don't
145
00:13:24,270 --> 00:13:26,760
have any folders inside of them.
146
00:13:28,700 --> 00:13:35,750
Also, something that you can also try is simply writing down recursion in Google.
147
00:13:35,810 --> 00:13:38,050
OK, so write down recursion.
148
00:13:38,090 --> 00:13:39,110
OK, my bad here.
149
00:13:39,110 --> 00:13:42,890
I forgot to add these parentheses.
150
00:13:42,890 --> 00:13:44,910
Here are a parentheses, I'm saying.
151
00:13:46,070 --> 00:13:53,650
So basically go go to Google and type down recursion, a link that opens the same page over and over.
152
00:13:53,780 --> 00:13:55,460
That's what you're going to see.
153
00:13:56,000 --> 00:14:00,910
It's a cool feature of Google, at least for the moment that I recorded this video.
154
00:14:01,700 --> 00:14:07,340
And there was a lot of other interesting problems that remind us of the recursion concept.
155
00:14:08,420 --> 00:14:17,780
But for now, simply remember the main of the main idea, the main understanding of recursions, that
156
00:14:17,780 --> 00:14:19,340
it has a bigger problem.
157
00:14:19,550 --> 00:14:22,580
This bigger problem can be divided into smaller problems.
158
00:14:23,300 --> 00:14:30,710
And yeah, and basically when you divide it into smaller problems, there is at least there should be
159
00:14:30,980 --> 00:14:39,170
some stopping conditions, some trivial solution that from this point on this mechanism should start
160
00:14:39,290 --> 00:14:46,820
stop making these calls for the division of sub problems and it should basically build its way up and
161
00:14:46,820 --> 00:14:52,800
build the result for the final problem based on the results of the sub problems.
162
00:14:53,360 --> 00:14:55,580
So that's about the theory.
163
00:14:55,590 --> 00:15:03,920
And now I think we can take a look at a couple of examples and to see how they will look like when we
164
00:15:03,920 --> 00:15:08,460
are going to work with practical examples and code.
165
00:15:08,630 --> 00:15:12,830
So I hope you are ready, guys, because here we go.
17086
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.