1 00:00:02,290 --> 00:00:02,940 Hello everyone. 2 00:00:02,950 --> 00:00:09,000 So I hope we are getting better idea about recursion now what we will do so we will solve many of those 3 00:00:09,100 --> 00:00:11,140 problems so we can understand it better. 4 00:00:11,380 --> 00:00:11,690 OK. 5 00:00:11,740 --> 00:00:15,360 So today we will be solving fable not Cassidy's problem. 6 00:00:15,420 --> 00:00:27,920 OK Phoebe anarchy cities so where does this happen knocking cities so 0 1 1 2 3 5 8. 7 00:00:27,940 --> 00:00:29,600 So this is a fable knocking cities now. 8 00:00:29,650 --> 00:00:34,730 What is if it were knocking cities so enough people knocking cities the first two numbers are fixed. 9 00:00:35,020 --> 00:00:38,860 Now if you want to calculate any number that will be the sum of the previous two number. 10 00:00:38,980 --> 00:00:42,610 So for calculating when what we will do we will add the previous two number. 11 00:00:43,030 --> 00:00:46,420 Okay so zero plus 1 is when we want to find this number. 12 00:00:46,420 --> 00:00:49,480 So it will be the addition of previous two numbers. 13 00:00:49,510 --> 00:00:49,740 Okay. 14 00:00:49,750 --> 00:00:54,440 We want to find this number so it will be the addition of previous two numbers. 15 00:00:54,520 --> 00:00:55,420 We want to find it. 16 00:00:55,450 --> 00:00:58,270 So addition of previous to number. 17 00:00:58,390 --> 00:00:59,390 So what is it. 18 00:00:59,390 --> 00:01:01,620 Addition of previous to number. 19 00:01:01,750 --> 00:01:03,250 Now the cities will continue. 20 00:01:03,280 --> 00:01:07,090 So eight plus five 13 13 blessed. 21 00:01:07,120 --> 00:01:09,250 This will be 21 21 plus 13. 22 00:01:09,280 --> 00:01:11,410 This will be 34 and so on. 23 00:01:11,410 --> 00:01:11,940 Okay. 24 00:01:11,950 --> 00:01:12,910 So what is our aim. 25 00:01:12,940 --> 00:01:18,400 Our aim is to find and that we will not kill them but okay we have to find and net if you will not give 26 00:01:18,400 --> 00:01:19,120 number. 27 00:01:19,360 --> 00:01:24,800 So let's call it zero to Fukunaga number let's call it first if it will not get them. 28 00:01:25,120 --> 00:01:26,050 And so on. 29 00:01:26,050 --> 00:01:26,560 Okay. 30 00:01:26,560 --> 00:01:32,140 So if I want to calculate sixth Fibonacci number so tell me 64 block number. 31 00:01:32,200 --> 00:01:33,820 So this is zero. 32 00:01:33,820 --> 00:01:34,630 This is 0 8. 33 00:01:34,630 --> 00:01:40,870 This is first second third fourth fifth and sixth so sixth we we're not going number will be eight. 34 00:01:40,870 --> 00:01:47,770 Okay so fib of six is eight six from an outgoing number is eight. 35 00:01:47,830 --> 00:01:48,260 Okay. 36 00:01:48,370 --> 00:01:50,330 So we have to find and net. 37 00:01:50,380 --> 00:01:54,010 We will not get them but our goal is to find and net for we're not going. 38 00:01:54,200 --> 00:01:56,630 Mystery I want to do something like this. 39 00:01:56,710 --> 00:01:58,980 So if you want to call grid and network when I can. 40 00:01:59,000 --> 00:02:02,610 But it will be the addition of previous to that is. 41 00:02:02,670 --> 00:02:08,270 And net minus one who will not condemn and and that's minus from the Iraqi number and and that minus 42 00:02:08,270 --> 00:02:09,030 two people not going in. 43 00:02:09,040 --> 00:02:13,210 But okay so some of the previous two people not them but. 44 00:02:13,490 --> 00:02:13,810 Okay. 45 00:02:13,820 --> 00:02:17,680 So this is how we will be able to calculate and that's where we're not going no. 46 00:02:18,110 --> 00:02:18,410 Okay. 47 00:02:18,410 --> 00:02:24,700 And we can see this is recursion if I want to solve bigger problem then I have to solve smaller problem. 48 00:02:24,740 --> 00:02:25,440 Okay. 49 00:02:25,700 --> 00:02:27,820 So let's write code for it. 50 00:02:28,160 --> 00:02:29,810 And these two are fixed. 51 00:02:29,990 --> 00:02:30,310 Okay. 52 00:02:31,360 --> 00:02:36,520 First two digits of difficult not number first two numbers of the Fibonacci guesses they are fixed they 53 00:02:36,520 --> 00:02:37,640 are 0 and 1. 54 00:02:38,140 --> 00:02:44,520 Okay so we have to use this formula and it's from an outgoing number is the sum of previous two people 55 00:02:44,550 --> 00:02:45,800 not going number. 56 00:02:45,900 --> 00:02:46,160 Okay. 57 00:02:46,170 --> 00:02:51,420 So let's write the code for this so we will think only in terms of PMI. 58 00:02:51,510 --> 00:02:54,020 So what a letter down typewritten that will be in danger. 59 00:02:54,060 --> 00:02:56,980 I have to attend an danger that name of the function is fib. 60 00:02:57,120 --> 00:03:02,580 It will take we have to find a network we in a month so it will take integer as input. 61 00:03:02,580 --> 00:03:07,420 Now first of all what we have to do basic is okay. 62 00:03:07,550 --> 00:03:12,470 So first is base case basic is the smallest problem whose solution we already know. 63 00:03:12,470 --> 00:03:18,420 So if and in 0 so what is there to when I can no deal tracking number is 0 only. 64 00:03:18,440 --> 00:03:20,510 Okay. 65 00:03:20,880 --> 00:03:22,860 Now it's time for the recursion. 66 00:03:22,860 --> 00:03:23,980 Okay recursive case 67 00:03:27,320 --> 00:03:29,120 so we have to recursive case here. 68 00:03:29,350 --> 00:03:30,100 Okay. 69 00:03:30,470 --> 00:03:36,210 So small output 1 and small output 2. 70 00:03:36,280 --> 00:03:44,180 So what will be small output 1 so a small output 1 will be and minus one people not them but that's 71 00:03:44,200 --> 00:03:53,110 minus one to an ongoing number and small output will be it will be and minus two people are going number 72 00:03:53,130 --> 00:03:55,480 and net minus second Copenhagen No. 73 00:03:55,670 --> 00:03:58,420 Okay now it's time for the calculation 74 00:04:01,350 --> 00:04:01,620 okay. 75 00:04:01,640 --> 00:04:03,220 So in calculation what do you do. 76 00:04:03,230 --> 00:04:04,010 I have done 77 00:04:06,790 --> 00:04:09,470 submission of small output one in small output two. 78 00:04:10,370 --> 00:04:14,050 Okay so this is all good very simple. 79 00:04:14,050 --> 00:04:17,020 And now we have to call this function let's say I want to conclude it. 80 00:04:17,040 --> 00:04:21,500 Third if you want I can add but okay I want to include We're not going no. 81 00:04:21,960 --> 00:04:23,820 Okay so this is our computer code. 82 00:04:23,860 --> 00:04:26,070 Now if we will run this code we will get at it. 83 00:04:26,430 --> 00:04:26,710 Okay. 84 00:04:26,730 --> 00:04:30,600 So let's first try to run this call and then I will explain you what do with added 85 00:04:34,550 --> 00:04:38,480 so that it will be same so that it is segmentation fault at. 86 00:04:38,510 --> 00:04:38,770 Okay. 87 00:04:38,780 --> 00:04:43,420 So just like in the factorial we are having infinite loop here. 88 00:04:43,520 --> 00:04:46,960 Now let us try to brighten our code to understand the problem. 89 00:04:47,030 --> 00:04:47,260 Okay. 90 00:04:47,270 --> 00:04:52,620 So the problem is seem like we get in the factorial in finite loop problem. 91 00:04:52,640 --> 00:04:55,030 Now I want to calculate for we're not going number three. 92 00:04:55,060 --> 00:04:57,540 Okay so let's write a novel code. 93 00:04:57,720 --> 00:04:59,210 So I have three. 94 00:04:59,300 --> 00:04:59,990 So what. 95 00:05:00,080 --> 00:05:01,100 What will happen. 96 00:05:01,170 --> 00:05:10,990 I am calling on to do will call on 1 when we will call on 0 now and then 0 so it will return 0. 97 00:05:10,990 --> 00:05:16,400 So from here let's circle all this okay. 98 00:05:16,420 --> 00:05:23,140 So these are the values often these are the values of an SO and is 0 1 and is it lambda attendings will 99 00:05:23,180 --> 00:05:24,380 our base case. 100 00:05:24,470 --> 00:05:27,330 Okay so I will return 0 from here. 101 00:05:28,860 --> 00:05:29,310 Okay. 102 00:05:29,400 --> 00:05:32,580 Now after this code this line will be executed. 103 00:05:32,610 --> 00:05:43,020 So one will call on minus one okay then minus one will call on minus two minus two will call on minus 104 00:05:43,020 --> 00:05:47,250 three minus three will call on minus four and so on. 105 00:05:47,250 --> 00:05:49,050 Basically this will become infinite loop. 106 00:05:49,050 --> 00:05:50,330 It will never stop. 107 00:05:50,430 --> 00:05:50,930 Okay. 108 00:05:50,970 --> 00:05:56,370 So what is happening here is obviously I want to if I wanted to calculate the first when I can and what 109 00:05:56,370 --> 00:05:58,260 it would call in the previous two. 110 00:05:58,260 --> 00:06:00,240 So it will call on zero and minus one. 111 00:06:00,330 --> 00:06:03,830 Okay so this thing is obvious it will call in the previous two. 112 00:06:03,870 --> 00:06:07,880 So this is obvious but what will happen it will never stop. 113 00:06:07,890 --> 00:06:08,530 Okay yeah. 114 00:06:08,550 --> 00:06:13,050 We will get infinite loop and our our loop will never stop. 115 00:06:13,080 --> 00:06:14,220 Okay so what is the problem. 116 00:06:14,220 --> 00:06:19,000 Problem is I am making two jumps so I have to take dubious cases. 117 00:06:19,080 --> 00:06:25,020 We can see here I am making two jumps and minus 1 and minus 2 since I am making to them so I have to 118 00:06:25,020 --> 00:06:26,430 take dubious cases here. 119 00:06:26,700 --> 00:06:27,250 Okay. 120 00:06:27,300 --> 00:06:30,330 And we know the first two feet were not in them but are fixed. 121 00:06:30,330 --> 00:06:32,480 So first off we went not going but at 0 and 1. 122 00:06:32,490 --> 00:06:35,430 So I have to add one more base case. 123 00:06:35,430 --> 00:06:36,030 Okay. 124 00:06:36,270 --> 00:06:43,650 So with one more base case will be if the value of and is one if I weren't to conclude the first few 125 00:06:43,660 --> 00:06:44,280 lucky number. 126 00:06:44,320 --> 00:06:48,080 So first we go knocking number is fixed and that is one only. 127 00:06:48,110 --> 00:06:51,130 Okay now if you will learn our code of a code will run fine. 128 00:06:51,160 --> 00:06:51,420 Okay. 129 00:06:51,460 --> 00:06:53,620 So I want to read the third if it were not going and what. 130 00:06:53,970 --> 00:07:00,650 Let us see what will be our output so our output is coming out to be 2 which is correct. 131 00:07:01,040 --> 00:07:10,890 Okay now let's again but in our code so our output was 2 and this is Elvis's 0 and 1 so 0 plus 1 is 132 00:07:10,890 --> 00:07:12,440 1 one plus one is two. 133 00:07:12,450 --> 00:07:14,160 So this is the third if it will not be number. 134 00:07:14,250 --> 00:07:17,160 So this is our output and our output is correct. 135 00:07:17,160 --> 00:07:21,130 Okay now let us try to write another code and see what is happening. 136 00:07:21,210 --> 00:07:22,350 So I want to calculate. 137 00:07:22,350 --> 00:07:23,540 Third if we will not going number. 138 00:07:23,970 --> 00:07:27,550 So this is third if it were not given but I went to a red card if we were not going in. 139 00:07:27,570 --> 00:07:30,360 But now I will come here. 140 00:07:30,540 --> 00:07:36,950 Okay so this tree will call on 2 and this is waiting at line number 15. 141 00:07:37,050 --> 00:07:38,650 Okay. 142 00:07:38,910 --> 00:07:42,150 And the value of ending quest tree is waiting at line number 15. 143 00:07:42,180 --> 00:07:43,440 So what will happen. 144 00:07:43,450 --> 00:07:47,910 Who will call on 1 No one is our base case. 145 00:07:47,910 --> 00:07:48,690 So what will happen. 146 00:07:48,690 --> 00:07:50,490 I will attend one from here. 147 00:07:50,490 --> 00:07:53,300 Okay so this will return when. 148 00:07:53,460 --> 00:07:57,810 So our small output 1 is 1. 149 00:07:57,850 --> 00:08:00,170 Okay now it will call. 150 00:08:00,210 --> 00:08:02,130 Now 2 will call on N minus 2. 151 00:08:02,130 --> 00:08:03,760 So too will call on 0. 152 00:08:04,880 --> 00:08:06,420 Now 0 is also a base case. 153 00:08:06,420 --> 00:08:09,620 So it will return 0 it will returns it also. 154 00:08:09,620 --> 00:08:11,420 This is our small output 2. 155 00:08:11,540 --> 00:08:14,560 So our small output 2 is 0. 156 00:08:14,720 --> 00:08:22,010 And then our calculation part I have to write the addition of these 2 so 0 plus 1 is 1 so too will return 157 00:08:22,380 --> 00:08:24,350 1 2 3 okay. 158 00:08:24,470 --> 00:08:28,620 Now what will happen 3 was waiting at line number 15. 159 00:08:28,700 --> 00:08:30,730 Now it will call on line number 16. 160 00:08:30,830 --> 00:08:35,700 So it will call on 1 Okay when is the base case. 161 00:08:35,990 --> 00:08:40,960 So it will return 1 Okay so this one. 162 00:08:41,110 --> 00:08:45,060 It was our small output when I was 1 output 1 is 1. 163 00:08:45,070 --> 00:08:47,460 And this one is our small output 2. 164 00:08:47,620 --> 00:08:50,160 So small output 2 is also 1. 165 00:08:50,290 --> 00:08:54,670 And then I am returning the addition of these two small good one plus my output 2. 166 00:08:54,970 --> 00:09:01,350 So I will return the addition of these 2 so when plus 1 is 2 so 3 will return to okay. 167 00:09:01,420 --> 00:09:04,580 So two will come here and then we are printing 2. 168 00:09:04,630 --> 00:09:05,780 So too is our answer. 169 00:09:05,860 --> 00:09:08,360 Okay so that's how this code is working. 170 00:09:09,790 --> 00:09:10,490 Okay. 171 00:09:10,720 --> 00:09:13,810 So one thing that I want you to do is think of all this 172 00:09:18,040 --> 00:09:22,620 so one thing that I want you to do is think of all this after writing the code. 173 00:09:22,690 --> 00:09:23,260 Okay. 174 00:09:23,260 --> 00:09:24,510 Violating the code. 175 00:09:24,580 --> 00:09:26,810 Think only in terms of PMI. 176 00:09:27,030 --> 00:09:27,680 Okay. 177 00:09:27,700 --> 00:09:29,790 You have to think about this diagram. 178 00:09:29,860 --> 00:09:33,930 After writing the gold after writing the code you have to tango this diagram. 179 00:09:34,060 --> 00:09:34,660 Okay. 180 00:09:34,870 --> 00:09:38,880 So I suggest you do write in the code by making this diagram. 181 00:09:39,250 --> 00:09:42,270 But first I write the code without thinking of this diagram. 182 00:09:42,340 --> 00:09:42,670 Okay. 183 00:09:42,670 --> 00:09:44,080 I'm repeating myself. 184 00:09:44,200 --> 00:09:47,330 So first I have to write the code. 185 00:09:47,500 --> 00:09:52,410 Thinking only in terms of PMI and second we have to write in our code. 186 00:09:52,440 --> 00:09:56,010 And when we're done in our code we have to make this diagram. 187 00:09:56,140 --> 00:09:58,120 Okay so first write code. 188 00:09:58,120 --> 00:10:02,070 Second that in the code by making this diagram okay. 189 00:10:02,290 --> 00:10:05,160 You do not have to think of this diagram first. 190 00:10:05,170 --> 00:10:06,250 So this is secondary. 191 00:10:06,250 --> 00:10:08,080 We have to tango this diagram later on. 192 00:10:08,080 --> 00:10:12,950 First we have to write the code and violating the code we have to think only in terms of PMI. 193 00:10:12,970 --> 00:10:14,500 So first the base case. 194 00:10:14,500 --> 00:10:16,300 Second the recursive take case. 195 00:10:16,300 --> 00:10:18,320 And third the calculation part. 196 00:10:18,340 --> 00:10:19,300 Okay. 197 00:10:19,450 --> 00:10:20,920 So I hope you understood this problem. 198 00:10:22,460 --> 00:10:23,870 Okay thank you.