1
00:00:00,700 --> 00:00:01,840
Welcome back.

2
00:00:02,170 --> 00:00:08,500
Previously we have discussed how we can find n factorial using recursion.

3
00:00:08,500 --> 00:00:11,590
So that's the pseudocode we have over here.

4
00:00:12,130 --> 00:00:17,710
It's interesting to note that we could have achieved the same thing.

5
00:00:17,710 --> 00:00:23,110
That is we could have found n factorial iteratively as well.

6
00:00:23,110 --> 00:00:25,990
So that would be something like this.

7
00:00:25,990 --> 00:00:29,530
Let's say initially factorial is set to one.

8
00:00:29,530 --> 00:00:33,100
And then we iterate from 5 to 1.

9
00:00:33,850 --> 00:00:36,070
And then we just keep multiplying.

10
00:00:36,070 --> 00:00:37,960
So initially fact is one.

11
00:00:37,960 --> 00:00:39,370
And then I is five.

12
00:00:39,370 --> 00:00:42,880
So this becomes five into one.

13
00:00:42,880 --> 00:00:44,560
And then I becomes four.

14
00:00:44,560 --> 00:00:48,250
So we multiply to this four and then this becomes three.

15
00:00:48,250 --> 00:00:52,420
So we multiply it and we multiply two and we multiply one.

16
00:00:52,420 --> 00:00:57,220
So this over here also gives us five factorial.

17
00:00:57,220 --> 00:01:06,460
It's interesting to note that whatever we did using recursion could also be done using iteration.

18
00:01:06,460 --> 00:01:09,550
So this is an important thing that you should know.

19
00:01:09,550 --> 00:01:13,840
Things done recursively can also be done iteratively.

20
00:01:14,370 --> 00:01:23,040
Another thing to note when we compare recursion and iteration, is that an advantage of iteration over

21
00:01:23,040 --> 00:01:28,200
recursion is that it does not use space on the call stack.

22
00:01:28,200 --> 00:01:29,190
Recursion call stack.

23
00:01:29,190 --> 00:01:31,740
Okay, so we have seen the recursion call stack.

24
00:01:31,740 --> 00:01:32,700
We've visualized it.

25
00:01:32,700 --> 00:01:33,810
It's something like this right.

26
00:01:33,810 --> 00:01:35,370
We had all the calls over here.

27
00:01:35,550 --> 00:01:42,690
So when we solve the same problem iteratively we do not use recursive call stack space.

28
00:01:42,690 --> 00:01:51,000
So therefore you will see that in many coding interview questions you can achieve a better space complexity

29
00:01:51,000 --> 00:01:55,680
with an iterative solution as compared to a recursive solution.

30
00:01:55,680 --> 00:02:00,150
So this is another interesting point when we compare recursion and iteration.

31
00:02:00,480 --> 00:02:02,160
Another interesting point.

32
00:02:02,160 --> 00:02:10,140
And let me make some space over here when we compare recursion and iteration, is that recursion has

33
00:02:10,140 --> 00:02:15,870
both an ascending phase as well as a descending phase.

34
00:02:15,870 --> 00:02:17,700
Now what do I mean with that?

35
00:02:17,700 --> 00:02:22,350
Again, let's first take a look at iteration to understand this in a better manner.

36
00:02:22,350 --> 00:02:27,630
When it comes to iteration, it only has the ascending phase.

37
00:02:27,630 --> 00:02:36,450
So this means that we go from I equal to 5 to 1 in this case, and we iterate from 5 to 4 to 3 to 1,

38
00:02:36,450 --> 00:02:37,350
2 to 1.

39
00:02:37,350 --> 00:02:37,980
And that's it.

40
00:02:37,980 --> 00:02:38,250
Right?

41
00:02:38,250 --> 00:02:39,810
So there is no coming back.

42
00:02:39,810 --> 00:02:44,520
Once we've gone from 5 to 4, there is no coming back to five again.

43
00:02:44,640 --> 00:02:53,130
But when you take a look at recursion, notice over here that once we have like again let's let's take

44
00:02:53,130 --> 00:02:54,720
a look at the recursion call stack.

45
00:02:54,720 --> 00:02:57,180
So let's say we have f of five over here.

46
00:02:57,480 --> 00:03:00,000
And we have f of four over here.

47
00:03:00,000 --> 00:03:02,040
And we have f of three over here.

48
00:03:03,490 --> 00:03:10,090
Let's say F of one is popped out, F of two is popped out, and then we come back to F of three.

49
00:03:10,180 --> 00:03:12,610
So let's say we are again in the body over here.

50
00:03:12,610 --> 00:03:17,200
Notice that we are again over here when we get the value right.

51
00:03:17,200 --> 00:03:22,390
When we get the value of f of two, we are over here and we can do more things over here.

52
00:03:22,390 --> 00:03:25,480
I could print something or I could do some other operations.

53
00:03:25,480 --> 00:03:34,360
So recursion has not only an ascending phase, which is what iteration has, but recursion also has

54
00:03:34,360 --> 00:03:35,440
a descending phase.

55
00:03:35,440 --> 00:03:40,300
So this is something interesting which we can use in different questions.

56
00:03:40,750 --> 00:03:47,950
So the bottom line is that everything that is done recursively could be done iteratively.

57
00:03:47,950 --> 00:03:52,000
And we have seen that iterative solutions have better space complexity.

58
00:03:52,000 --> 00:03:55,690
So why use recursion if this is the case.

59
00:03:55,690 --> 00:04:05,050
The answer to that is that solutions written in a recursive way are many times more readable and easy

60
00:04:05,050 --> 00:04:09,550
to write and comprehend, especially when it comes to complex questions.

61
00:04:09,550 --> 00:04:17,170
So that is why recursion is a powerful tool, even though it has some disadvantages, such as it using

62
00:04:17,170 --> 00:04:19,330
more auxiliary space.