Question

Answer this question using recursion. Show step by step to solve this question

1. F(n) = F(n-1) + F(n-2)

where:

F(0) = 0 F(1) = 1

Answer 1

First of all we need to understand here what recursion is ??

So recursion is performing similar task again and again until we don't reach to the condition where we can terminate or in programming terms we say it as base case.

So here in your question we have to calculate F(n) which is equivalent to F(n-1) + F(n-2).

Here if you will look closely than F(n-1) is same as F(n) but the only difference is of n as it gets decremented by 1 here ,same is the case with F(n-2).

But hold on lets think for a second .

Take n=10

Now according to the question F(n) will call first F(n-1) i.e F(9) than F(9) will call F(8) and this procedure will go on forever .....is this the case??

NO!

So to get rid of this problem we are provided with the BASE CASES i.e as soon as we reach at the base case we can return from there .

So here as soon as n reaches 0 or 1 it returns 1 from there and than other recursion calls take place.

Diagramatically the recursion calls work as follow:

Taking n=5

For your info i may tell you that above equation is a well known problem of recursion as if referred as FIBONACCI SEQUENCE.

SO F(5) will call F(4) and F(3)

then first F(4) calls will occur then after it recieves its answer than F(3) calls will occur then finaaly after summing both values we are going to get the answer.

AS you can see in the diagram -- first the nodes of the tree that are on the left are called first then the nodes of the trees on the right are called .

Hope it clarify your doubts and now you will have no problem regarding recursion.

Please upvote my answer as it will give the boost to write more quality answers!!