Optimizing the problem
you can go to Dynamic programming. To achieve benefits do this you need overlapping recursion.

Easiest way yo program it, using a Map library as Memoization. Store any value calculated. Check any value from the map before calculation. This will eliminate the recalculations.

The simple case is always the Fibonacci Sequence, in which given $n$ find the $F(n) = F(n-1) + F(n-2)$.

You could see the overlappings easily. Make an array to store $F_i$ once found to prevent refound, Top-Down.

Buttom up; Start from the lowest of the recursion to reach the target. 

For your case you need a table of size $10^9 \times 1000$ to fill. If the size is big, you may reuse some rows.