1
00:00:00,800 --> 00:00:01,730
Hey everyone!

2
00:00:01,730 --> 00:00:02,690
Welcome back!

3
00:00:02,690 --> 00:00:08,360
We have discussed so far various interesting things regarding recursion.

4
00:00:08,360 --> 00:00:15,650
Another important thing to know about recursion is that you can write recursive solutions, either going

5
00:00:15,650 --> 00:00:18,950
from zero to n or n to zero.

6
00:00:18,950 --> 00:00:27,740
Now remember, it's interesting to know that this is possible, but if you can practice writing solutions

7
00:00:27,740 --> 00:00:35,120
in both ways, it's very helpful because it will help you develop a good grip on solving coding interview

8
00:00:35,120 --> 00:00:35,780
questions.

9
00:00:35,780 --> 00:00:38,420
So let's go ahead and try this out together.

10
00:00:39,150 --> 00:00:48,270
So let's say the question at hand is given n find the value of one plus, two plus, etc. up to n.

11
00:00:48,270 --> 00:00:50,040
So this is the question at hand.

12
00:00:50,400 --> 00:00:53,910
Let's try to solve this question in both ways.

13
00:00:53,910 --> 00:01:00,480
We are going to do it recursively, and we will do it from zero to n as well as n to zero.

14
00:01:00,480 --> 00:01:06,630
First let's write the recursive solution where we are going from zero to n.

15
00:01:06,870 --> 00:01:09,300
Let's write the pseudocode for this okay.

16
00:01:09,780 --> 00:01:11,160
So let's get started.

17
00:01:11,220 --> 00:01:15,570
Now let's say I have a function and I call it sum.

18
00:01:15,570 --> 00:01:21,570
And I have the parameters the current sum and n over here.

19
00:01:21,570 --> 00:01:25,200
And I'm passing the initial sum as zero.

20
00:01:25,200 --> 00:01:27,330
And I want to add up till five.

21
00:01:27,330 --> 00:01:29,700
So zero comma five are my inputs.

22
00:01:29,700 --> 00:01:40,560
And then the recursive case is that I'm just gonna return curr plus sum of cr plus one up to n okay.

23
00:01:40,560 --> 00:01:44,130
And again let's draw out the recursion tree for this.

24
00:01:44,130 --> 00:01:48,210
And the base case is going to be that if I hit five right.

25
00:01:48,210 --> 00:01:52,230
If I reach five if cr is equal to n.

26
00:01:52,230 --> 00:01:53,850
And in this case that's five.

27
00:01:53,850 --> 00:01:58,350
So if CR is equal to n then I'm just gonna return n.

28
00:01:58,350 --> 00:02:00,690
So let's see if this will work.

29
00:02:01,200 --> 00:02:06,360
So initially I'm going to call sum with the parameters zero and five.

30
00:02:06,360 --> 00:02:08,460
So sum zero comma five.

31
00:02:08,460 --> 00:02:14,820
And inside the body of the function cr at this point is zero which is not equal to five.

32
00:02:14,820 --> 00:02:21,900
So it's gonna recursively call sum of cr plus one and again pass n as five.

33
00:02:21,900 --> 00:02:27,120
So that's sum of one comma five and cr at this point is zero right.

34
00:02:27,120 --> 00:02:31,500
So again when we return it's going to be zero plus sum of one comma five.

35
00:02:31,500 --> 00:02:37,800
So this sum of zero comma five is gonna recursively call sum of one comma five.

36
00:02:37,860 --> 00:02:40,920
And then again we are inside the function cr is one.

37
00:02:40,920 --> 00:02:42,240
It's not equal to five.

38
00:02:42,240 --> 00:02:45,990
So we're going to call recursively sum of two comma five.

39
00:02:45,990 --> 00:02:52,020
This is going to recursively call sum of three comma five which again is going to call sum of four comma

40
00:02:52,020 --> 00:02:52,530
five.

41
00:02:52,530 --> 00:02:55,740
And this is going to call sum of five comma five.

42
00:02:55,740 --> 00:03:00,450
At this point CR is equal to n or five is equal to five.

43
00:03:00,450 --> 00:03:06,810
So we have said that we have hit the base or terminating condition and let's just return n.

44
00:03:06,810 --> 00:03:08,400
So n is equal to five.

45
00:03:08,400 --> 00:03:09,870
So this over here.

46
00:03:11,070 --> 00:03:13,230
Is gonna return five.

47
00:03:13,950 --> 00:03:14,520
Okay.

48
00:03:14,520 --> 00:03:18,780
So this the value of this is going to be four plus five.

49
00:03:18,810 --> 00:03:19,290
Okay.

50
00:03:19,290 --> 00:03:25,740
So sum of four comma five is going to give the value nine okay.

51
00:03:25,740 --> 00:03:29,790
So this over here will become three plus nine which is.

52
00:03:30,380 --> 00:03:31,220
12.

53
00:03:31,250 --> 00:03:31,700
Okay.

54
00:03:31,700 --> 00:03:34,640
So some of three comma five is going to be 12.

55
00:03:34,640 --> 00:03:37,730
And this is going to return two plus 12 which is 14.

56
00:03:37,730 --> 00:03:42,170
So some of two comma five will be 1414 plus one is 15.

57
00:03:42,170 --> 00:03:44,480
So some of one comma five is 15.

58
00:03:44,480 --> 00:03:46,910
And then we're going to add zero to it.

59
00:03:46,910 --> 00:03:52,430
And thus some of zero comma five is gonna return the value 15 okay.

60
00:03:52,430 --> 00:03:56,150
So one plus two up to five has the value 15.

61
00:03:56,790 --> 00:04:00,600
So we have solved this question using recursion.

62
00:04:00,600 --> 00:04:09,840
And notice that we went from zero to n over here it's zero car is one, two, three, four and five.

63
00:04:09,840 --> 00:04:10,350
Right.

64
00:04:10,350 --> 00:04:14,310
So we solve this question by going from zero to n.

65
00:04:14,550 --> 00:04:19,770
Now let's try to solve the same question by going from n to zero.

66
00:04:20,770 --> 00:04:22,510
Let's write the pseudo code for it.

67
00:04:22,510 --> 00:04:23,470
So.

68
00:04:24,380 --> 00:04:25,640
Let's write it over here.

69
00:04:25,670 --> 00:04:34,280
Now I could write the function sum as sum and the input is n, and I'm calling it with the input parameter

70
00:04:34,280 --> 00:04:34,850
five.

71
00:04:34,850 --> 00:04:40,490
And then the recursive case could be returned n plus sum of n minus one.

72
00:04:40,490 --> 00:04:41,930
And the base case is.

73
00:04:41,930 --> 00:04:44,570
If n is zero return just return.

74
00:04:44,570 --> 00:04:44,930
All right.

75
00:04:44,930 --> 00:04:50,300
So notice that the base case changes based on how you write it over here.

76
00:04:50,300 --> 00:04:53,840
The last valid case is going to be one.

77
00:04:53,840 --> 00:04:56,270
Or the first invalid case is going to be zero.

78
00:04:56,270 --> 00:04:56,600
Right.

79
00:04:56,600 --> 00:05:02,990
So you can think of the base case as the first as the last valid case or the first invalid case.

80
00:05:02,990 --> 00:05:09,260
And in this case because we were going from zero to n, so zero one up to five.

81
00:05:09,260 --> 00:05:13,550
So we had five over here, which was the last valid case.

82
00:05:13,550 --> 00:05:17,060
So the base case changes based on how you write it.

83
00:05:17,240 --> 00:05:23,090
Now let's draw the recursion tree for this solution over here.

84
00:05:23,090 --> 00:05:25,730
So initially we call sum of five.

85
00:05:25,730 --> 00:05:30,620
And this is going to call sum of four right n plus sum of four.

86
00:05:30,620 --> 00:05:32,930
And this is going to call sum of three.

87
00:05:33,980 --> 00:05:37,220
And this over here is going to call sum of two.

88
00:05:37,910 --> 00:05:42,590
Which in turn will call some of one, which in turn will call some of zero.

89
00:05:42,590 --> 00:05:47,960
And at this point we will hit our base condition and we will just return.

90
00:05:47,960 --> 00:05:49,760
So this is just going to return.

91
00:05:50,640 --> 00:05:51,210
Okay.

92
00:05:51,210 --> 00:05:53,190
So we could say return zero okay.

93
00:05:53,190 --> 00:05:54,690
So let's say return zero.

94
00:05:54,690 --> 00:05:59,340
So this value over here is going to be one plus zero which is equal to one.

95
00:05:59,340 --> 00:06:00,810
So this is going to be one.

96
00:06:00,810 --> 00:06:03,780
And this is going to return two plus one which is three.

97
00:06:03,780 --> 00:06:06,120
So s of two is going to be three.

98
00:06:06,240 --> 00:06:12,690
Now S of three is going to be three plus three which is six S of four is going to be four plus six which

99
00:06:12,690 --> 00:06:13,560
is ten.

100
00:06:13,560 --> 00:06:18,240
And S of five is going to be five plus ten which is 15.

101
00:06:18,240 --> 00:06:23,580
So in this way notice that we went from five to 4 to 3 up to zero.

102
00:06:23,580 --> 00:06:25,620
Or we went from n to zero.

103
00:06:25,620 --> 00:06:31,800
So you can write recursive solutions going from zero to n or n to zero.

104
00:06:31,800 --> 00:06:34,680
So try to write at least a few questions.

105
00:06:34,680 --> 00:06:41,580
Try to practice writing the solution in both ways, so that you get a good grip on solving coding.

106
00:06:41,580 --> 00:06:44,250
Interview questions using recursion.