After trying to understand your description of how it should be the recursion, i have come to believe that what you need is something like the following
k[0] := 0;
k[1] := 1;
k[2] := 2;
k[3] := 3;
k[n_] := 1 + k[n - 1] /; n > 3;
I tried the following values to try to make sure that works well the recursion,
Table[k[i], {i, {4, 5, 9, 13, 7, 11, 13, 17, 43, 47, 53, 59, 61, 67,
71}}]
I think that the following link may help you to understand more things about how to solve your problem, applied the same idea to your project.
Mathematica, Fibonacci sequence using While and Module commands