Let $X$ be countable:

We partition $X$ by the relation $x\sim y$ iff there are $n,k$ with $f^n(x)=f^k(y)$. If $X$ is countable and has infinitely many singleton components, $g$ can be chosen to permute them arbitrarily (and identity otherwise). This gives uncountably many possibilities for $g$.

If $X$ is countable and has infinitely many non-singleton components, then $g$ can be chosen as $f$ on some components, and as $f^2$ on others, which again gives you uncountably many possibilities.

Let $X$ be countable:

We partition $X$ by the relation $x\sim y$ iff there are $n,k$ with $f^n(x)=f^k(y)$. If $X$ is countable and has infinitely many singleton components, $g$ can be chosen to permute them arbitrarily (and identity otherwise). This gives uncountably many possibilities for $g$.

If $X$ is countable and has infinitely many non-singleton components, then $g$ can be chosen as $f$ on some components, and as $f^2$ on others, which again gives you uncountably many possibilities.

From now on assume that the set of all powers of $f$ is finite. Then there is some $n$ and $k>0$ with $f^{n+k}=f^n$.

If $X$ has only finitely many components, then there must be some $y$ with infinitely many predecessors. We can define infinitely many $g$ as follows:

• $g(y)=y$, and $g(z)=z$ whenever there is no $j>0$ with $f^j(z)=y$. Also $g(f^r(y))=f^r(y)$.
• Otherwise: for each $x$ with $f(x)=y$ (except possibly the one which is an iterated image of $y$) let $n_x$ be maximal such that there is $\bar x$ with $f^{n_x} (\bar x)=x$.
• Now let $g$ map any such $x$ to some $x'$ with $n_{x'}\ge n_x$. This defines $g$ on $f^{-1}(y)$. There are infinitely many possibilities for $g$.
• Now let $f^j(z)=y$, $j>1$. So $j\le n_z$. Consider $x:={f^{j-1}(z)}$. Let $g(z):= f^{n_{ g( x)}-j}(\overline{g(x)})$.