1
00:00:00,630 --> 00:00:07,470
Previously we have discussed what recursion is and we have identified when to use recursion.

2
00:00:07,500 --> 00:00:14,940
Now in this video, let's discuss a powerful concept called recursive leap of faith.

3
00:00:15,030 --> 00:00:23,580
This concept will help us and understand recursion even better, and it also deals with how to actually

4
00:00:23,580 --> 00:00:27,390
go about using recursion in coding interview questions.

5
00:00:27,420 --> 00:00:31,800
Now, many times recursion feels like magic.

6
00:00:31,800 --> 00:00:38,370
If you are just able to wrap your head around the basics of recursion, you will see that you will be

7
00:00:38,370 --> 00:00:43,650
able to use this powerfully in solving a variety of coding interview questions.

8
00:00:43,650 --> 00:00:46,500
And that's why many people think of recursion.

9
00:00:47,070 --> 00:00:49,530
Like feel of it as if it's magic.

10
00:00:49,530 --> 00:00:53,580
Now what are the steps in using recursion?

11
00:00:53,580 --> 00:00:58,650
So the five steps in using recursion are these five steps over here.

12
00:00:58,650 --> 00:01:01,230
And let's go through them one by one.

13
00:01:01,230 --> 00:01:04,920
The first step is to understand the problem at hand.

14
00:01:04,920 --> 00:01:06,480
Let's take an example.

15
00:01:06,480 --> 00:01:10,770
Let's say you are asked to print a sequence that looks like this.

16
00:01:10,770 --> 00:01:15,060
So you have 321123.

17
00:01:15,060 --> 00:01:16,770
Now this is just an example.

18
00:01:16,770 --> 00:01:23,310
Let's say you are given n and you need to print n, n, minus one, etc. up to one.

19
00:01:23,310 --> 00:01:26,190
And then you have one, two etc. up to n.

20
00:01:26,190 --> 00:01:30,660
So that's what is over here just for n equal to three.

21
00:01:31,380 --> 00:01:35,220
The second step is to identify a subproblem.

22
00:01:35,220 --> 00:01:43,290
We have seen that recursion is suitable when you are able to break the original problem into subproblems,

23
00:01:43,290 --> 00:01:47,700
and solving the subproblems helps you to solve the original problem.

24
00:01:47,700 --> 00:01:52,380
So the second step over here is to identify a subproblem.

25
00:01:52,380 --> 00:01:59,100
Now identifying a subproblem will become more intuitive and you will be able to do it more and more

26
00:01:59,100 --> 00:02:05,760
easier with more exposure to a wide variety of coding interview questions, which we will take care

27
00:02:05,760 --> 00:02:05,970
of.

28
00:02:05,970 --> 00:02:07,020
In this course.

29
00:02:07,020 --> 00:02:13,350
We will go through a variety of questions in the future sections, but let's take it one step at a time.

30
00:02:13,350 --> 00:02:18,000
So for this example over here, what would be the subproblem?

31
00:02:18,000 --> 00:02:23,520
The subproblem would be to print 211 and two right.

32
00:02:23,520 --> 00:02:35,250
So again if you had to do this like (543) 211-2345, notice that the subproblem for the original problem

33
00:02:35,250 --> 00:02:44,790
is to print 43211234, and the subproblem of this would be to print three two, 1123, etc..

34
00:02:45,270 --> 00:02:45,750
All right.

35
00:02:45,750 --> 00:02:51,630
So that's the second problem which is second step which is to identify the subproblem.

36
00:02:52,120 --> 00:02:59,350
The third step is the step of trust or faith, which is what we call the recursive leap of faith.

37
00:02:59,350 --> 00:03:03,970
And this is actually what makes recursion feel like magic.

38
00:03:03,970 --> 00:03:11,440
Or this is actually what makes recursion so powerful and so helpful in a wide variety of coding interview

39
00:03:11,440 --> 00:03:12,130
questions.

40
00:03:12,130 --> 00:03:15,370
So let's try to understand this step over here.

41
00:03:15,910 --> 00:03:24,550
Now, the step of trust or faith is that you have to trust that this recursive call, which is like

42
00:03:24,550 --> 00:03:30,070
if we replace solving this sub problem over here with a recursive call.

43
00:03:31,030 --> 00:03:38,980
We have to trust that this recursive call will correctly solve a smaller version of your problem.

44
00:03:39,190 --> 00:03:44,470
Again, we will come back and try to understand this using the example at hand.

45
00:03:44,470 --> 00:03:46,870
So we have identified the problem.

46
00:03:46,870 --> 00:03:48,910
We have identified a sub problem.

47
00:03:48,910 --> 00:03:56,650
And we are saying in this step over here that if we replace solving the sub problem with a recursive

48
00:03:56,650 --> 00:04:05,080
call, we trust that if we have correctly designed the function, then this will be taken care by itself.

49
00:04:05,080 --> 00:04:07,840
So that is what this trust over here involves.

50
00:04:07,840 --> 00:04:16,390
Now because we trust this, we don't need to mentally simulate or unroll the whole recursion.

51
00:04:16,390 --> 00:04:16,840
Right.

52
00:04:16,840 --> 00:04:20,770
So this is the power of recursion if you set it up correctly.

53
00:04:20,770 --> 00:04:26,800
And if you have the correct base case as well, then it's going to take care of all the other smaller

54
00:04:26,800 --> 00:04:30,490
sub problems without you having to unroll mentally.

55
00:04:30,490 --> 00:04:32,290
All the various steps.

56
00:04:32,290 --> 00:04:35,920
So this makes recursion extremely powerful.

57
00:04:35,920 --> 00:04:39,430
Okay, so you assume your function works for simpler cases.

58
00:04:39,430 --> 00:04:41,680
It will work for more complex ones.

59
00:04:41,680 --> 00:04:49,210
So this is the step of the recursive leap of faith which makes recursion as we just now said, so powerful.

60
00:04:49,240 --> 00:04:56,650
Now let's go through the remaining steps, and then let's come back to this example again to understand

61
00:04:56,650 --> 00:04:57,730
this even better.

62
00:04:58,540 --> 00:05:03,730
Step number four is to link the original problem and the sub problem.

63
00:05:03,820 --> 00:05:10,690
Remember, in the previous video we had said that recursion is useful when solving the sub problem is

64
00:05:10,690 --> 00:05:13,390
helpful in solving the original problem.

65
00:05:13,390 --> 00:05:15,340
So that's what we're doing over here.

66
00:05:15,340 --> 00:05:19,000
We are linking the sub problem to the original problem.

67
00:05:19,000 --> 00:05:25,870
So in this case the original problem when n is equal to three is to print three, two, one, one,

68
00:05:25,870 --> 00:05:26,920
two and three.

69
00:05:26,950 --> 00:05:32,680
Now we have already taken care of 2112 because it's the sub problem.

70
00:05:32,680 --> 00:05:37,150
And we trust that the recursive call is going to give us this output over here.

71
00:05:37,150 --> 00:05:44,500
Now linking one and two would mean to ensure that if you're getting this, just ensure that you're getting

72
00:05:44,500 --> 00:05:47,230
these parts as well in the output.

73
00:05:47,230 --> 00:05:49,570
Again, more of this in a moment.

74
00:05:49,570 --> 00:05:55,660
The final step over here is to ensure that you have the base condition correctly written out.

75
00:05:55,660 --> 00:06:02,590
Because remember, for recursion you always need a base condition to avoid an infinite loop.

76
00:06:03,040 --> 00:06:10,030
Now in this case, for this example over here, let's say the base case is for zero just return because

77
00:06:10,030 --> 00:06:12,610
we just want to keep printing till one.

78
00:06:12,610 --> 00:06:15,880
So for example over here 54321.

79
00:06:15,880 --> 00:06:18,160
And then when you reach zero just return.

80
00:06:18,160 --> 00:06:19,330
We don't want to print it.

81
00:06:19,330 --> 00:06:19,870
All right.

82
00:06:19,870 --> 00:06:22,300
So let's say that's the base condition over here.

83
00:06:22,720 --> 00:06:25,240
Now of course you can write this in different ways.

84
00:06:25,240 --> 00:06:27,130
But let's just go with this for now.

85
00:06:27,130 --> 00:06:32,680
Now let's just make some space and revisit this problem over here.

86
00:06:32,680 --> 00:06:35,710
So and let's go through the five steps again.

87
00:06:35,710 --> 00:06:39,370
So we wanted to print 321123.

88
00:06:39,370 --> 00:06:43,270
And we identified that the sub problem is 2112.

89
00:06:43,300 --> 00:06:49,750
We trust that if we set the recursion recursive function correctly, if you write it correctly then

90
00:06:49,750 --> 00:06:54,130
this over here is going to be taken care by the recursive call.

91
00:06:54,130 --> 00:06:58,090
And then in step four we linked the sub problem.

92
00:06:58,090 --> 00:07:01,690
And the main problem that means we already have this part.

93
00:07:01,690 --> 00:07:06,310
And we just ensure that we get this also in the output for this example.

94
00:07:06,310 --> 00:07:09,070
And then we had the base case that for zero return.

95
00:07:09,460 --> 00:07:14,080
Let's now go ahead and write the pseudocode for this.

96
00:07:14,650 --> 00:07:17,680
Let's say we call the function seek okay.

97
00:07:17,680 --> 00:07:19,600
So seek for sequence.

98
00:07:19,600 --> 00:07:22,900
And we have the input n over here.

99
00:07:22,900 --> 00:07:26,890
And let's say we are giving three as the input now.

100
00:07:27,560 --> 00:07:28,430
Over here.

101
00:07:28,850 --> 00:07:35,090
We are going to replace 2112 with a recursive call to the same function.

102
00:07:35,090 --> 00:07:38,810
Because remember recursion is a function calling itself.

103
00:07:38,810 --> 00:07:43,730
So this over here is going to be written as seek with a smaller input.

104
00:07:43,730 --> 00:07:44,780
Over here we have n.

105
00:07:44,780 --> 00:07:47,990
So we're going to have an input closer to the base condition.

106
00:07:47,990 --> 00:07:53,360
Let's say that's n minus one because if n is three two is equal to n minus one.

107
00:07:53,360 --> 00:07:58,580
And then in step four we linked the original problem and the sub problem.

108
00:07:58,580 --> 00:08:03,860
So we have to ensure that we get this and this three over here as well in the output.

109
00:08:03,860 --> 00:08:04,340
All right.

110
00:08:04,340 --> 00:08:05,690
And n is three right.

111
00:08:05,690 --> 00:08:07,730
So this is n in the original problem.

112
00:08:07,730 --> 00:08:13,250
So this over here linking one and two in the pseudocode is going to look like this.

113
00:08:13,250 --> 00:08:18,650
Print n and then have the recursive call for n minus one to get this part over here.

114
00:08:18,650 --> 00:08:22,910
And then again print n to get this three also printed.

115
00:08:22,910 --> 00:08:25,460
So this is going to be the recursive case.

116
00:08:25,460 --> 00:08:29,270
And then finally we need to ensure that we have the base condition.

117
00:08:29,270 --> 00:08:33,290
So if n is equal to zero we're just gonna return.

118
00:08:33,290 --> 00:08:35,030
So this is the base case.

119
00:08:35,030 --> 00:08:38,510
And this over here is the recursive case.

120
00:08:39,020 --> 00:08:44,960
Now this part over here is what we call the inductive step.

121
00:08:45,350 --> 00:08:54,140
In simple terms induction which is a maths concept, is that if this is going to work for N then it's

122
00:08:54,140 --> 00:08:57,560
going to work for n minus one or it's the trust.

123
00:08:58,040 --> 00:08:58,430
All right.

124
00:08:58,430 --> 00:08:59,450
It's the trust part.

125
00:08:59,450 --> 00:09:03,560
If it's going to work for N it will work for n minus one as well.

126
00:09:03,560 --> 00:09:06,470
So again it will work for n because we have set it up correctly.

127
00:09:06,470 --> 00:09:06,740
Right.

128
00:09:06,740 --> 00:09:09,710
So if you have printed n so we got this three over here.

129
00:09:09,710 --> 00:09:13,430
Then we have done the recursive call to get this part over here.

130
00:09:13,430 --> 00:09:17,090
And we have done again print n to get this three over here.

131
00:09:17,090 --> 00:09:17,750
All right.

132
00:09:17,750 --> 00:09:24,650
So this over here is how we can apply recursion in a wide variety of problems.

133
00:09:24,650 --> 00:09:29,000
And again this will become more and more easy with a lot of practice.

134
00:09:29,000 --> 00:09:31,220
Let's take one more example over here.

135
00:09:32,180 --> 00:09:35,480
Let's say we want to find n factorial.

136
00:09:35,510 --> 00:09:42,650
Now quick side note n factorial is just n into n minus one into n minus two up to one.

137
00:09:42,650 --> 00:09:46,670
For example, three factorial is three into two into one.

138
00:09:46,700 --> 00:09:50,150
Now notice that let's say n is equal to five.

139
00:09:50,150 --> 00:09:52,700
We would want to find five factorial.

140
00:09:52,700 --> 00:10:00,500
Notice that five factorial actually can be solved as five into four factorial.

141
00:10:00,530 --> 00:10:01,010
Okay.

142
00:10:01,010 --> 00:10:07,160
So the second step which is identify the subproblem in this case would be four factorial.

143
00:10:08,870 --> 00:10:15,560
And it is the subproblem because if we know the value of four factorial, we can use it to solve the

144
00:10:15,560 --> 00:10:19,460
original problem, which is to find the value of five factorial.

145
00:10:19,460 --> 00:10:22,370
So four factorial is four into three into two into one.

146
00:10:22,370 --> 00:10:26,390
Let's say you know the value of four factorial as 24.

147
00:10:26,420 --> 00:10:34,310
Now you can use this 24 to find the value of five factorial, because five factorial is five into 24.

148
00:10:34,820 --> 00:10:35,360
All right.

149
00:10:35,360 --> 00:10:43,610
So we trust that if we set this up correctly such that it works for five factorial, then it's going

150
00:10:43,610 --> 00:10:45,530
to work for four factorial etc..

151
00:10:45,530 --> 00:10:46,010
Right.

152
00:10:46,010 --> 00:10:48,020
So that's our step number three.

153
00:10:48,020 --> 00:10:51,620
And we're going to link one and two which is five.

154
00:10:51,620 --> 00:10:54,920
Factorial is equal to five into four factorial.

155
00:10:54,920 --> 00:11:01,100
Or in general terms n factorial is going to be n into n minus one factorial.

156
00:11:01,100 --> 00:11:06,200
Notice this n minus one factorial is going to be a recursive call.

157
00:11:08,240 --> 00:11:08,600
All right.

158
00:11:08,600 --> 00:11:13,970
So this four factorial which is n minus one factorial is going to be a recursive call.

159
00:11:13,970 --> 00:11:17,600
And we trust that it's just going to work magically.

160
00:11:17,600 --> 00:11:20,960
We don't need to mentally unroll it completely okay.

161
00:11:20,960 --> 00:11:24,710
And again this over here is again is the inductive step.

162
00:11:24,710 --> 00:11:31,070
If it's working for N and it's working for N because we have set it up correctly, that for n factorial

163
00:11:31,070 --> 00:11:33,830
it's going to be n into n minus one factorial.

164
00:11:33,830 --> 00:11:37,430
So if it works for n it will work for n minus one.

165
00:11:37,430 --> 00:11:38,690
So that's induction.

166
00:11:38,690 --> 00:11:44,330
Again it means that when we are trying to find n minus one factorial, this same thing over here is

167
00:11:44,330 --> 00:11:50,510
going to take care of it as n minus one into n minus two factorial.

168
00:11:50,990 --> 00:11:51,620
Okay.

169
00:11:51,620 --> 00:11:57,500
And this is going to work because we are correctly setting it up and we are ensuring that there is a

170
00:11:57,500 --> 00:11:58,520
base condition.

171
00:11:58,520 --> 00:11:58,850
All right.

172
00:11:58,850 --> 00:12:01,400
So that's very important when you set it up.

173
00:12:01,580 --> 00:12:07,340
And the base condition over here let's say is if n is equal to one then just return one.

174
00:12:07,340 --> 00:12:10,940
Because notice over here we don't want to go further okay.

175
00:12:10,940 --> 00:12:14,000
So five factorial is five into four into three into two into one.

176
00:12:14,000 --> 00:12:16,610
We don't want to go further and we stop over here.

177
00:12:16,610 --> 00:12:18,860
So if n is equal to one then return.

178
00:12:18,860 --> 00:12:25,640
Now we will see in a future video how to make it very intuitive to identify the base condition.

179
00:12:25,970 --> 00:12:33,350
Basically, you can think of the base condition as the last valid input or the first invalid input,

180
00:12:33,350 --> 00:12:35,540
but more of that in a future video.

181
00:12:35,540 --> 00:12:42,650
So over here we have discussed the recursive leap of faith, which is what makes recursion so powerful

182
00:12:42,740 --> 00:12:48,260
and sometimes causes people to feel about recursion as if it is magic.