1 00:00:02,500 --> 00:00:03,520 Hi everyone. 2 00:00:03,520 --> 00:00:06,160 So in this lecture with a strategic vision. 3 00:00:06,180 --> 00:00:09,200 Okay so recursion is one of my favorite topic. 4 00:00:09,220 --> 00:00:14,060 The best part of the equation is we can easily code the most complicated problems. 5 00:00:14,160 --> 00:00:20,900 Okay recursion is very important topic because going forward in many structure we use recursion only. 6 00:00:20,980 --> 00:00:23,590 Okay so we have to do recursion properly. 7 00:00:23,590 --> 00:00:26,010 Otherwise we may face a lot of problems. 8 00:00:26,020 --> 00:00:27,990 Okay so what is recursion. 9 00:00:28,000 --> 00:00:29,810 What is the definition of recursion. 10 00:00:29,860 --> 00:00:33,480 So recursion is when a function is calling itself. 11 00:00:33,550 --> 00:00:33,940 Okay. 12 00:00:33,970 --> 00:00:39,550 The definition of recursion is when a function is calling itself so function calling itself. 13 00:00:39,580 --> 00:00:40,860 Okay so this is a recursion. 14 00:00:41,230 --> 00:00:48,640 Okay so till now what we have seen I have a function mean main is calling a function a function a is 15 00:00:48,640 --> 00:00:51,940 calling an other function b and so on. 16 00:00:51,970 --> 00:00:52,380 Okay. 17 00:00:52,480 --> 00:00:58,360 But here in the equation what I am trying to say here is a function will call itself that is we have 18 00:00:58,360 --> 00:01:05,600 a function mean main function is calling a function a function a is a green calling function. 19 00:01:05,980 --> 00:01:06,580 And so on. 20 00:01:07,110 --> 00:01:07,660 Okay. 21 00:01:07,720 --> 00:01:12,310 So it is a little weird when function e is calling function itself. 22 00:01:12,310 --> 00:01:12,870 Okay. 23 00:01:13,090 --> 00:01:15,990 Now let's try to think in a different manner. 24 00:01:16,120 --> 00:01:23,320 Okay when we will use recursion so we will use recursion we will use recursion whenever the solution 25 00:01:23,380 --> 00:01:27,300 of a problem depends upon the solution of a smaller problem. 26 00:01:27,310 --> 00:01:28,700 Okay let us take an example. 27 00:01:29,260 --> 00:01:32,300 So suppose I want to find an factorial. 28 00:01:33,220 --> 00:01:36,270 Okay we want to find out what is in factorial. 29 00:01:36,460 --> 00:01:37,680 So what we will do. 30 00:01:37,750 --> 00:01:44,670 Can we write like an factorial is this is n and minus 1 and minus 2 and so on. 31 00:01:44,670 --> 00:01:48,440 Kelvin Okay so can I write this line. 32 00:01:48,460 --> 00:01:50,170 Can I write this part in an other way. 33 00:01:50,170 --> 00:01:58,070 Can I write it like an factorial is and make the play and minus one factorial okay. 34 00:01:58,100 --> 00:01:59,660 We can write it like this way. 35 00:01:59,750 --> 00:02:04,760 Now suppose I have a function factorial Okay so I have a factorial function. 36 00:02:05,030 --> 00:02:07,770 I will give it n and it will give me an factorial. 37 00:02:07,820 --> 00:02:10,640 Okay so factorial off and it is. 38 00:02:10,640 --> 00:02:18,080 Same as can I write like this and multiply factorial function and minus 1. 39 00:02:18,120 --> 00:02:18,720 Okay. 40 00:02:18,960 --> 00:02:23,430 So this is the function name fact is the function name. 41 00:02:23,490 --> 00:02:30,630 Okay so this function takes I indigenous argument and it will have done me it will give me an factorial 42 00:02:31,140 --> 00:02:36,270 factorial often as nothing but and multiply factorial of and minus one. 43 00:02:36,990 --> 00:02:41,100 Okay so here we can see a function. 44 00:02:41,100 --> 00:02:46,080 The fact function is calling the fact function but with a smaller input. 45 00:02:46,700 --> 00:02:47,480 Okay. 46 00:02:47,670 --> 00:02:54,300 So then we will use recursion when a problem depends upon the problem of the same nature but with a 47 00:02:54,300 --> 00:03:03,860 smaller input size I am repeating myself we will use it caution when a problem depends on a problem 48 00:03:04,040 --> 00:03:10,180 of the same nature but with the smaller input size okay. 49 00:03:10,190 --> 00:03:14,760 So here we can see I have a problem. 50 00:03:14,820 --> 00:03:16,210 I want to find then factorial. 51 00:03:16,240 --> 00:03:17,430 It depends upon the. 52 00:03:17,970 --> 00:03:22,000 It depends upon a smaller problem of the same nature. 53 00:03:22,020 --> 00:03:26,210 Nature is same but with a smaller input sites okay. 54 00:03:26,320 --> 00:03:32,660 Now what we are trying to do here is so we are trying to divide the problem so I have a big problem. 55 00:03:32,980 --> 00:03:34,330 I have a big problem. 56 00:03:34,330 --> 00:03:35,320 I will divide. 57 00:03:35,320 --> 00:03:37,980 I will convert the problem into smaller problem. 58 00:03:38,170 --> 00:03:42,070 I will again convert it into a smaller problem. 59 00:03:42,070 --> 00:03:46,000 I will again convert it to a smaller problem and it will go on. 60 00:03:46,030 --> 00:03:50,310 Okay so finally our problem will become very very small. 61 00:03:50,500 --> 00:03:50,950 Okay. 62 00:03:51,040 --> 00:03:53,480 So we are reducing the size of our problem. 63 00:03:53,500 --> 00:03:55,620 Okay our problem size is being reduced. 64 00:03:56,340 --> 00:03:56,780 Okay. 65 00:03:56,890 --> 00:04:01,600 We can see here our problem now our problem becomes smaller. 66 00:04:01,740 --> 00:04:02,140 Okay. 67 00:04:02,200 --> 00:04:05,570 So recursion what occasion will do I have a big problem. 68 00:04:05,590 --> 00:04:08,140 I will convert the big problem into smaller problem. 69 00:04:08,140 --> 00:04:11,540 I will again convert the smaller problem in to smaller problem. 70 00:04:11,590 --> 00:04:15,130 Again the smaller problem will be converted into smaller problem. 71 00:04:15,160 --> 00:04:17,210 And so on okay. 72 00:04:17,320 --> 00:04:22,880 Now let us try to see a thing called We Will tried to solve the same problem. 73 00:04:22,970 --> 00:04:26,360 So let us take the value of an input from the user. 74 00:04:28,460 --> 00:04:31,240 Okay so let's say I have a function fact. 75 00:04:31,340 --> 00:04:33,910 So this function effectively done me the answer. 76 00:04:34,070 --> 00:04:36,020 So I have this fact function. 77 00:04:36,080 --> 00:04:39,490 I will give it n factory function and it will be done with the answer. 78 00:04:39,510 --> 00:04:42,350 And let us try to predict the end factorial okay. 79 00:04:44,370 --> 00:04:45,470 Now what we have discussed. 80 00:04:45,480 --> 00:04:48,680 So what we have done type of the function it will be in digit. 81 00:04:48,750 --> 00:04:53,100 Then it would function is fact and it will take a and b as argument holds factorial. 82 00:04:53,100 --> 00:04:58,860 We have to conclude OK so what is the meaning of the equation. 83 00:04:58,860 --> 00:04:59,610 What do we do. 84 00:04:59,640 --> 00:05:09,820 We will find out we will convert the big problem into smaller problem so in small answer I'm calling 85 00:05:09,820 --> 00:05:13,090 the function factorial and I will give and minus one. 86 00:05:13,500 --> 00:05:14,050 OK. 87 00:05:14,200 --> 00:05:16,130 So now at line number five. 88 00:05:16,180 --> 00:05:18,400 I know the factory I live in minus one. 89 00:05:18,430 --> 00:05:19,420 So what is the factory. 90 00:05:19,420 --> 00:05:27,400 Often it will be what I will do I just have to return and make to play small said okay. 91 00:05:27,600 --> 00:05:35,100 So what I'm trying to do here is I want to conclude the factorial often so at line number five. 92 00:05:35,110 --> 00:05:36,180 What I'm doing. 93 00:05:36,370 --> 00:05:38,680 I'm calculating the factorial of and minus 1. 94 00:05:38,710 --> 00:05:39,060 Okay. 95 00:05:39,070 --> 00:05:44,830 What this fact function will do this fact function takes an integer and it returns and in digit which 96 00:05:44,830 --> 00:05:50,050 is the fact all of them but so this fact photo really will give me and minus one factory. 97 00:05:50,160 --> 00:05:50,900 Okay. 98 00:05:51,040 --> 00:05:54,990 And they're dead minus one factory is stored in a small answer. 99 00:05:55,000 --> 00:05:58,420 And finally either done and multiply and minus one factory. 100 00:05:58,440 --> 00:06:02,290 Okay now let us try to add another code and let us see what will happen. 101 00:06:02,500 --> 00:06:02,800 Okay. 102 00:06:07,430 --> 00:06:09,550 Now it is waiting for us to give input. 103 00:06:09,560 --> 00:06:11,510 Let's say I want to calculate for the factory. 104 00:06:11,530 --> 00:06:15,890 Okay so forth and that. 105 00:06:15,950 --> 00:06:21,380 So what will happen what is happening here is basically we are getting segmentation fault in a finite 106 00:06:21,380 --> 00:06:21,650 loop. 107 00:06:21,680 --> 00:06:26,650 Okay so this is in finite loop we are getting segmentation for it. 108 00:06:26,690 --> 00:06:28,810 Now let us try to brighten our code. 109 00:06:28,820 --> 00:06:30,140 What is happening. 110 00:06:30,170 --> 00:06:33,620 Okay let's try to drive it another good. 111 00:06:33,620 --> 00:06:33,850 Okay. 112 00:06:33,860 --> 00:06:36,040 So what is happening here is. 113 00:06:36,320 --> 00:06:43,280 So I have this function mean I have this function when it is calling the function factorial often. 114 00:06:43,330 --> 00:06:50,260 Okay so Maiden is calling fact and led to the values food and is food. 115 00:06:50,270 --> 00:06:56,570 Okay so and is food now what is happening here is this factory function is again calling the factory 116 00:06:56,570 --> 00:06:57,040 function. 117 00:06:57,050 --> 00:07:01,830 So it is calling a factorial function but the value of an S T. 118 00:07:01,850 --> 00:07:04,620 So the value of land is three. 119 00:07:04,640 --> 00:07:08,900 We can understand it this in a different way but actually it doesn't happen. 120 00:07:08,930 --> 00:07:12,410 Okay so let's try to understand it in a different manner. 121 00:07:12,830 --> 00:07:23,760 So I have mean no men is calling a function factorial okay and the value of these food okay now at this 122 00:07:23,760 --> 00:07:31,020 line what is happening here is let's suppose we have another instance of defect bowl function okay we 123 00:07:31,020 --> 00:07:35,970 have another instance of the actual function and this is calling the factory but the value of this tree 124 00:07:36,540 --> 00:07:38,700 you can see here and minus one. 125 00:07:38,760 --> 00:07:39,250 Okay. 126 00:07:39,330 --> 00:07:44,350 So this new instance is created you can assume that but it doesn't happen okay. 127 00:07:44,430 --> 00:07:47,040 So now what is happening it is. 128 00:07:47,040 --> 00:07:47,790 So what will happen. 129 00:07:47,790 --> 00:07:55,900 This fact function it will call fact to again the value of and this to here. 130 00:07:56,020 --> 00:08:01,660 Now what I want to say here is we know the local variables of one function is different from the local 131 00:08:01,660 --> 00:08:03,750 variables of another function. 132 00:08:03,790 --> 00:08:09,810 Okay so this end here the value of this for it and it had the value of industry. 133 00:08:09,970 --> 00:08:12,850 So this end and this end they both are different. 134 00:08:13,210 --> 00:08:15,100 Okay they are different. 135 00:08:15,100 --> 00:08:20,470 Okay why different because we know the local variables of one function is different on the local variable 136 00:08:20,470 --> 00:08:23,260 itself another function these are two different functions. 137 00:08:23,310 --> 00:08:24,720 Okay two instances. 138 00:08:24,880 --> 00:08:31,240 So this n and this end they both are different now what will happen this will call fact to when know 139 00:08:31,240 --> 00:08:33,130 the value of and becomes one. 140 00:08:33,190 --> 00:08:37,870 So what is happening here is as soon as we entered this function we are calling and a function. 141 00:08:37,870 --> 00:08:42,160 Okay so now this fact when it will call fact to zero. 142 00:08:42,160 --> 00:08:47,330 So the value of n is zero then it will call fact minus 1. 143 00:08:47,410 --> 00:08:51,150 It will call effect minus 2 and so on. 144 00:08:51,160 --> 00:08:51,620 Okay. 145 00:08:51,670 --> 00:08:55,340 So basically it is we are doing in finite cause okay. 146 00:08:55,450 --> 00:08:57,120 We are doing infinite cores. 147 00:08:57,190 --> 00:09:00,180 So this is infinite loop this is infinite loop. 148 00:09:01,030 --> 00:09:02,930 So we are getting segmentation for. 149 00:09:02,980 --> 00:09:03,240 Okay. 150 00:09:03,250 --> 00:09:05,420 So why we are getting segmentation fault. 151 00:09:05,440 --> 00:09:13,280 So what is happening here is when I reach this line all these four functions when I am here all these 152 00:09:13,280 --> 00:09:17,680 four functions are waiting for the factorial one function to compute its work. 153 00:09:17,760 --> 00:09:22,610 Okay all are waiting all have the copies off and now it is taking some memory. 154 00:09:22,700 --> 00:09:23,240 Okay. 155 00:09:23,390 --> 00:09:27,860 This is taking some memory this is taking some memory it is taking some memory it is taking some memory. 156 00:09:27,920 --> 00:09:29,470 Okay so what will happen. 157 00:09:29,480 --> 00:09:36,020 We are we are doing infinite cores so at some time it will not be able the program will not be able 158 00:09:36,020 --> 00:09:39,270 to create more memory and we will get segmentation fault. 159 00:09:39,310 --> 00:09:42,210 Okay so when Irish fact minus two. 160 00:09:42,230 --> 00:09:43,100 What will happen. 161 00:09:43,100 --> 00:09:49,730 All these functions are waiting for the effect minus to function to compute its work. 162 00:09:49,850 --> 00:09:56,390 Okay so everything will take memory they are taking small small memories but we are doing in finite 163 00:09:56,390 --> 00:09:56,920 cores. 164 00:09:56,990 --> 00:09:58,840 So had some time what will happen. 165 00:09:59,120 --> 00:10:00,620 We will get out of memory. 166 00:10:00,620 --> 00:10:00,890 Okay. 167 00:10:00,920 --> 00:10:05,420 We will not be able to create more memory and we will get segmentation fault due to in finite cores 168 00:10:06,830 --> 00:10:14,650 Okay so while there are finite calls because we started at an equals four then three two one zero. 169 00:10:15,020 --> 00:10:16,660 So I deliver to happen. 170 00:10:16,670 --> 00:10:19,750 We should stop at zero or we should stop at one. 171 00:10:20,190 --> 00:10:22,780 Okay but here we are making in calls. 172 00:10:22,850 --> 00:10:23,420 Okay. 173 00:10:23,420 --> 00:10:27,880 Ideally we should stop at zero or one but we are making here in finite calls. 174 00:10:27,920 --> 00:10:29,410 I can prove it also. 175 00:10:29,420 --> 00:10:30,470 So how will I prove it. 176 00:10:30,470 --> 00:10:31,370 What I will do. 177 00:10:32,710 --> 00:10:39,150 As soon as I entered this function I will print the value of an okay I will print the value often. 178 00:10:39,160 --> 00:10:40,860 Now let us try to run this file. 179 00:10:42,290 --> 00:10:44,620 Now let's see the value of an is food. 180 00:10:44,780 --> 00:10:50,160 And as soon as we will print ended so you can see here these are the values of n.. 181 00:10:50,280 --> 00:10:56,240 Okay so these are all the values of these main them but of course I am trying to make here okay. 182 00:10:56,270 --> 00:10:59,790 So we are making many calls but we could not get our answer. 183 00:10:59,810 --> 00:11:04,220 Finally we will get the segmentation fault due to the lack of memory. 184 00:11:04,220 --> 00:11:08,460 Okay so we are making many many calls. 185 00:11:08,550 --> 00:11:11,720 I don't know where it will stop okay. 186 00:11:11,960 --> 00:11:16,980 It will stop when we get out of memory and we will get segmentation fault due to lack of memory. 187 00:11:17,480 --> 00:11:17,740 Okay. 188 00:11:17,750 --> 00:11:23,180 It is making these main number of calls and it is trying to find Don center this trying to find the 189 00:11:23,180 --> 00:11:23,820 Ford factor. 190 00:11:23,870 --> 00:11:28,700 Okay so at this moment what is happening here is we have due to lack of memory. 191 00:11:28,700 --> 00:11:30,920 We are getting this segmentation forward. 192 00:11:30,980 --> 00:11:34,610 Okay now let's call it up. 193 00:11:34,680 --> 00:11:39,650 I am not able to call it more so what I have done here is. 194 00:11:39,790 --> 00:11:42,430 So this is the same code you can see here. 195 00:11:42,430 --> 00:11:49,770 This is the same code I have written this code on idea on and now let's say the input is food and we 196 00:11:49,760 --> 00:11:52,650 will try to end the file we will try in the code. 197 00:11:52,660 --> 00:11:59,110 Okay so you can see the output we are getting run by method where runtime error because of infinite 198 00:11:59,110 --> 00:11:59,680 loop. 199 00:11:59,680 --> 00:12:00,530 Okay. 200 00:12:00,820 --> 00:12:07,300 Now you can see here this is the output for 3 2 1 0 and then minus one minus two minus three and so 201 00:12:07,300 --> 00:12:07,780 on. 202 00:12:07,780 --> 00:12:08,410 Okay. 203 00:12:08,590 --> 00:12:13,740 You can scroll to the bottom and you can see you do a self okay. 204 00:12:13,870 --> 00:12:18,310 So for 2 to 1 and then 0 minus one minus 2. 205 00:12:18,340 --> 00:12:19,850 So ideally what should happen. 206 00:12:19,900 --> 00:12:23,770 Ideally our program should stop at some moment okay. 207 00:12:23,770 --> 00:12:27,280 Our program should stop at some moment now Vader should stop 208 00:12:30,590 --> 00:12:30,830 okay. 209 00:12:30,840 --> 00:12:34,760 So what is happening here is factorial for function. 210 00:12:34,760 --> 00:12:38,280 This is calling factorial 3. 211 00:12:38,480 --> 00:12:40,930 It is calling factorial 2. 212 00:12:41,180 --> 00:12:44,460 It is calling factorial when it is calling. 213 00:12:44,480 --> 00:12:47,070 Let's say factorial zero okay. 214 00:12:47,180 --> 00:12:51,250 Now it is calling factorial minus 1. 215 00:12:51,310 --> 00:12:54,930 Now according to mean there is no need of this call. 216 00:12:54,980 --> 00:12:55,340 Why. 217 00:12:55,660 --> 00:12:58,060 Because this is very trivial problem. 218 00:12:58,090 --> 00:12:58,340 Okay. 219 00:12:58,360 --> 00:13:00,860 What is 0 factorial 0 vector Lisbon. 220 00:13:00,970 --> 00:13:05,830 So I already know the answer of zero factorial so why to make the call to minus 1. 221 00:13:05,830 --> 00:13:07,180 Okay so what do we do. 222 00:13:07,180 --> 00:13:11,510 Factorial zero will return 1 because zero factorial is 1. 223 00:13:11,530 --> 00:13:14,890 Okay so our recursion chain will stop here. 224 00:13:14,950 --> 00:13:16,910 We do not need to go any further. 225 00:13:16,930 --> 00:13:23,890 Okay so factorial zero will give this output will give its output to factorial 1. 226 00:13:23,890 --> 00:13:26,610 Okay so we are returning 1 here. 227 00:13:26,920 --> 00:13:27,160 Okay. 228 00:13:27,190 --> 00:13:31,870 Similarly factorial 1 will do its work and it will return the factorial of 1 and so on. 229 00:13:32,170 --> 00:13:37,150 Okay so in recursion we call the same function with the smaller input size. 230 00:13:37,180 --> 00:13:41,880 Okay we are calling the same function with the smaller input size. 231 00:13:41,950 --> 00:13:46,760 Now with the help of the output of the smaller problem we have to calculate our output. 232 00:13:47,350 --> 00:13:53,440 Okay so with the help of I am repeating myself with the help of the output of a smaller problem we have 233 00:13:53,440 --> 00:13:54,510 to calculate our output. 234 00:13:54,520 --> 00:13:56,540 Let's say the output of three factorial. 235 00:13:56,550 --> 00:13:59,620 So this is bigger problem and this is a smaller problem. 236 00:13:59,740 --> 00:14:03,900 Let's say the output of factorial 3 is x. 237 00:14:04,060 --> 00:14:06,020 Okay so what factory 4 will do. 238 00:14:06,100 --> 00:14:13,040 It will multiply forward with X and then it will return the output to the mean. 239 00:14:13,150 --> 00:14:13,670 Okay. 240 00:14:13,750 --> 00:14:19,960 So with the help of the output of the smaller problem the function we will calculate our bigger problem 241 00:14:19,960 --> 00:14:22,930 and then we will return our output to the mean. 242 00:14:22,990 --> 00:14:28,840 Okay so to stop the recursion chain what we have to do we have to stop our recursion chain here because 243 00:14:28,840 --> 00:14:30,780 0 factorial is a very trivial problem. 244 00:14:30,790 --> 00:14:31,900 We already know Don. 245 00:14:31,930 --> 00:14:35,420 So why to why to make call to minus one. 246 00:14:35,440 --> 00:14:41,350 Okay now let's see so we have to call we have to stop 247 00:14:46,310 --> 00:14:47,730 we have to stop that equation. 248 00:14:47,750 --> 00:14:49,370 Chin now to stop the occasion. 249 00:14:50,270 --> 00:14:50,760 I know. 250 00:14:50,840 --> 00:14:52,240 If the value of any zero. 251 00:14:52,640 --> 00:14:53,870 I already know the answer. 252 00:14:53,910 --> 00:14:56,280 Zero factoid Lisbon one so I will attend one here. 253 00:14:57,110 --> 00:15:00,830 Okay now this we have an occasion Jane will stop. 254 00:15:00,860 --> 00:15:02,480 Okay let's run this file 255 00:15:05,460 --> 00:15:09,480 so let's then put this forward okay. 256 00:15:09,500 --> 00:15:13,730 So what is happening it is the value of this forward and then it becomes T. 257 00:15:13,750 --> 00:15:17,420 Then it becomes true then it becomes one then it becomes zero. 258 00:15:17,420 --> 00:15:18,490 Now let's see here. 259 00:15:18,620 --> 00:15:20,790 We are not making gold two minus one. 260 00:15:20,840 --> 00:15:21,200 Okay. 261 00:15:21,210 --> 00:15:24,170 Our our function our equation Jean stops at zero. 262 00:15:24,700 --> 00:15:24,960 Okay. 263 00:15:24,980 --> 00:15:26,450 We didn't call on minus. 264 00:15:26,450 --> 00:15:30,050 We stopped at zero and this is our answer 24. 265 00:15:30,080 --> 00:15:32,180 Okay so 24 is the fourth factorial. 266 00:15:32,780 --> 00:15:37,640 Okay so our output is right now let us drive another code how it is working. 267 00:15:37,670 --> 00:15:37,960 Okay 268 00:15:41,320 --> 00:15:45,760 so this is I mean okay. 269 00:15:45,800 --> 00:15:48,050 So main is calling factorial for 270 00:15:50,980 --> 00:15:51,270 okay. 271 00:15:51,320 --> 00:15:58,170 So the value of and is four here and what is happening here is when mean cause effect forward function. 272 00:15:58,190 --> 00:16:02,920 So the main function it is waiting for the actual forward function to return it sunset. 273 00:16:03,350 --> 00:16:03,900 Okay. 274 00:16:04,080 --> 00:16:09,000 So this main function we are waiting at line number 16. 275 00:16:09,020 --> 00:16:09,410 Okay. 276 00:16:09,620 --> 00:16:12,590 I am also writing the line number at which the function is waiting. 277 00:16:12,590 --> 00:16:19,340 So this main function is waiting at line numbers 16 for the factorial function to do its work to complete 278 00:16:19,340 --> 00:16:20,610 its work. 279 00:16:20,660 --> 00:16:21,140 Okay. 280 00:16:21,290 --> 00:16:26,960 So I will enter defect world function and then we are again making the call the value of n is not zero. 281 00:16:27,050 --> 00:16:27,350 Okay. 282 00:16:27,350 --> 00:16:28,220 The value of in this word. 283 00:16:28,760 --> 00:16:31,580 So I am making the call to fact function. 284 00:16:31,580 --> 00:16:36,710 So this is calling factorial to function. 285 00:16:36,710 --> 00:16:40,900 The value of in history and this is waiting at line number eight. 286 00:16:41,250 --> 00:16:42,160 OK effectively forward. 287 00:16:42,160 --> 00:16:44,910 Function is waiting at line number eight. 288 00:16:45,030 --> 00:16:48,780 Now again three is not close to zero. 289 00:16:48,780 --> 00:16:51,980 So it is it will call factorial to function. 290 00:16:52,200 --> 00:16:56,660 And this is also waiting at line embodied the value of and is to. 291 00:16:56,670 --> 00:16:59,360 Now again 2 is not zero. 292 00:16:59,400 --> 00:17:03,180 So it will call factorial 1 function. 293 00:17:03,180 --> 00:17:09,520 So the value of n is 1 and it is waiting at line number it again it will be a red line number it because 294 00:17:09,530 --> 00:17:10,530 1 is not 0. 295 00:17:10,550 --> 00:17:13,130 So it will call effectively zero function. 296 00:17:13,130 --> 00:17:13,330 Okay. 297 00:17:13,340 --> 00:17:15,200 The value of n is 0 now. 298 00:17:15,950 --> 00:17:16,390 Okay. 299 00:17:16,520 --> 00:17:20,770 So the value of end is zero okay. 300 00:17:20,780 --> 00:17:21,990 So this condition is true. 301 00:17:22,010 --> 00:17:26,100 What I am doing here is I am returning when so what. 302 00:17:26,110 --> 00:17:26,820 What will happen. 303 00:17:27,190 --> 00:17:28,110 I am returning when. 304 00:17:28,120 --> 00:17:35,240 So this factoid zero function it will return when it is returning when and we added. 305 00:17:35,240 --> 00:17:35,910 Line number 8. 306 00:17:35,930 --> 00:17:37,460 So headline number 8. 307 00:17:37,670 --> 00:17:38,600 Small I said. 308 00:17:38,720 --> 00:17:43,420 So the small line said it is one here okay. 309 00:17:43,510 --> 00:17:45,920 Now and multiply small answer. 310 00:17:45,930 --> 00:17:49,140 So what is the value of in one small line is 1. 311 00:17:49,150 --> 00:17:52,520 So it will return when multiply 1 which is 2. 312 00:17:52,600 --> 00:17:57,700 So it is returning to and the two waste will be stored in this small answer. 313 00:17:57,700 --> 00:18:03,260 So small answer becomes 2 now factorial 2 will do its work. 314 00:18:03,430 --> 00:18:04,530 Okay so. 315 00:18:04,780 --> 00:18:10,030 So it will be 1 I told you and no factor to will do its work. 316 00:18:10,030 --> 00:18:12,780 So to multiply small answer. 317 00:18:12,970 --> 00:18:16,420 So small answer will now becomes to here. 318 00:18:16,420 --> 00:18:24,200 Okay now three multiplied two and multiply small answer so three multiply two. 319 00:18:24,370 --> 00:18:27,130 So it will return six to the factory for function. 320 00:18:27,140 --> 00:18:29,930 So the small answer becomes six eight. 321 00:18:30,070 --> 00:18:34,560 Now and multiply a small answer and it's for small answer is six. 322 00:18:34,720 --> 00:18:38,980 So it will done six into four 24 to the mean. 323 00:18:39,010 --> 00:18:39,300 Okay. 324 00:18:39,310 --> 00:18:43,280 So the headline number 16 I'm returning to a default. 325 00:18:43,310 --> 00:18:49,080 So answer contains 24 and I am printing 24 here okay. 326 00:18:49,230 --> 00:18:55,690 So you know what happened here is when I reach suppose when I am reaching this function when I use this 327 00:18:55,690 --> 00:18:59,850 function all these functions they are out of memory. 328 00:19:00,070 --> 00:19:00,360 Okay. 329 00:19:00,370 --> 00:19:02,110 They do not exist anymore. 330 00:19:02,410 --> 00:19:02,890 Okay. 331 00:19:03,040 --> 00:19:04,700 So their wait is over. 332 00:19:04,760 --> 00:19:10,330 They are out of memory so what is happening it is as soon as this function is returning when as soon 333 00:19:10,330 --> 00:19:11,850 as this function is attending when. 334 00:19:11,910 --> 00:19:17,090 Now this function does not exist as soon as this function returns its answer. 335 00:19:17,110 --> 00:19:19,930 Now this function does not exist. 336 00:19:19,930 --> 00:19:20,450 Okay. 337 00:19:20,560 --> 00:19:27,670 So as soon as vector to function gets down from the factory one function it's where it is or what. 338 00:19:27,850 --> 00:19:33,010 Similarly as soon as the actual tree function gets that would put a de facto right to function. 339 00:19:33,010 --> 00:19:34,090 It's where it is or what. 340 00:19:34,150 --> 00:19:35,470 And so on. 341 00:19:35,470 --> 00:19:38,220 Okay so we call it go back. 342 00:19:38,260 --> 00:19:38,980 Okay. 343 00:19:38,980 --> 00:19:39,970 This is called strike. 344 00:19:39,970 --> 00:19:43,090 I think we have already discussed it in functions. 345 00:19:43,090 --> 00:19:44,790 So what is a call stick. 346 00:19:44,980 --> 00:19:50,300 So Ghost tech is like a glass so at the bottom we have the main function. 347 00:19:51,070 --> 00:19:58,840 Okay so we have the main function main function is calling the factorial for function factorial for 348 00:19:58,840 --> 00:20:07,170 function is calling factorial 3 function factoid 3 function calls factorial 2 function factorial 2 function 349 00:20:07,170 --> 00:20:13,450 calls for 3 1 function and effectively 1 function is calling factoid 0 function. 350 00:20:13,540 --> 00:20:14,180 Okay. 351 00:20:14,260 --> 00:20:17,110 And effect 0 0 function is not calling anything. 352 00:20:17,200 --> 00:20:18,900 Okay so what is that call a stick. 353 00:20:18,910 --> 00:20:22,570 So what really happened so factoid 0 will do its work. 354 00:20:22,600 --> 00:20:27,340 It will complete its work and it will return the answer to defect relevant function and then it will 355 00:20:27,340 --> 00:20:29,220 goes out of the memory. 356 00:20:29,260 --> 00:20:31,320 Okay well it goes out it will go out. 357 00:20:31,500 --> 00:20:36,820 Factory one function they compute it works and it will return the answer to the factory to function 358 00:20:36,850 --> 00:20:40,680 then factory won't function they go out okay. 359 00:20:40,750 --> 00:20:44,210 And this way everything will go out okay. 360 00:20:44,410 --> 00:20:46,610 Everything will go out of this tank okay. 361 00:20:46,810 --> 00:20:51,250 So we call it call stack we have already discussed it in functions. 362 00:20:51,250 --> 00:20:51,750 Okay. 363 00:20:51,850 --> 00:20:54,480 So the order is reverse okay. 364 00:20:54,490 --> 00:20:56,010 Factories 0 function. 365 00:20:56,050 --> 00:21:00,570 So the factorial 0 function it comes at last. 366 00:21:00,590 --> 00:21:02,120 But it goes out first. 367 00:21:03,100 --> 00:21:03,790 Okay. 368 00:21:03,860 --> 00:21:08,630 This function mean so mean comes head first but it will go last. 369 00:21:08,750 --> 00:21:09,010 Okay. 370 00:21:09,020 --> 00:21:12,060 It will wait for the other function to compute their work. 371 00:21:12,170 --> 00:21:14,380 We do not need to go in so much depth. 372 00:21:14,510 --> 00:21:19,090 We will discuss something in the next session which is going to make things very easy for us. 373 00:21:19,160 --> 00:21:19,650 Okay. 374 00:21:19,820 --> 00:21:23,610 But this is how that equation works internally okay. 375 00:21:23,660 --> 00:21:25,970 This is how that equation works internally. 376 00:21:26,060 --> 00:21:29,870 Now I hope you got the idea how the recursion is working. 377 00:21:29,870 --> 00:21:35,550 Okay if you want if you want you can optimize this code. 378 00:21:35,550 --> 00:21:36,900 Also how we can optimize. 379 00:21:36,960 --> 00:21:41,030 So first of all this is not required now. 380 00:21:41,080 --> 00:21:42,880 There is one small but no discord. 381 00:21:42,940 --> 00:21:45,690 Whatever the value of an is minus one. 382 00:21:45,720 --> 00:21:51,720 Okay what if the value of end is minus 1 then it will never stop again it will become infinite loop 383 00:21:51,730 --> 00:21:53,270 let me show you. 384 00:21:53,370 --> 00:21:55,360 So let's say the value of n is minus 1. 385 00:21:55,400 --> 00:21:57,900 A negative value then not a good. 386 00:21:57,900 --> 00:22:00,110 Then again it will run into infinite loop. 387 00:22:00,450 --> 00:22:00,910 Okay. 388 00:22:02,260 --> 00:22:05,310 Okay so let's come and it our first. 389 00:22:05,340 --> 00:22:08,190 Now let's see the value of this minus. 390 00:22:08,190 --> 00:22:11,470 I will give the value of n negative so minus 1. 391 00:22:11,490 --> 00:22:17,430 So again we are getting infinite loop y infinite loop because this is the beginning condition. 392 00:22:17,430 --> 00:22:20,280 Okay now the value of N will never be 0. 393 00:22:20,340 --> 00:22:21,600 It will keep on reducing. 394 00:22:21,600 --> 00:22:22,310 So that's why. 395 00:22:22,620 --> 00:22:24,690 So that's why this will run into infinite loop. 396 00:22:24,690 --> 00:22:32,380 Now to fix this problem what we can do here is we can we can write a condition like if the value of 397 00:22:32,380 --> 00:22:39,480 land is negative I will return minus 1 Okay factor for negative numbers are not defined. 398 00:22:39,540 --> 00:22:48,040 Okay so in this case if I will give the input a negative number let's say minus 5. 399 00:22:48,060 --> 00:22:49,310 So what will happen. 400 00:22:49,350 --> 00:22:56,390 So we are getting minus 1 okay because vector for negative numbers is not defined McCain coming down 401 00:22:56,420 --> 00:22:57,110 this code. 402 00:22:57,110 --> 00:22:58,590 Okay. 403 00:22:58,640 --> 00:23:06,210 So the value of an is minus 5 and the answer is minus 1 because vector for negative number is not defined. 404 00:23:06,230 --> 00:23:07,010 Okay. 405 00:23:07,340 --> 00:23:08,570 Now this is the correct code. 406 00:23:08,600 --> 00:23:09,010 Okay. 407 00:23:09,110 --> 00:23:10,830 We are using recursion here. 408 00:23:10,910 --> 00:23:11,140 Okay. 409 00:23:11,150 --> 00:23:11,570 Thank you.