1
00:00:00,430 --> 00:00:07,420
Notice that for the Fibonacci question, the question itself is defined recursively.

2
00:00:07,450 --> 00:00:08,800
Now why do I say that?

3
00:00:08,800 --> 00:00:17,020
Because it's given in the question that f of n is equal to f of n minus one plus f of n minus two.

4
00:00:17,050 --> 00:00:24,220
So when we write a function to find the Fibonacci number for n, we would recursively call the same

5
00:00:24,220 --> 00:00:28,900
function with lower inputs n minus one and n minus two.

6
00:00:28,900 --> 00:00:33,400
And we will use these solutions to find the answer to f of n.

7
00:00:33,400 --> 00:00:37,030
So the question itself is recursively defined.

8
00:00:37,060 --> 00:00:40,930
Now the input is n and we need to find f of n.

9
00:00:40,930 --> 00:00:42,250
So that's the question.

10
00:00:42,280 --> 00:00:47,290
Now let me write the value of n for the Fibonacci series over here.

11
00:00:47,290 --> 00:00:49,840
So we have 0123.

12
00:00:49,840 --> 00:00:52,660
And it goes on in this manner over here.

13
00:00:52,690 --> 00:00:57,490
Notice that for n is equal to zero the output has to be zero.

14
00:00:57,490 --> 00:01:01,360
And for n is equal to one, the output has to be one.

15
00:01:01,360 --> 00:01:06,220
So these two are the last valid cases.

16
00:01:09,310 --> 00:01:16,150
Remember, we had discussed under recursion that you can identify the base case as either the last valid

17
00:01:16,150 --> 00:01:18,670
case or the first invalid case.

18
00:01:18,670 --> 00:01:24,880
So when we come up with the recursive approach, this over here will give us our base condition.

19
00:01:24,880 --> 00:01:28,960
Now the general condition is that for n.

20
00:01:29,840 --> 00:01:37,670
Or for finding f of n, we would just need f of n minus one and f of n minus two, and we have to add

21
00:01:37,670 --> 00:01:40,130
the values together these two values together.

22
00:01:40,130 --> 00:01:48,560
So to find f of n we will recursively call the same function with inputs n minus one and n minus two.

23
00:01:48,560 --> 00:01:53,510
And this over here is going to be our terminating condition or base condition.

24
00:01:53,510 --> 00:01:57,710
So this would be the recursive approach of solving this question.

25
00:01:57,710 --> 00:02:02,720
So basically the base condition is checking whether n is less than two.

26
00:02:02,750 --> 00:02:06,860
So if n is 0 or 1 we will just return n itself.

27
00:02:06,860 --> 00:02:08,210
That's the base case.

28
00:02:08,210 --> 00:02:15,890
And then in the other cases if that's not true we will just return f of n minus one plus f of n minus

29
00:02:15,890 --> 00:02:16,220
two.

30
00:02:16,220 --> 00:02:18,170
So this is the recursive approach.

31
00:02:18,170 --> 00:02:24,830
And remember this is the first step for coming up with the dynamic programming solution to a DP question.

32
00:02:24,830 --> 00:02:27,920
First we just write the recursive approach.

33
00:02:27,920 --> 00:02:32,120
So let's go ahead and code the solution that we just now discussed.