Notice that for the Fibonacci question, the question itself is defined recursively.
Now why do I say that?
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.
So when we write a function to find the Fibonacci number for n, we would recursively call the same
function with lower inputs n minus one and n minus two.
And we will use these solutions to find the answer to f of n.
So the question itself is recursively defined.
Now the input is n and we need to find f of n.
So that's the question.
Now let me write the value of n for the Fibonacci series over here.
So we have 0123.
And it goes on in this manner over here.
Notice that for n is equal to zero the output has to be zero.
And for n is equal to one, the output has to be one.
So these two are the last valid cases.
Remember, we had discussed under recursion that you can identify the base case as either the last valid
case or the first invalid case.
So when we come up with the recursive approach, this over here will give us our base condition.
Now the general condition is that for n.
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
the values together these two values together.
So to find f of n we will recursively call the same function with inputs n minus one and n minus two.
And this over here is going to be our terminating condition or base condition.
So this would be the recursive approach of solving this question.
So basically the base condition is checking whether n is less than two.
So if n is 0 or 1 we will just return n itself.
That's the base case.
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
two.
So this is the recursive approach.
And remember this is the first step for coming up with the dynamic programming solution to a DP question.
First we just write the recursive approach.
So let's go ahead and code the solution that we just now discussed.