Can I solve KFIB by recursion?

help
, ,
1

I had a doubt if the problem [KFIB][1] can be solved by recursion. If so, could someone explain to me with an appropriate solution?

Thanks in advance!
[1]: Contest Page | CodeChef

2

Yes, It is Quite Simple to solve the problem using recursion.

You just have to follow the following recurrence relation:

f(n) = 1 , if(n less than or equal to k)
f(n) = k , if(n is equal to k + 1)
f(n) = 2*f(n - 1) - f(i - k - 1) , otherwise

In addition you have to use some memoization so that you do not end up with infinite recurrences.

You can refer to this code here for more details.

2 Likes