1
00:00:00,580 --> 00:00:08,440
We have seen that recursion is nothing but a function calling itself until the base condition or the

2
00:00:08,440 --> 00:00:09,850
terminating condition.

3
00:00:09,850 --> 00:00:17,530
So the base condition tells the function when it can stop calling itself and then start returning.

4
00:00:17,530 --> 00:00:21,490
So that's what the base condition is all about now.

5
00:00:22,100 --> 00:00:30,830
The wrong way of trying to identify the base condition is trying to visualize the whole recursive sequence

6
00:00:30,830 --> 00:00:35,810
and then identifying when the function should stop calling itself.

7
00:00:36,020 --> 00:00:40,280
Especially you will find this difficult in complex questions.

8
00:00:40,310 --> 00:00:47,450
Now there is a better way of identifying the base condition for a recursive solution, and that is by

9
00:00:47,450 --> 00:00:54,740
thinking of either the last valid input or the first invalid input.

10
00:00:54,770 --> 00:01:01,550
Okay, so there are these two ways you can either think of the last valid case or the first invalid

11
00:01:01,550 --> 00:01:02,120
case.

12
00:01:02,450 --> 00:01:10,310
Now these two are pretty similar in that you could in some cases write either way the solution, or

13
00:01:10,310 --> 00:01:14,990
in some cases you will find that one of these is more easier to implement.

14
00:01:14,990 --> 00:01:21,410
But again, the point I'm trying to make over here is that to identify the base condition, don't try

15
00:01:21,410 --> 00:01:28,760
to visualize the whole recursive sequence, but rather just think of the last valid input or the first

16
00:01:28,760 --> 00:01:29,870
invalid input.

17
00:01:29,900 --> 00:01:35,060
Now let's take two examples to understand what I'm talking about over here.

18
00:01:35,060 --> 00:01:38,300
So over here we have two pseudo codes.

19
00:01:38,300 --> 00:01:43,400
So this over here is the pseudo code that we have seen to find n factorial.

20
00:01:43,400 --> 00:01:51,950
And notice that in this case the base case over here is the last valid input okay.

21
00:01:51,950 --> 00:01:55,790
So you can see that over here the last valid input is one.

22
00:01:55,790 --> 00:01:58,340
And in this case we are just returning one.

23
00:01:58,340 --> 00:02:00,980
And the function stops calling itself.

24
00:02:00,980 --> 00:02:10,100
Now we know that for example n factorial or let's say five factorial for simplicity is five into four

25
00:02:10,100 --> 00:02:13,070
into three into two into one and one over.

26
00:02:13,070 --> 00:02:15,920
Here is the last valid input.

27
00:02:15,920 --> 00:02:19,880
The next input over here would be zero which is not valid right.

28
00:02:19,880 --> 00:02:25,490
So at this point we have decided to stop calling the function and we are returning one.

29
00:02:25,490 --> 00:02:29,210
So this over here is one way of identifying the base condition.

30
00:02:29,210 --> 00:02:33,560
And the other way over here is to think of the first invalid input.

31
00:02:33,560 --> 00:02:41,870
For example, over here we have a function that can be used to print the values from n to one.

32
00:02:41,870 --> 00:02:42,200
Okay.

33
00:02:42,200 --> 00:02:44,090
So let's say n is equal to five.

34
00:02:44,090 --> 00:02:48,410
So the output would be five, four, three two and one.

35
00:02:48,530 --> 00:02:56,300
Now over here notice that the base case has been returned as the first invalid input.

36
00:02:56,300 --> 00:03:00,470
So the last valid input in this case is one.

37
00:03:00,470 --> 00:03:04,550
And after one we get to zero which is less than one.

38
00:03:04,550 --> 00:03:05,060
Right.

39
00:03:05,060 --> 00:03:08,450
And this over here is the first invalid input.

40
00:03:08,450 --> 00:03:12,650
So again you could you could write this in the other way as well.

41
00:03:12,650 --> 00:03:18,290
Like you could tweak this and write it such that the base case is based on the last valid input.

42
00:03:18,290 --> 00:03:22,430
But I'm writing it purposefully in this way over here to give an example.

43
00:03:22,430 --> 00:03:28,820
Now these two things are very helpful, especially in complex questions to come up with the relevant

44
00:03:28,820 --> 00:03:29,960
base condition.