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.