1
00:00:06,380 --> 00:00:13,790
Recursion is a technique that allows a program to call itself one or more times until a specified condition

2
00:00:13,790 --> 00:00:14,390
is met.

3
00:00:14,960 --> 00:00:21,740
Once the condition is met, the calculations are then processed from the last one called to the first.

4
00:00:22,670 --> 00:00:28,460
So let's start off with a pretty simple example so that we can get a really good understanding of how

5
00:00:28,460 --> 00:00:29,690
recursion works.

6
00:00:29,960 --> 00:00:33,260
So we will do factorial.

7
00:00:34,130 --> 00:00:38,780
And you might already be familiar with this because it's pretty common.

8
00:00:39,560 --> 00:00:48,230
So we have in factorial, which is the same as in times n minus one times n minus two times n minus

9
00:00:48,230 --> 00:00:50,720
three and so on and so forth.

10
00:00:51,530 --> 00:00:59,000
Well we can actually rewrite this as n factorial is equal to n times.

11
00:00:59,770 --> 00:01:03,310
In minus one factorial.

12
00:01:06,070 --> 00:01:17,110
And with that, then we can assume we have a function called factorial that takes in.

13
00:01:18,440 --> 00:01:29,210
And what we can do is we can say, well, the answer to that is equal to n times the factorial of n

14
00:01:29,210 --> 00:01:30,320
minus one.

15
00:01:30,590 --> 00:01:35,690
So we can have this function, represent this right here.

16
00:01:37,520 --> 00:01:45,170
So what does this look like when we try to calculate from the last called to the first?

17
00:01:45,440 --> 00:01:48,320
Well, we can look at the call stack.

18
00:01:51,590 --> 00:01:52,130
Right.

19
00:01:52,970 --> 00:01:55,040
And so we'll draw it out right here.

20
00:01:59,020 --> 00:02:00,160
Put a couple of.

21
00:02:02,460 --> 00:02:03,500
Frozen.

22
00:02:04,760 --> 00:02:06,590
And so we have.

23
00:02:07,600 --> 00:02:08,410
Main.

24
00:02:09,860 --> 00:02:13,940
And then we have we'll say factor five.

25
00:02:15,170 --> 00:02:17,400
Factor for.

26
00:02:19,500 --> 00:02:22,320
Factor of three.

27
00:02:23,440 --> 00:02:34,360
Factor of two, and then we'll add another one right here just for clarity, and we will put one there.

28
00:02:35,320 --> 00:02:42,130
So when we go to unwind, actually scratch, that will go this way, right?

29
00:02:42,130 --> 00:02:44,140
So we start at the main function.

30
00:02:44,470 --> 00:02:45,910
So this is the start.

31
00:02:46,270 --> 00:02:55,480
So as we do our executions, we then call factorial of five, which then calls factorial of four, which

32
00:02:55,480 --> 00:02:59,140
then calls factorial of three, two.

33
00:02:59,140 --> 00:03:00,970
And then at the end we have one.

34
00:03:00,970 --> 00:03:05,860
So this is the order as it.

35
00:03:07,260 --> 00:03:08,400
Execute.

36
00:03:09,420 --> 00:03:14,820
So remember I said recursion calculations are processed from the last one called.

37
00:03:15,030 --> 00:03:16,170
So this is the.

38
00:03:19,160 --> 00:03:20,930
Paul is the one.

39
00:03:20,930 --> 00:03:23,420
And now we begin unwinding

40
00:03:25,760 --> 00:03:26,780
our stack.

41
00:03:27,200 --> 00:03:31,370
So we will have one times factorial of two.

42
00:03:32,090 --> 00:03:41,750
Times factorial the three times factorial of four times factorial of five, and then our value is returned.

43
00:03:46,000 --> 00:03:47,140
Is returned.

44
00:03:48,820 --> 00:03:56,470
So now that we have a good understanding of how this works, let's go implement this and rust so that

45
00:03:56,470 --> 00:03:58,270
we can really see it in action.