1 00:00:00,880 --> 00:00:09,280 Previously we have discussed what recursion is and we have developed some intuition on when to use recursion. 2 00:00:09,310 --> 00:00:14,920 Now let's explore two powerful tools to visualize recursion. 3 00:00:15,220 --> 00:00:22,150 Remember, if you can visualize recursion for a coding interview question, it would be very easy to 4 00:00:22,150 --> 00:00:23,380 code out the solution. 5 00:00:23,380 --> 00:00:26,410 So let's explore these two techniques. 6 00:00:26,440 --> 00:00:32,800 The first technique over here is a recursion tree, and we have already discussed the question where 7 00:00:32,800 --> 00:00:34,930 we had to find n factorial. 8 00:00:34,930 --> 00:00:35,650 All right. 9 00:00:35,650 --> 00:00:38,680 And let's say we are just finding five factorial. 10 00:00:38,680 --> 00:00:40,480 And we have the pseudocode over here. 11 00:00:40,570 --> 00:00:45,190 Let's try to draw the recursion tree for this particular pseudocode. 12 00:00:45,220 --> 00:00:49,150 So initially we are calling the function with the input five. 13 00:00:49,150 --> 00:00:52,030 So let me just write f of five over here. 14 00:00:52,720 --> 00:00:58,720 And once we are inside the body of the function because n is not equal to one it's five. 15 00:00:58,720 --> 00:01:01,420 We will again call the function recursively. 16 00:01:01,420 --> 00:01:04,240 Over here we will call f of n minus one. 17 00:01:04,240 --> 00:01:07,060 Or in this case that would be f of four. 18 00:01:07,060 --> 00:01:09,250 So let's write f of four over here. 19 00:01:09,520 --> 00:01:16,990 And once we are inside the function again for the input four, we would again come over here and we 20 00:01:16,990 --> 00:01:18,730 would be calling f of three. 21 00:01:18,730 --> 00:01:19,150 Right. 22 00:01:19,150 --> 00:01:20,620 So again that's over here. 23 00:01:20,620 --> 00:01:23,800 We would be over here and we would have called F of three. 24 00:01:23,800 --> 00:01:30,220 And in a similar manner again we would be inside the function with n equal to three n is not equal to 25 00:01:30,220 --> 00:01:30,490 one. 26 00:01:30,490 --> 00:01:35,320 So we would come over here again and we would call f of two right. 27 00:01:35,920 --> 00:01:40,570 And again we would come over here n is equal to two. 28 00:01:40,600 --> 00:01:41,950 N is not equal to one. 29 00:01:41,950 --> 00:01:45,010 So we will come over here and we will call f of one. 30 00:01:46,490 --> 00:01:47,060 Okay. 31 00:01:47,060 --> 00:01:54,140 Now when we are inside the function with n as one, because n is equal to one, we have reached the 32 00:01:54,140 --> 00:01:59,240 base or terminating condition and therefore we would return one. 33 00:01:59,240 --> 00:02:02,750 So this call over here will return one. 34 00:02:03,320 --> 00:02:11,000 So over here when we called f of two we had to multiply this with n which in this case is two right. 35 00:02:11,000 --> 00:02:17,390 So f of two will return this over here which is one into n which is two. 36 00:02:17,420 --> 00:02:22,130 In that case so f of two will return two into one okay. 37 00:02:22,130 --> 00:02:25,880 And similarly f of three f of three called f of two. 38 00:02:25,910 --> 00:02:29,300 That's this part over here for the call of f of three. 39 00:02:29,300 --> 00:02:31,130 And then you have to multiply it with three. 40 00:02:31,130 --> 00:02:31,430 Right. 41 00:02:31,430 --> 00:02:34,940 So f of three will return two into three. 42 00:02:35,660 --> 00:02:36,290 Okay. 43 00:02:36,290 --> 00:02:41,540 And similarly F of four will return this six over here multiplied with this four. 44 00:02:41,540 --> 00:02:43,160 So that's 24. 45 00:02:43,160 --> 00:02:52,520 And F of five will return this 24 over here multiplied with five which is one, 20 or 24 into five. 46 00:02:52,520 --> 00:02:56,300 So this over here is what we call the recursion tree. 47 00:02:56,330 --> 00:02:59,900 Now this is equal to 120 and we get the answer. 48 00:02:59,900 --> 00:03:05,480 Now you will see that in many questions the recursion tree will look something like this. 49 00:03:05,480 --> 00:03:08,000 You may have multiple branches. 50 00:03:10,700 --> 00:03:11,240 Okay. 51 00:03:11,240 --> 00:03:16,250 So again, we will see that in the course as we go on to future questions. 52 00:03:16,250 --> 00:03:17,810 But I'm just mentioning it over here. 53 00:03:17,810 --> 00:03:21,800 So this also is a typical recursion tree that you will see. 54 00:03:21,800 --> 00:03:28,880 So if you are able to draw the recursion tree for a question then you will see that as we practice more 55 00:03:28,880 --> 00:03:29,540 questions. 56 00:03:29,540 --> 00:03:36,170 If you can do this successfully, you will be easily be able to write the code for the solution. 57 00:03:36,170 --> 00:03:42,140 And this is in fact very helpful to identify the time and space complexity as well. 58 00:03:42,140 --> 00:03:44,150 Now more of that later in the course. 59 00:03:44,150 --> 00:03:51,200 But now let's proceed and take a look at another tool for visualization with respect to recursion, 60 00:03:51,200 --> 00:03:54,260 which is the recursion called stack. 61 00:03:55,780 --> 00:03:58,330 So we have seen the recursion tree. 62 00:03:58,360 --> 00:04:01,150 Now we are exploring the recursion call stack. 63 00:04:01,150 --> 00:04:06,310 So let's again take the same example over here where we wanted to find five factorial. 64 00:04:06,310 --> 00:04:10,660 So how would the recursion call stack look like. 65 00:04:10,660 --> 00:04:19,210 Now before we go ahead and visualize this, remember when a function is called, the computer allocates 66 00:04:19,210 --> 00:04:26,620 memory because it has to remember things like local variables, function parameters, return addresses, 67 00:04:26,620 --> 00:04:31,750 etc. so when a function is called the computer has to allocate memory. 68 00:04:31,750 --> 00:04:33,460 So this is something that you should know. 69 00:04:33,460 --> 00:04:38,500 Now let's proceed and take a look at the recursion call stack for this question over here. 70 00:04:38,500 --> 00:04:41,320 So initially we are calling f of five. 71 00:04:41,320 --> 00:04:47,560 So there would be f of five over here in the recursion call stack okay. 72 00:04:47,560 --> 00:04:50,710 So memory is allocated over here we have f of five. 73 00:04:50,710 --> 00:04:53,830 And we have seen that f of five calls f of four. 74 00:04:53,830 --> 00:04:55,630 So we have f of four over here. 75 00:04:55,630 --> 00:05:01,930 And at this point notice that f of five has not ended. 76 00:05:02,050 --> 00:05:03,610 That's why it's still over here. 77 00:05:03,610 --> 00:05:08,350 Because notice over here we are returning f of four into n. 78 00:05:08,350 --> 00:05:11,200 So it would not have done the multiplication. 79 00:05:11,200 --> 00:05:13,270 This has gone to f of four. 80 00:05:14,170 --> 00:05:21,250 And only once we get the value of this would the computer be able to do the the multiplication of what 81 00:05:21,250 --> 00:05:24,880 we get over here with n which is five in this case. 82 00:05:24,880 --> 00:05:28,240 So notice f of five has not ended. 83 00:05:28,270 --> 00:05:32,830 The computer has to hold on to it and remember it. 84 00:05:32,830 --> 00:05:35,860 So that's why we retain this over here. 85 00:05:35,860 --> 00:05:41,890 And then we proceed F of four will call f of three. 86 00:05:41,890 --> 00:05:43,450 That's something that we have seen. 87 00:05:43,930 --> 00:05:46,960 And then f of three will call f of two. 88 00:05:46,960 --> 00:05:49,990 And then f of two will call f of one. 89 00:05:50,290 --> 00:05:55,270 Now when we reach f of one we have seen that we have reached the base condition. 90 00:05:55,270 --> 00:05:56,740 So it returns one. 91 00:05:56,740 --> 00:05:59,260 So this returning one over here. 92 00:05:59,260 --> 00:06:01,630 When this happens it returns one. 93 00:06:01,630 --> 00:06:07,360 And we pop out F of one from the recursive call stack. 94 00:06:07,360 --> 00:06:14,110 And again notice over here this follows the leaf principle or last in first out. 95 00:06:14,110 --> 00:06:21,610 Notice that in this call stack f of one was the last one to be added, and it's the first one to be 96 00:06:21,610 --> 00:06:22,180 popped out. 97 00:06:22,180 --> 00:06:28,420 So that's why we call it a recursion call stack, because a stack follows the leaf principle. 98 00:06:28,420 --> 00:06:29,950 Last in first out. 99 00:06:29,950 --> 00:06:34,810 Now again more of that later in the course where we discuss the stack data structure. 100 00:06:34,810 --> 00:06:37,300 But I'm just trying to link the concepts over here. 101 00:06:37,300 --> 00:06:39,580 Now this is the recursion call stack. 102 00:06:39,580 --> 00:06:40,630 Quickly summarizing. 103 00:06:40,630 --> 00:06:45,850 It's called a stack because it follows the leaf or last in first out principle. 104 00:06:45,850 --> 00:06:51,910 And again over here we have seen that when we called f of five it did call f of four. 105 00:06:52,060 --> 00:06:56,320 And at that point f of five was not over. 106 00:06:56,320 --> 00:06:58,690 So the computer had to hold on to it. 107 00:06:58,690 --> 00:07:02,140 So popping out starts only when we start returning. 108 00:07:02,140 --> 00:07:07,120 So over here we have seen F of one was popped out and it returned one. 109 00:07:07,120 --> 00:07:15,310 Now F of two can return because it got the value of f of one and it multiplies that value with two. 110 00:07:15,340 --> 00:07:18,910 So f of two will return one into two. 111 00:07:18,940 --> 00:07:19,390 Okay. 112 00:07:19,390 --> 00:07:21,430 And we can pop out f of two. 113 00:07:21,460 --> 00:07:27,580 Similarly f of three will return two into three and we can pop out f of three. 114 00:07:27,580 --> 00:07:30,730 And similarly f of four will return. 115 00:07:31,610 --> 00:07:40,430 Six into four and we can pop out F of four, and F of five will return 24 into five and we are done. 116 00:07:40,430 --> 00:07:44,990 We can pop out F of five as well, and we get the answer which is 120. 117 00:07:45,440 --> 00:07:50,180 Now this over here is what we call the recursion call stack. 118 00:07:50,180 --> 00:07:57,620 Now the recursion tree and the recursion call stack are very powerful tools. 119 00:07:57,620 --> 00:08:04,460 They are very important because they help us to calculate especially the space complexity. 120 00:08:04,460 --> 00:08:08,330 We'll see that in future questions and in many questions. 121 00:08:08,330 --> 00:08:12,080 It's very helpful to calculate the time complexity as well. 122 00:08:12,080 --> 00:08:18,860 Now when we talk about the recursion call stack over here, we have seen that at max at a point it's 123 00:08:18,860 --> 00:08:24,590 taking up space of the order of n where n in this case is five. 124 00:08:24,590 --> 00:08:28,220 So over here this takes up space of the order of n. 125 00:08:28,220 --> 00:08:35,060 So if we have a call stack that looks like this, this would take space of the order of n which is again 126 00:08:35,060 --> 00:08:35,960 auxiliary space. 127 00:08:35,960 --> 00:08:37,220 It's extra space. 128 00:08:37,730 --> 00:08:46,880 We have understood how to go about visualizing recursion using a recursion tree or recursion call stack. 129 00:08:46,880 --> 00:08:52,910 In the next video, let's discuss the difference between recursion and iteration.