Complexity of recursive solution to coin change
A general method for solving recurrences of this form is generating functions. The exact solution also depends on the initial values. In your case, one possible solution is $T(n,k) = C 2^{n+k}$.