Let $G$ be a connected graph of uniformly bounded degree. A $k$ non-backtracking random walk ($k$-NBRW) $(X_n)_{n =0}^{\infty}$ on $G$ evolves according to the following rule: Given $ (X_n)_{n =0}^{s}$, at time $s+1$ the walk picks at random some edge which is incident to $X_s$ that was not crossed in the last $k$ steps and moves to its other end-point. If no such edge exists then it makes a simple random walk step. Assume that for some $R>0$ every ball of radius $R$ in $G$ contains a simple cycle of length at least $k$. We show that under some "nice" random time change the $k$-NBRW becomes reversible. This is used to prove that it is recurrent iff the simple random walk is.