1
00:00:00,420 --> 00:00:03,960
‫So now we're going to do our introduction to recursion.

2
00:00:04,320 --> 00:00:12,870
‫And my favorite definition of recursion is that it is a function that calls itself until it doesn't.

3
00:00:13,320 --> 00:00:20,280
‫So to explain this, I'm going to bring up a gift box and we need to open the gift box.

4
00:00:20,280 --> 00:00:22,620
‫So how do we open gift boxes?

5
00:00:22,950 --> 00:00:27,840
‫We open gift boxes by calling the open gift box function.

6
00:00:28,110 --> 00:00:37,650
‫And when we open the gift box, we could get a gift, in this case, a ball, or we could get a smaller

7
00:00:37,680 --> 00:00:38,940
‫gift box.

8
00:00:39,270 --> 00:00:46,680
‫And the way that we open gift boxes is with the open gift box functions we're calling the same function

9
00:00:46,680 --> 00:00:47,580
‫again.

10
00:00:47,850 --> 00:00:56,850
‫And when we call this function on this gift box, we can get a gift, a ball or a smaller gift box.

11
00:00:57,330 --> 00:01:01,140
‫Once again, we call the open gift box function.

12
00:01:01,470 --> 00:01:05,730
‫And in this case, we'll say that this box contains the ball.

13
00:01:06,630 --> 00:01:12,200
‫So now let's put this back and we're going to write some pseudo code.

14
00:01:12,210 --> 00:01:16,020
‫So don't try to write this code because it won't work.

15
00:01:16,020 --> 00:01:18,030
‫It's just pseudocode.

16
00:01:18,510 --> 00:01:21,480
‫So we'll have a function called Open Gift Box.

17
00:01:21,480 --> 00:01:26,160
‫It returns a pointer to an object that is a ball.

18
00:01:26,520 --> 00:01:30,870
‫So when we run this function, we'll either get a ball or a gift box.

19
00:01:30,870 --> 00:01:32,040
‫We need to test for that.

20
00:01:32,040 --> 00:01:34,470
‫We'll say if is ball.

21
00:01:34,470 --> 00:01:41,160
‫In other words, if what's inside of the box is a ball, we're going to return the ball.

22
00:01:41,490 --> 00:01:46,890
‫Now, if we were writing real code, we would probably have a line that looks like this that actually

23
00:01:46,890 --> 00:01:48,240
‫creates the ball.

24
00:01:48,330 --> 00:01:53,970
‫But I want to keep this simple, so I'm going to remove this line and just keep the if statement.

25
00:01:54,300 --> 00:01:59,970
‫So if the conditional in this if statement is false, that means we have a gift box.

26
00:02:00,180 --> 00:02:04,950
‫And if we have a gift box, we need to run open gift box.

27
00:02:05,220 --> 00:02:08,820
‫And this is where the function calls itself.

28
00:02:09,210 --> 00:02:12,220
‫So in recursion, there are a couple of rules.

29
00:02:12,240 --> 00:02:21,330
‫First, the process of opening each new box is the same or the process of doing whatever it is that

30
00:02:21,330 --> 00:02:24,330
‫you're doing has to be the same.

31
00:02:24,660 --> 00:02:32,790
‫The other rule is that each time we open a box, we make the problem smaller or whatever it is that

32
00:02:32,790 --> 00:02:38,550
‫you're doing with recursion, each step has to be smaller than the step before.

33
00:02:38,940 --> 00:02:43,080
‫So that's why I show the gift box is getting smaller and smaller.

34
00:02:43,740 --> 00:02:49,200
‫So let's remove these and then we'll walk through this code and show how it would work.

35
00:02:49,650 --> 00:02:52,950
‫First, you call the open gift box function.

36
00:02:53,700 --> 00:02:56,190
‫We're going to check to see, is this a ball?

37
00:02:56,190 --> 00:02:57,870
‫And in this case, it is not.

38
00:02:57,900 --> 00:02:59,280
‫It is a gift box.

39
00:02:59,280 --> 00:03:02,910
‫So we're going to need to run the open gift box function.

40
00:03:03,300 --> 00:03:08,340
‫And this adds another instance of open gift box to the call stack.

41
00:03:08,670 --> 00:03:12,990
‫And we'll talk about the call stack in more detail in the next video.

42
00:03:13,290 --> 00:03:16,980
‫So now with this gift box, we're going to say, is this a ball?

43
00:03:17,190 --> 00:03:18,690
‫And in this case, it is not.

44
00:03:18,690 --> 00:03:25,860
‫It is another gift box, which means we need to run open gift box again, which adds another instance

45
00:03:25,860 --> 00:03:29,610
‫of the open gift box function to the call stack.

46
00:03:30,060 --> 00:03:32,700
‫Now, we'll check to see, is this a ball?

47
00:03:32,700 --> 00:03:34,550
‫In this case, it is.

48
00:03:34,560 --> 00:03:37,440
‫So we will return the ball.

49
00:03:37,800 --> 00:03:44,070
‫And because we ran this return statement, we are not going to run this line of code.

50
00:03:44,610 --> 00:03:47,340
‫We're just going to return the ball.

51
00:03:48,040 --> 00:03:52,240
‫So now let's put this back and talk a little bit about terminology.

52
00:03:52,270 --> 00:03:58,570
‫If this box contains the ball, this is what is called a base case.

53
00:03:58,870 --> 00:04:04,690
‫Once we get to the base case, we don't want to keep calling new instances of the function.

54
00:04:05,320 --> 00:04:09,430
‫If this is a gift box, this is what is called a recursive case.

55
00:04:09,430 --> 00:04:14,350
‫This is where we need to call another instance of the open gift box function.

56
00:04:14,680 --> 00:04:19,840
‫And this is also a recursive case, and this is our base case.

57
00:04:20,560 --> 00:04:22,840
‫So let's bring back our code.

58
00:04:23,320 --> 00:04:31,240
‫So this if statement is what we do when we reach our base case, if we don't have a base case and we

59
00:04:31,240 --> 00:04:38,260
‫remove this, you run an instance of the function and then it runs this line, which creates another

60
00:04:38,260 --> 00:04:44,650
‫instance of the function, which runs this line, which creates another instance of the function.

61
00:04:44,920 --> 00:04:50,770
‫And we end up in an infinite loop of adding new instances of the function to the call stack.

62
00:04:50,770 --> 00:04:54,760
‫And if that happens, you get what is called a Stack Overflow.

63
00:04:54,940 --> 00:05:01,540
‫So you have to have something like this which will break us out of that loop of adding new instances

64
00:05:01,540 --> 00:05:02,950
‫to the call stack.

65
00:05:03,350 --> 00:05:06,170
‫So there are two essential parts in this if statement.

66
00:05:06,170 --> 00:05:10,160
‫First, this conditional has to be true at some point.

67
00:05:10,400 --> 00:05:15,860
‫So if you have something like this, if one is greater than two, well, that can never be true.

68
00:05:15,890 --> 00:05:21,260
‫Which means we will end up in that infinite loop of creating new instances.

69
00:05:21,410 --> 00:05:27,260
‫So you might look at that and say, Well, that is obvious that one is not greater than two, but you

70
00:05:27,260 --> 00:05:31,490
‫could have something more complex than this in your conditional.

71
00:05:31,760 --> 00:05:36,830
‫So if you're getting a Stack Overflow, this is one of the places to troubleshoot.

72
00:05:37,460 --> 00:05:39,380
‫So I'm going to bring this back.

73
00:05:39,800 --> 00:05:42,980
‫And the other thing is you need to have a return statement.

74
00:05:43,220 --> 00:05:47,340
‫So let's take this out and replace it with see out.

75
00:05:47,360 --> 00:05:48,230
‫Hello.

76
00:05:48,590 --> 00:05:55,370
‫In this situation, once this conditional becomes true, all we're doing is outputting the word hello.

77
00:05:55,550 --> 00:05:58,500
‫And because it is not a return statement.

78
00:05:58,520 --> 00:06:04,370
‫Once you run this line of code, you're just going to come right down here and go back into that loop

79
00:06:04,370 --> 00:06:06,920
‫of adding instances to the call stack.

80
00:06:07,220 --> 00:06:15,950
‫So it is very important that you have this return statement, and that is our introduction to recursion.