1
00:00:00,970 --> 00:00:05,830
In the previous video, we defined the two targets of part planning and how we are going to go about

2
00:00:05,830 --> 00:00:05,950
it.

3
00:00:06,310 --> 00:00:08,320
Focusing on first search for now.

4
00:00:08,470 --> 00:00:11,350
We mentioned something of a recursive implementation.

5
00:00:11,770 --> 00:00:14,560
Now what exactly is a recursive implementation?

6
00:00:14,890 --> 00:00:20,290
It is an algorithmic implementation that involves recursion instead of the normal iterative case we

7
00:00:20,290 --> 00:00:21,310
are used to daily.

8
00:00:21,850 --> 00:00:25,000
Now the question we need to answer is what is recursion?

9
00:00:25,690 --> 00:00:27,460
Let's start with the story.

10
00:00:30,170 --> 00:00:33,680
Imagine you just arrived at Starbucks for your morning coffee.

11
00:00:34,160 --> 00:00:40,490
The problem is, between you and your coffee, there is a long line of other morning coffee people.

12
00:00:41,120 --> 00:00:45,920
You love everyone to bits, but it won't be too bad if they just disappear.

13
00:00:46,580 --> 00:00:50,750
You don't like reading, especially when you don't know for how long.

14
00:00:51,530 --> 00:00:57,650
So you go up to each customer, starting from the front, and start asking, what's their order?

15
00:00:58,340 --> 00:01:02,000
You know, serve time for one cup and you know how to do the math.

16
00:01:02,600 --> 00:01:06,170
So your curiosity has been questioned, right?

17
00:01:07,040 --> 00:01:07,820
Yes and no.

18
00:01:08,630 --> 00:01:09,110
Yes.

19
00:01:09,380 --> 00:01:15,680
It does get you the answer you were looking for by going up to each person and asking who's order doing

20
00:01:15,680 --> 00:01:20,630
the math and adding previous wait time to correct till the last person.

21
00:01:21,670 --> 00:01:24,850
Did I mention going up to each customer and doing the math?

22
00:01:25,630 --> 00:01:26,530
It's morning.

23
00:01:27,070 --> 00:01:29,350
You don't want to do work before work.

24
00:01:30,410 --> 00:01:35,090
So you have an idea where you would get your answer by doing very little book.

25
00:01:35,690 --> 00:01:37,370
It is a recursive thought.

26
00:01:38,330 --> 00:01:40,610
You will understand what that is in a minute.

27
00:01:41,720 --> 00:01:45,980
You ask Mrs. Bink, how long will she have to wait to get served?

28
00:01:46,820 --> 00:01:50,660
Now, this question being personal to Mrs. Bing as she is herself.

29
00:01:50,660 --> 00:01:53,930
Concern of her wait time gets her curious.

30
00:01:54,710 --> 00:01:56,840
She asks the next person of his weight.

31
00:01:57,830 --> 00:02:02,030
This goes on until the first person that is out the counter.

32
00:02:02,690 --> 00:02:05,750
He knows his order and there is no guide before him.

33
00:02:06,230 --> 00:02:07,730
So he can just do the math.

34
00:02:08,420 --> 00:02:10,430
That is, he wants one lady.

35
00:02:10,520 --> 00:02:12,230
That would take around 3 minutes.

36
00:02:12,950 --> 00:02:15,470
So Mr. Red answer backs to Mr. Green.

37
00:02:16,040 --> 00:02:17,930
I would be waiting 3 minutes.

38
00:02:18,620 --> 00:02:21,260
Mr. Green knows his order and his weight time.

39
00:02:21,620 --> 00:02:22,230
He adds up.

40
00:02:22,250 --> 00:02:24,620
Mr. Ridgway, time to get total wait.

41
00:02:24,620 --> 00:02:28,100
Time till he gets up and tells to Mr. Orange.

42
00:02:28,850 --> 00:02:35,600
This process decreases back to Mrs. Bink, who estimates her weight time, and now you finally know

43
00:02:35,600 --> 00:02:38,480
how long you will have to wait before getting served.

44
00:02:39,020 --> 00:02:40,910
There it is, 24 minutes.

45
00:02:41,690 --> 00:02:46,850
That's enough time to do a quick match above cheap without worrying about missing coffee.

46
00:02:47,600 --> 00:02:47,960
Few.

47
00:02:50,570 --> 00:02:52,430
So that was the recursive thought.

48
00:02:53,090 --> 00:02:59,000
You divide down the problem into smaller sub problems by asking the next person office we we're done.

49
00:02:59,450 --> 00:03:06,170
Then this division went on until the fourth person which was the base condition as he knew exactly how

50
00:03:06,170 --> 00:03:07,310
long he will have to wait.

51
00:03:07,760 --> 00:03:10,250
So he answers back to the person before him.

52
00:03:11,060 --> 00:03:17,900
Then we wrote back this answer to solve the previous dilemma sub problem and solve all the problems

53
00:03:17,900 --> 00:03:21,050
eventually leads us to solving the original problem.

54
00:03:21,680 --> 00:03:22,880
So this is recursion.

55
00:03:23,030 --> 00:03:23,990
Easy, right?

56
00:03:24,740 --> 00:03:27,440
Let's see it in the form of a nice looking flowchart.

57
00:03:32,030 --> 00:03:37,700
So we start off by checking if we add the simplest case or the best condition.

58
00:03:38,750 --> 00:03:45,260
If not, then we simply divide our problem into simpler and smaller sub problems.

59
00:03:45,950 --> 00:03:50,990
This division goes on until we reach our simplest case.

60
00:03:52,080 --> 00:03:57,900
If we are at the simplest case, this is the second step and we simply return the solution to the base

61
00:03:57,900 --> 00:03:58,470
condition.

62
00:03:59,920 --> 00:04:05,380
Once we have the solution to the base condition, we roll back the answer to solve the previously lived

63
00:04:05,710 --> 00:04:06,370
problems.

64
00:04:06,880 --> 00:04:11,740
This is the third and the final step and eventually leads us to solving the original problem.

65
00:04:12,250 --> 00:04:12,800
That's it.

66
00:04:13,270 --> 00:04:15,340
You have learned all of recursion.