1 00:00:00,170 --> 00:00:07,610 Once you have identified that you can solve a coding interview question using recursion, the most important 2 00:00:07,610 --> 00:00:12,920 step to proceed further is to be able to draw the recursion tree. 3 00:00:13,070 --> 00:00:20,930 You will see that if you can do that after you are done with drawing out the recursion tree, you will 4 00:00:20,930 --> 00:00:24,530 be able to easily solve the question and code it out. 5 00:00:24,530 --> 00:00:29,750 So let's go ahead and practice drawing a simple recursion tree. 6 00:00:29,750 --> 00:00:35,750 Now this over here is going to be a very simple one, and we will keep drawing recursion trees as we 7 00:00:35,750 --> 00:00:37,190 go along with the course. 8 00:00:37,190 --> 00:00:43,670 So let's say you want to draw the recursion tree for the Fibonacci series. 9 00:00:43,700 --> 00:00:46,790 Now a quick setting of the context over here. 10 00:00:46,790 --> 00:00:56,060 The Fibonacci series can be defined as f of n is equal to f of n minus one plus f of n minus two. 11 00:00:56,060 --> 00:01:01,370 And it's also given that f of zero is zero and f of one is one. 12 00:01:01,370 --> 00:01:02,690 Now what does this mean? 13 00:01:02,690 --> 00:01:05,330 Let's write out the sequence to understand this. 14 00:01:05,330 --> 00:01:09,320 So the first term is zero and the second term is one. 15 00:01:09,320 --> 00:01:10,850 So let's write the two terms. 16 00:01:11,910 --> 00:01:12,600 All right. 17 00:01:12,600 --> 00:01:19,410 Now it's given over here that the next term is the sum of the previous two terms. 18 00:01:19,410 --> 00:01:27,630 So f of if this is zero, this is one f of two would be f of one plus f of zero. 19 00:01:27,630 --> 00:01:31,740 And we know the values of f of zero and f of one which is zero and one. 20 00:01:31,740 --> 00:01:39,060 So this value over here which is f of two would be zero plus one which is equal to one. 21 00:01:39,090 --> 00:01:45,210 Again, the next term over here would be the sum of these two previous terms. 22 00:01:45,210 --> 00:01:48,000 So f of three would be equal to two. 23 00:01:48,030 --> 00:01:53,250 Similarly f of four would be two plus one which is equal to three. 24 00:01:53,250 --> 00:01:55,770 And it goes on in this manner. 25 00:01:55,770 --> 00:01:56,220 All right. 26 00:01:56,220 --> 00:01:59,430 So this is the Fibonacci series. 27 00:01:59,430 --> 00:02:00,180 All right. 28 00:02:00,180 --> 00:02:04,230 Now we will see this in a future video in detail. 29 00:02:04,230 --> 00:02:13,410 But over here we are just trying to try out drawing the recursion tree for this interesting question. 30 00:02:13,410 --> 00:02:14,730 So let's get started. 31 00:02:17,360 --> 00:02:18,170 All right. 32 00:02:18,170 --> 00:02:22,310 So let's say we're going to start with F of three. 33 00:02:22,340 --> 00:02:22,760 Okay. 34 00:02:22,760 --> 00:02:25,580 So let's say we want to find the value of f of three. 35 00:02:25,580 --> 00:02:29,930 So the code calls f of three. 36 00:02:30,230 --> 00:02:37,100 And this over here is going to recursively call f of two and f of one okay. 37 00:02:37,100 --> 00:02:38,900 So it's going to call f of two. 38 00:02:39,290 --> 00:02:48,860 And notice that before it goes to call f of one this f of two itself will recursively call f of one 39 00:02:48,860 --> 00:02:50,480 and f of zero. 40 00:02:50,480 --> 00:02:50,810 Right. 41 00:02:50,810 --> 00:02:52,190 So this is f of one. 42 00:02:52,190 --> 00:02:54,740 And first it's going to call f of one. 43 00:02:54,740 --> 00:03:02,180 And because we already know the value of f of one it's going to return the value which is one okay. 44 00:03:02,180 --> 00:03:08,090 And then f of two is going to recursively call the function f of zero. 45 00:03:08,090 --> 00:03:10,790 Again we already know the value of f of zero. 46 00:03:10,790 --> 00:03:12,590 So it's going to return zero. 47 00:03:13,630 --> 00:03:19,480 And now f of two can be calculated, which is one plus zero which is one. 48 00:03:19,480 --> 00:03:23,590 Therefore, f of two is gonna return one to f of three. 49 00:03:23,590 --> 00:03:24,040 Okay. 50 00:03:24,040 --> 00:03:27,400 So f of three is f of two plus f of one. 51 00:03:27,400 --> 00:03:28,600 We have seen that right. 52 00:03:28,600 --> 00:03:34,990 So first it will go down to this part over here it will try to calculate f of two. 53 00:03:35,020 --> 00:03:38,200 Again f of two will recursively call f of one. 54 00:03:38,200 --> 00:03:43,240 And because this returns it will go to the other branch call f of zero. 55 00:03:43,240 --> 00:03:44,440 Get back the value. 56 00:03:44,440 --> 00:03:49,990 And it's it's done with getting back the values needed and it will return the value one. 57 00:03:49,990 --> 00:03:53,110 Now f of three is going to call f of one. 58 00:03:53,110 --> 00:03:56,260 And we already know that f of one is already computed. 59 00:03:56,260 --> 00:03:58,060 So it's going to return one. 60 00:03:58,060 --> 00:04:03,130 And then f of three is going to return one plus one which is equal to two. 61 00:04:04,280 --> 00:04:09,470 So this over here, what we've drawn out over here is the recursion tree. 62 00:04:09,500 --> 00:04:16,100 Now, once you are done drawing out the recursion tree, it's very easy to go ahead and code this out. 63 00:04:16,130 --> 00:04:21,710 Now, in simple terms, the pseudocode would be just that if n. 64 00:04:22,470 --> 00:04:24,450 Is less than or equal to one. 65 00:04:24,480 --> 00:04:26,100 We already know the value, right? 66 00:04:26,100 --> 00:04:33,900 So if n less than or equal to one, we just need to return n itself, because for zero the value is 67 00:04:33,900 --> 00:04:34,590 also zero. 68 00:04:34,590 --> 00:04:36,990 For one the value is also one, right. 69 00:04:36,990 --> 00:04:45,570 And for other cases we just need to return f of n minus one plus f of n minus two. 70 00:04:45,600 --> 00:04:46,860 Again, we are. 71 00:04:46,860 --> 00:04:50,520 We are not aiming to write the detailed pseudocode over here. 72 00:04:50,520 --> 00:04:53,580 I'm just giving you a sample over here. 73 00:04:53,580 --> 00:04:57,120 We will see this in a future video in great detail. 74 00:04:57,120 --> 00:05:01,680 But over here we are just getting introduced to drawing a recursion tree. 75 00:05:01,680 --> 00:05:08,670 If you can successfully draw the recursion tree for a recursion problem, you will find that it will 76 00:05:08,670 --> 00:05:12,570 be a very easy task to go ahead and code it out. 77 00:05:12,570 --> 00:05:15,840 This is especially true for complex questions.