Converting a algorithm to a runtime function
The recursion for $g$'s running time is $$T(n)=n(T(n-1)+1)$$ where $1$ is the (constant) work done from the print statement and incrementing $k$. $g(n-1,k)$ and the constant work are called $n$ times from the for loop.
The recursion stops at $g(0,k)$ which has running time $T(0)=1$.

Solving this recursion on Mathematica (I suspect doing it by hand would involve induction or inspection) gave the result:
$$T(n)=\Gamma(n+1)+en\Gamma(n,1)$$
The complexity of this is
$$T(n)=O(\Gamma(n+1)+en\Gamma(n,1))$$
$$T(n)=O(n\Gamma(n,1))$$
Since $n$ is an integer, then we can reduce this to
$$T(n)=O(n!)$$