I think I have a solution.
Each call to f gives rise to two new calls to f recursively. One can think of it as a binary tree. Each call to f represents a node and the first f call in f goes to the left and the second to the right.
If k is equal to n or bigger then the recursion will be limited by n only. The imaginary binary tree will be complete and have a depth of n. The number of nodes, or rather f calls, will be 2^(n+1) - 1. Say n=1 for example that will give 3 f calls.
Now if k is made smaller than n it will start limiting the recursion. The imaginary binary tree will no longer be complete. Certain branches will be ignore because k has become smaller than 0 for certain paths and the recursion will stop until it reaches the maximum depth sey by n. This happens each time the second call to f in f has been called k+1 times because then k becomes negative (the first call to f in f leaves k unchanged)
The question now becomes: How many nodes, that is f calls, in the imaginary binary tree won't be visited because of k? If those are subtracted from the total number of nodes of the complete binary tree we have the number of actual f calls.
An analysis is somewhat involved. If a node is reached after more than k+1 "right child" calls to f then it should be subtracted from the total. But the result is simple and somewhat surprising. The number of not performed f calls can found in Pascal's triangle. One simply cuts out a subtriangle and add up all coefficients.
Code:
Pascal's triangle
---------------
1: 1 1
2: 1 2 1
3: 1 3 3 1
4: 1 4 6 4 1
5: 1 5 10 10 5 1
6: 1 6 15 20 15 6 1
Now if n=4 and k=1 you cut out this subtriangle from k+1 to n-1.
Code:
Subtriangle (cut from k+1=2 to n-1=3)
---------------------------------------------
2: 1
3: 1 3
You add up the numbers and double the sum. That's the number of nodes (f calls) that should be removed from the total which is 2^(n+1) - 1 according to the formula above. So we have f(4,1) = (2^(4+1) - 1) - 2*(1 + 1+3) = (32 - 1) - 2*5 = 21.
If instead n=6 and k=2 you get,
Code:
Subtriangle (cut from k+1=3 to n-1=5)
---------------------------------------------
3: 1
4: 1 4
5: 1 5 10
And f(6,2) = (2^(6+1) - 1) - 2*(1 + 1+4 + 1+5+10) = (128-1) - 2*22 = 83.
Since Pascal's triangle can be calculated in quadratic time the algorithm is O(N^2). On the other hand binominal coefficients quickly become very large so f(100, 50) is hardly tractable with standard arithmetic.