1
00:00:00,410 --> 00:00:06,080
‫So in this video we're going to use recursion to solve for a factorial.

2
00:00:06,590 --> 00:00:12,200
‫So this four with an exclamation point is four factorial.

3
00:00:12,620 --> 00:00:20,390
‫So if you've never seen a factorial before, four factorial is four times three times two times one.

4
00:00:20,840 --> 00:00:27,020
‫So I'm going to move this up here and we're going to look at why a factorial is a great thing to solve

5
00:00:27,020 --> 00:00:28,250
‫with recursion.

6
00:00:28,880 --> 00:00:37,700
‫So if you take these three numbers here three times, two times one, that would be three factorial.

7
00:00:37,940 --> 00:00:47,120
‫So that means that four factorial is equal to four times three factorial and three factorial is equal

8
00:00:47,120 --> 00:00:55,640
‫to three times two factorial, and two factorial is equal to two times one factorial.

9
00:00:56,030 --> 00:01:00,170
‫But something different happens when we do one factorial.

10
00:01:00,200 --> 00:01:03,140
‫One factorial is one.

11
00:01:03,470 --> 00:01:06,260
‫So this is our base case.

12
00:01:06,710 --> 00:01:10,310
‫So there are two requirements for recursion.

13
00:01:10,730 --> 00:01:17,750
‫First, the process that we're doing each time that we call the function needs to be the same.

14
00:01:18,050 --> 00:01:22,880
‫And you can see that we're doing the same thing over and over here.

15
00:01:23,390 --> 00:01:29,240
‫And the second requirement was that each time we need to be making the problem smaller.

16
00:01:29,510 --> 00:01:35,720
‫So I'm going to take these numbers and shrink them down into the corner and just bring in all of the

17
00:01:35,720 --> 00:01:37,820
‫code for factorial.

18
00:01:38,420 --> 00:01:40,970
‫It is just these lines.

19
00:01:41,600 --> 00:01:43,820
‫So we pass it an integer.

20
00:01:43,820 --> 00:01:46,940
‫N in this case that's going to be four.

21
00:01:47,240 --> 00:01:51,350
‫We're going to check to see if N is equal to one.

22
00:01:51,710 --> 00:01:54,950
‫So this will be this one here.

23
00:01:55,160 --> 00:01:59,630
‫And when we return, one that's going to be this one here.

24
00:01:59,960 --> 00:02:07,610
‫And if N is not equal to one, we'll return in times factorial of N minus one.

25
00:02:07,970 --> 00:02:11,420
‫And this is where the function calls itself.

26
00:02:11,980 --> 00:02:18,670
‫So in this case in is equal to four and then in minus one is equal to three.

27
00:02:19,630 --> 00:02:23,680
‫So now let's move this up into the corner and walk through this.

28
00:02:24,600 --> 00:02:30,150
‫So we start out with factorial of PN, which in this case is four.

29
00:02:30,570 --> 00:02:35,160
‫So the first thing we're going to do is check to see if MN is equal to one.

30
00:02:35,550 --> 00:02:37,740
‫And in this case, in is equal to four.

31
00:02:37,740 --> 00:02:40,970
‫So the conditional in this if statement will be false.

32
00:02:40,980 --> 00:02:48,480
‫And then we move down to here and then we're going to say return in times factorial of MN minus one.

33
00:02:48,480 --> 00:02:51,360
‫So that's going to be four and three.

34
00:02:51,780 --> 00:02:57,450
‫So now we have a new instance of the factorial function added to the call stack.

35
00:02:57,690 --> 00:03:02,710
‫And in this instance, the first line will run is this line is in equal to one.

36
00:03:02,730 --> 00:03:04,560
‫Well, now it's equal to three.

37
00:03:04,890 --> 00:03:07,530
‫So we're going to come down to this line.

38
00:03:08,370 --> 00:03:13,770
‫So now in this case in is three in minus one is two.

39
00:03:14,190 --> 00:03:18,600
‫So we'll do this check again if an is equal to one and is equal to two.

40
00:03:18,630 --> 00:03:21,690
‫So this is going to be false and we're going to come down to here.

41
00:03:22,110 --> 00:03:28,740
‫So now N is equal to two and n minus one is equal to one.

42
00:03:29,130 --> 00:03:34,380
‫Now, for this instance of factorial in is equal to one.

43
00:03:34,650 --> 00:03:42,150
‫So we're going to return one like this, and that's going to be this one here.

44
00:03:42,780 --> 00:03:48,150
‫So now let's take a closer look at just these lines and we'll spread these out a little bit.

45
00:03:48,510 --> 00:03:51,970
‫When we say return one on the bottom here.

46
00:03:51,990 --> 00:03:53,820
‫Where is it returning it?

47
00:03:54,240 --> 00:04:00,630
‫It's being returned to this instance of factorial, because factorial of one is going to be equal to

48
00:04:00,630 --> 00:04:00,990
‫one.

49
00:04:00,990 --> 00:04:03,990
‫So it's going to return it up here.

50
00:04:04,470 --> 00:04:11,490
‫And this return statement is returning to this instance of factorial and this return statement is returning

51
00:04:11,490 --> 00:04:14,670
‫to this one and so on up the line.

52
00:04:15,300 --> 00:04:19,860
‫So now let's take out the arrows and walk through this step by step.

53
00:04:20,280 --> 00:04:28,740
‫Factorial one is equal to one, two times one equals two and factorial two.

54
00:04:28,860 --> 00:04:30,160
‫That's equal to two.

55
00:04:30,180 --> 00:04:31,740
‫That's where you return.

56
00:04:31,740 --> 00:04:38,130
‫This two, three times two equals six and factorial three is equal to six.

57
00:04:38,130 --> 00:04:43,470
‫That's what this is getting passed up to four times six equals 24.

58
00:04:43,740 --> 00:04:47,040
‫And we return this to the original function call.

59
00:04:47,430 --> 00:04:51,960
‫So now let's look at this same thing a couple of different ways.

60
00:04:52,290 --> 00:04:55,080
‫Let's use the example of a gift box.

61
00:04:55,470 --> 00:05:01,470
‫But instead of looking for a ball like we did a couple of videos ago, we're looking for the number

62
00:05:01,470 --> 00:05:02,230
‫one.

63
00:05:02,250 --> 00:05:04,470
‫This gift box does not contain a one.

64
00:05:04,470 --> 00:05:05,820
‫It contains a four.

65
00:05:06,090 --> 00:05:10,320
‫So that means that this gift box contains another gift box.

66
00:05:10,590 --> 00:05:12,980
‫This one doesn't contain a one either.

67
00:05:12,990 --> 00:05:16,920
‫So that means it contains another gift box in this case is going to be two.

68
00:05:17,010 --> 00:05:20,910
‫And this gift box contains yet another gift box.

69
00:05:20,910 --> 00:05:23,580
‫But you can see that this gift box is different.

70
00:05:23,790 --> 00:05:28,050
‫This is going to be the gift box that contains the one.

71
00:05:28,230 --> 00:05:29,520
‫This is the base case.

72
00:05:29,520 --> 00:05:32,310
‫This is the equivalent of finding the ball.

73
00:05:32,730 --> 00:05:39,360
‫So it's going to return the one back up to this instance of the function factorial this function right

74
00:05:39,360 --> 00:05:44,220
‫here, and two times one is two that gets returned up here.

75
00:05:44,250 --> 00:05:51,990
‫That's going to be this function of factorial two and then three times two is six, six gets passed

76
00:05:51,990 --> 00:05:52,380
‫up.

77
00:05:52,380 --> 00:05:57,690
‫That's going to be this function, four times six is 24.

78
00:05:58,200 --> 00:06:00,990
‫So now let's look at this a third way.

79
00:06:01,020 --> 00:06:02,610
‫I'm going to bring up the call stack.

80
00:06:02,610 --> 00:06:05,670
‫We talked about a call stack in the last video.

81
00:06:06,000 --> 00:06:12,780
‫We're going to run factorial four and that's going to add an instance of the factorial function to the

82
00:06:12,780 --> 00:06:17,550
‫call stack and then will say return four times factorial three.

83
00:06:17,550 --> 00:06:20,430
‫That adds another item to the call stack.

84
00:06:20,670 --> 00:06:24,960
‫This is another instance of the function factorial.

85
00:06:25,260 --> 00:06:30,210
‫So in the last video we were seeing function one, function two, function three.

86
00:06:30,210 --> 00:06:37,350
‫In this case, both of these functions are named factorial, and then we'll do this again and add factorial

87
00:06:37,350 --> 00:06:45,660
‫of two to the call stack and then factorial of one to the call stack and factorial one is going to return

88
00:06:45,660 --> 00:06:46,260
‫one.

89
00:06:46,260 --> 00:06:52,710
‫And once it does that, it's done running and it gets popped from the call stack and now we can return

90
00:06:52,710 --> 00:07:01,230
‫three times factorial to we pop that from the call stack and so on, and then finally factorial four.

91
00:07:01,230 --> 00:07:05,970
‫We return 24 and pop that from the call stack as well.

92
00:07:06,420 --> 00:07:10,740
‫So now let's flip over and take a look at this NVS code.

93
00:07:11,440 --> 00:07:16,690
‫So what I've done here is I've created a breakpoint and I've already started running this.

94
00:07:16,690 --> 00:07:23,080
‫I came up here on the dropdown and I selected Debug C and C++ file.

95
00:07:23,080 --> 00:07:28,840
‫I've already done this step and I am skipping a couple of steps here, but we covered this in the last

96
00:07:28,840 --> 00:07:33,520
‫video and you can see that Main is already on the call stack.

97
00:07:34,430 --> 00:07:41,240
‫So I'm going to come up here and this button step into when I click on this, it's going to run this

98
00:07:41,240 --> 00:07:47,060
‫line here and it will add an instance of factorial to the call stack.

99
00:07:47,060 --> 00:07:52,580
‫So I'm going to click on this and you can see that Factorial has been added to the call stack.

100
00:07:53,090 --> 00:07:59,780
‫And so that is factorial being run with a value of four and it's going to check to see is in equal to

101
00:07:59,780 --> 00:08:00,260
‫one.

102
00:08:00,260 --> 00:08:01,310
‫It is not.

103
00:08:01,310 --> 00:08:05,360
‫And that would come down here and this will add another instance of factorial.

104
00:08:05,570 --> 00:08:11,030
‫So we'll click on this and you can see that we have another instance of factorial.

105
00:08:11,510 --> 00:08:14,090
‫I'm just clicked through this a couple more times.

106
00:08:14,510 --> 00:08:15,950
‫This is with two.

107
00:08:16,550 --> 00:08:19,070
‫So N is not equal to one.

108
00:08:19,070 --> 00:08:26,180
‫And we come down here and then we'll add our final instance of factorial when I click this again, when

109
00:08:26,180 --> 00:08:31,430
‫it runs this and we have four instances of factorial.

110
00:08:31,430 --> 00:08:35,150
‫So this is what we just saw in the animation of the call stack.

111
00:08:35,480 --> 00:08:43,340
‫And now for this instance of factorial that we just added in is equal to one and we return one.

112
00:08:43,340 --> 00:08:46,400
‫So when I click on this, it's going to jump down here.

113
00:08:46,760 --> 00:08:53,240
‫And when I click on this again, that top instance of factorial is going to be popped from the call

114
00:08:53,240 --> 00:08:53,600
‫stack.

115
00:08:53,600 --> 00:08:55,040
‫So I'll click on this.

116
00:08:55,640 --> 00:09:00,320
‫And now we only have three instances of factorial on the call stack.

117
00:09:00,770 --> 00:09:06,770
‫So in the last video we had separate instances of functions on the call stack, but they all had different

118
00:09:06,770 --> 00:09:07,130
‫names.

119
00:09:07,130 --> 00:09:10,310
‫They were different functions with recursion.

120
00:09:10,310 --> 00:09:12,320
‫We're putting functions with the same name.

121
00:09:12,320 --> 00:09:17,570
‫The same function is being called over and over and added to the call stack.

122
00:09:17,870 --> 00:09:23,240
‫So now I'm going to come over and click on this button and you can see it says Continue.

123
00:09:23,240 --> 00:09:29,120
‫When I click on this, it'll just play this to the end instead of doing this line by line.

124
00:09:29,420 --> 00:09:37,880
‫So I'm going to click on this and you can see up here we get our value of 24 returned and with that

125
00:09:37,880 --> 00:09:43,580
‫it looks like we have a working recursive function for factorial.