F recursive and surjective. Show that it exists g such that g recursive and f * g = I

Question

Let $f : \mathbb{N} \rightarrow \mathbb{N}$ recursive and surjective. I need to prove that it exists a function g such that the composition of functions f * g = I where g is also recursive.

My idea : Let $f(0) = n_0 $ & $f(n+1)=h(f(n))$ for some recursive function $h$. Then define $g$ recursively as the inverse function of $f$. Obviously this doesn't work as I end up using the inverse function of $h$.

I also suspect my definition of a recursive function to be not 100% clear.

Any hint would be appreciated, thanks.

Answer 1

You can find $g(x)$ by computing $f(0), f(1), \ldots$ until you reach the (necessarily smallest) $y$ such that $f(y) =x$.

Crucial point: Because $f$ is surjective, this is guaranteed to terminate for every $x$.