1
00:00:02,200 --> 00:00:02,930
Hello, everyone.

2
00:00:02,950 --> 00:00:09,010
So I hope we are getting better idea about recursion now, what we will do so we will solve many Aghajan

3
00:00:09,100 --> 00:00:11,140
problems so we can understand it better.

4
00:00:11,350 --> 00:00:11,720
OK.

5
00:00:11,740 --> 00:00:14,410
So today we will be solving Funaki serious problem.

6
00:00:15,280 --> 00:00:17,290
OK, Funaki cities.

7
00:00:18,940 --> 00:00:29,080
So what is happen, because it is so zero one one two three five eight, so this is a fable, I guess

8
00:00:29,080 --> 00:00:29,380
it is.

9
00:00:29,380 --> 00:00:30,210
Now, what is a fable?

10
00:00:30,290 --> 00:00:34,340
Because it is so in the Fibonacci series, the first two numbers are fixed.

11
00:00:34,930 --> 00:00:38,590
Now, if you want to calculate any number, that will be the sum of the previous to number.

12
00:00:38,920 --> 00:00:42,580
So for calculating when what we will do, we will add the previous two numbers.

13
00:00:42,940 --> 00:00:44,680
OK, so zero plus one is one.

14
00:00:45,070 --> 00:00:46,410
We want to find this number.

15
00:00:46,420 --> 00:00:48,820
So it will be the addition of previous to numbers.

16
00:00:49,420 --> 00:00:51,280
OK, we want to find this number.

17
00:00:51,280 --> 00:00:53,760
So it will be the addition of previous to numbers.

18
00:00:54,430 --> 00:00:57,340
We want to find it so addition of previous to number.

19
00:00:58,300 --> 00:01:05,740
So what is it addition of previous to a number now the series will continue, so eight plus five, 13,

20
00:01:06,010 --> 00:01:09,260
13 plus eight, this will be 21, 21, plus 13.

21
00:01:09,280 --> 00:01:10,960
This will be 34 and so on.

22
00:01:11,290 --> 00:01:12,880
OK, so what is our aim?

23
00:01:12,880 --> 00:01:15,260
Our aim is to find a net Fibonacci number.

24
00:01:15,820 --> 00:01:18,790
OK, we have to find a net Fibonacci number.

25
00:01:19,300 --> 00:01:22,020
So let's call it zero Fibonacci number.

26
00:01:22,390 --> 00:01:25,780
Let's call it first Fibonacci number and so on.

27
00:01:26,000 --> 00:01:32,160
OK, so if I want to calculate sixth Fibonacci number, so tell me sixth number.

28
00:01:32,200 --> 00:01:33,390
So this is zero.

29
00:01:33,760 --> 00:01:34,440
This is zero.

30
00:01:34,630 --> 00:01:37,930
This is first, second, third, fourth, fifth and sixth.

31
00:01:38,350 --> 00:01:40,390
So sixth number will be eight.

32
00:01:40,780 --> 00:01:44,800
OK, so first off, six is eight.

33
00:01:45,460 --> 00:01:47,080
Six for number is it.

34
00:01:47,740 --> 00:01:50,310
OK, so we have to find a net.

35
00:01:50,320 --> 00:01:53,720
We will not get them, but our goal is to find a net for them.

36
00:01:53,740 --> 00:01:56,200
But basically I want to do something like this.

37
00:01:56,650 --> 00:02:01,150
So if you want to call grid and network number, it will be there the previous to.

38
00:02:02,030 --> 00:02:03,700
That is a net minus one.

39
00:02:04,700 --> 00:02:08,419
And and that's minus no end and net minus two.

40
00:02:09,139 --> 00:02:13,040
OK, so some of the previous two Fibonacci number.

41
00:02:13,530 --> 00:02:17,670
OK, so this is how we will be able to calculate and that's what we're not going number.

42
00:02:18,040 --> 00:02:19,940
OK, and we can see this is recursion.

43
00:02:20,150 --> 00:02:24,260
If I want to solve a bigger problem then I have to solve a smaller problem.

44
00:02:24,650 --> 00:02:27,470
OK, so let's write code for it.

45
00:02:28,070 --> 00:02:29,780
And these two are fixed.

46
00:02:29,930 --> 00:02:30,320
OK.

47
00:02:31,280 --> 00:02:37,610
First religious of the first two numbers of the Fabianski says they are fixed, they are zero and one.

48
00:02:38,030 --> 00:02:40,700
OK, so we have to use this formula.

49
00:02:41,580 --> 00:02:45,160
And that's what talking about is the sum of previous two people not get no.

50
00:02:45,770 --> 00:02:47,760
OK, so let's write the code for this.

51
00:02:48,690 --> 00:02:53,430
So we will think only in terms of BMI, so what a letdown by Britain that will be in.

52
00:02:53,970 --> 00:02:57,870
I have to return in the name of the functionalism it will take.

53
00:02:58,500 --> 00:03:00,360
We have to find a network in a month.

54
00:03:00,420 --> 00:03:02,090
It will take our indigenous input.

55
00:03:02,520 --> 00:03:05,880
Now, first of all, what we have to do best case, OK?

56
00:03:07,490 --> 00:03:11,390
So first is basic, is basic, is the smallest problem, the solution?

57
00:03:11,420 --> 00:03:12,030
We already know.

58
00:03:12,410 --> 00:03:13,010
So if.

59
00:03:13,010 --> 00:03:13,730
And is zero.

60
00:03:14,710 --> 00:03:18,300
So what is the number, the number is zero only.

61
00:03:18,360 --> 00:03:18,760
OK.

62
00:03:20,820 --> 00:03:22,080
Now it's time for the.

63
00:03:22,770 --> 00:03:24,000
OK, recursive case.

64
00:03:27,260 --> 00:03:29,150
So we have to recursive case here.

65
00:03:29,270 --> 00:03:33,200
OK, so small output one and small output to.

66
00:03:36,220 --> 00:03:40,090
So what will be small output, one, so small output will be?

67
00:03:41,800 --> 00:03:46,840
And minus one Fibonacci number, and that's minus one, two and number and small output will be.

68
00:03:49,120 --> 00:03:49,780
It will be.

69
00:03:51,550 --> 00:03:54,790
And minus two, not going to buy a net minus second for.

70
00:03:55,600 --> 00:03:58,420
OK, now it's time for the calculation.

71
00:04:01,250 --> 00:04:02,950
OK, so in conclusion, what do you do?

72
00:04:03,140 --> 00:04:04,010
I have to return.

73
00:04:06,700 --> 00:04:09,330
Submission of small output one and small output two.

74
00:04:10,220 --> 00:04:15,640
OK, so this is very simple and now we have to call this function.

75
00:04:15,640 --> 00:04:17,829
Let's say I want to calculate Toadfish when I can.

76
00:04:17,829 --> 00:04:18,170
No.

77
00:04:18,310 --> 00:04:18,640
OK.

78
00:04:19,680 --> 00:04:21,029
I want to 131.

79
00:04:21,209 --> 00:04:21,570
No.

80
00:04:21,920 --> 00:04:23,500
OK, so this is our computer.

81
00:04:23,700 --> 00:04:26,100
Now, if we will run this code, we will get error.

82
00:04:26,340 --> 00:04:30,630
OK, so let's first try to learn the score and then I will explain you what will be their.

83
00:04:34,490 --> 00:04:38,460
So there will be same so that it is segmentation, fault error.

84
00:04:38,480 --> 00:04:42,730
OK, so just like in the factorial, we are having infinite loop here.

85
00:04:43,430 --> 00:04:46,460
Now, let us try to pretend our goal to understand the problem.

86
00:04:46,940 --> 00:04:51,920
OK, so the problem is seem like we get in the factorial infinite loop problem.

87
00:04:52,550 --> 00:04:54,930
Now I want to calculate Fibonacci number three.

88
00:04:55,010 --> 00:04:57,140
OK, so let's write a novel code.

89
00:04:57,650 --> 00:04:58,770
So I have three.

90
00:04:59,240 --> 00:05:00,730
So what what will happen?

91
00:05:01,100 --> 00:05:02,270
I am calling on to.

92
00:05:03,670 --> 00:05:10,870
We will call on when when will call on zero now and zero, so it will return zero.

93
00:05:10,930 --> 00:05:14,260
So from here, let's circle all this.

94
00:05:16,030 --> 00:05:23,760
OK, so these are the values often these are the values of so and zero, when it is returning our back

95
00:05:23,770 --> 00:05:24,720
is OK.

96
00:05:25,420 --> 00:05:27,130
So I will tangelo from here.

97
00:05:28,710 --> 00:05:32,610
OK, now, after this cold, this line will be executed.

98
00:05:32,640 --> 00:05:34,890
So when will call on minus one?

99
00:05:36,540 --> 00:05:44,550
OK, then minus one will call on minus two, minus two will go on minus three, minus three will go

100
00:05:44,670 --> 00:05:49,020
on minus four and so on, basically this will become infinite loop.

101
00:05:49,030 --> 00:05:49,980
It will never stop.

102
00:05:50,320 --> 00:05:56,100
OK, so what is happening here is obviously I want to if you want to calculate first, we're not going

103
00:05:56,170 --> 00:06:00,270
to recall on the previous two, so it will call on zero and minus one.

104
00:06:00,300 --> 00:06:01,800
OK, so this thing is obvious.

105
00:06:01,950 --> 00:06:03,420
It will call on the previous two.

106
00:06:03,820 --> 00:06:04,980
So this is obvious.

107
00:06:05,280 --> 00:06:06,960
But what will happen?

108
00:06:06,960 --> 00:06:07,830
It will never stop.

109
00:06:07,860 --> 00:06:12,030
OK, we are we will get infinite loop and other our love will never stop.

110
00:06:12,960 --> 00:06:14,220
OK, so what is the problem.

111
00:06:14,250 --> 00:06:21,600
Problem is I am making two jumps so I have to take two because we can see here I am making doorjambs

112
00:06:21,600 --> 00:06:24,390
and minus one and minus two since I am making to them.

113
00:06:24,400 --> 00:06:26,430
So I have to take two cases here.

114
00:06:26,590 --> 00:06:30,020
OK, and we know the first two are fixed.

115
00:06:30,270 --> 00:06:32,460
So first of all numbers are zero and one.

116
00:06:32,460 --> 00:06:34,650
So I have to add one more base case.

117
00:06:35,340 --> 00:06:37,830
OK, so the one more base case will be.

118
00:06:38,800 --> 00:06:39,790
If the value of.

119
00:06:40,930 --> 00:06:44,270
And is one, if I want to calculate the first Fibonacci number.

120
00:06:44,290 --> 00:06:47,650
So first number is fixed and that is one only.

121
00:06:48,060 --> 00:06:51,430
OK, now if we will run our code of a quarter million, fine, OK?

122
00:06:51,460 --> 00:06:52,780
So I want to calculate the third.

123
00:06:52,950 --> 00:06:55,770
We're not let us see what will be our output.

124
00:06:57,680 --> 00:07:00,620
So our output is coming out to be two, which is correct.

125
00:07:00,950 --> 00:07:03,830
OK, now let's again bring our called.

126
00:07:06,150 --> 00:07:12,230
So our output was to and this is obviously zero and one, so zero plus one is one one plus one is two.

127
00:07:12,390 --> 00:07:14,180
So this is the third Fibonacci number.

128
00:07:14,220 --> 00:07:16,740
So this is our output and our output is correct.

129
00:07:17,040 --> 00:07:20,850
OK, now let's try to try another gold and see what is happening.

130
00:07:21,150 --> 00:07:23,480
So I want to calculate Fibonacci number.

131
00:07:23,910 --> 00:07:27,050
So this is terrific, but I want to convert it.

132
00:07:27,570 --> 00:07:29,580
But now I will come here.

133
00:07:30,530 --> 00:07:39,720
OK, so this tree will call on two and this is waiting at line number fifteen, OK, and the value of

134
00:07:40,110 --> 00:07:41,760
three is waiting in line number fifteen.

135
00:07:42,120 --> 00:07:44,880
So what will happen to will call on when.

136
00:07:45,990 --> 00:07:50,070
No one is our base case, so what will happen, I will return one from here.

137
00:07:50,430 --> 00:08:01,170
OK, so this will return when so our small output one is one, OK, now it will call now two will call

138
00:08:01,170 --> 00:08:03,530
on minus two, so two will call on zero.

139
00:08:04,830 --> 00:08:07,470
Now, zero is also a base case, so it will return zero.

140
00:08:08,360 --> 00:08:09,620
It will return also.

141
00:08:09,630 --> 00:08:17,300
This is our small output to show our small output to is zero and then our calculation part, I have

142
00:08:17,300 --> 00:08:18,800
to return the addition of these two.

143
00:08:19,310 --> 00:08:20,750
So zero plus one is one.

144
00:08:20,960 --> 00:08:22,010
So two will return.

145
00:08:22,340 --> 00:08:23,120
One, two, three.

146
00:08:23,690 --> 00:08:25,280
OK, now what will happen?

147
00:08:26,090 --> 00:08:28,050
Three was waiting at line number 15.

148
00:08:28,610 --> 00:08:30,440
Now it will call on line number 16.

149
00:08:30,740 --> 00:08:32,360
So it will call on when.

150
00:08:33,530 --> 00:08:37,039
OK, when is the best case, so it will be one.

151
00:08:39,400 --> 00:08:46,630
OK, so this one, it was our small output, one salis, one output one is one and this one is our small

152
00:08:46,630 --> 00:08:47,230
output two.

153
00:08:47,560 --> 00:08:49,960
So small output two is also one.

154
00:08:50,200 --> 00:08:54,370
And then I am returning the addition of these two small children, plus more output do.

155
00:08:54,910 --> 00:08:56,540
So I will return the addition of these two.

156
00:08:56,560 --> 00:08:57,880
So one plus one is two.

157
00:08:58,240 --> 00:08:59,650
So three will return to.

158
00:09:00,940 --> 00:09:04,540
OK, so two will come here and then we are printing two.

159
00:09:04,570 --> 00:09:05,800
So, too is our answer.

160
00:09:05,830 --> 00:09:08,080
OK, so that's how this code is working.

161
00:09:09,700 --> 00:09:13,810
OK, so one thing that I want you to do is think of all this.

162
00:09:17,950 --> 00:09:23,950
So one thing that I want you to do is think of all this after writing the code, OK, violating the

163
00:09:23,950 --> 00:09:31,030
code, think only in terms of PMI, OK, you have to think about this diagram after writing the code,

164
00:09:31,480 --> 00:09:33,970
after writing the code, you have to take out this diagram.

165
00:09:34,000 --> 00:09:38,890
OK, so I suggest you do try it in the code by making this diagram.

166
00:09:39,220 --> 00:09:42,280
But first write the code without thinking of this diagram.

167
00:09:42,310 --> 00:09:43,680
OK, I'm repeating myself.

168
00:09:44,140 --> 00:09:49,200
So first I have to write the code thinking only in terms of PMI.

169
00:09:49,960 --> 00:09:52,420
And second, we have to try it in our code.

170
00:09:52,420 --> 00:09:55,660
And when we're done in our code, we have to make this diagram.

171
00:09:56,050 --> 00:09:58,120
OK, so first write code.

172
00:09:58,120 --> 00:10:04,680
Second that in the code by making this diagram, OK, you do not have to think of this diagram first.

173
00:10:05,110 --> 00:10:06,130
So this is second.

174
00:10:06,250 --> 00:10:08,080
We have to tangoed this diagram later on.

175
00:10:08,080 --> 00:10:10,930
First we have to write the code and violating the code.

176
00:10:10,930 --> 00:10:12,630
We have to tangle in terms of PMI.

177
00:10:12,910 --> 00:10:14,380
So first, the best case.

178
00:10:14,470 --> 00:10:17,740
Second, the recursive case and third, the calculation part.

179
00:10:18,250 --> 00:10:20,950
OK, so I hope you understood this problem.

180
00:10:22,310 --> 00:10:23,780
OK, thank you.

