Let's say we have some three term recursion $$x_{n+1} = f(x_n, x_{n-1})$$ where $f : \mathbb R^2 \to \mathbb R$ is sufficiently differentiable.
If for instance $f$ only depends on $x_n$ and $\Vert \nabla f \Vert \leq L$ for some $L < 1$ we could apply the Banach fixed point theorem.
But are there any similar theorems for when $f$ actually depends on both arguments?
One possibility is just reducing the problem back to the simple recursion, similar to the way you can reduce higher order differential equations to a system of first order equations:
Let us define $F(x, y) = (f(x, y), x)$, then the recursion defined by $x_{n+1} = f(x_n, x_{n+1})$ is equivalent to
$$(x_{n+1}, x_n) = (f(x_n, x_{n-1}), x_n) = F(x_n, x_{n-1})$$
or for $X_n := (x_n, x_{n-1})$ we can write that as $X_{n+1} = F(X_n)$. Now we can apply Banach to this new equation, provided that
$$\Vert F(X) - F(Y) \Vert \leq L \Vert X - Y \Vert$$
for some $L < 1$.
If $f$ is sufficiently differentiable, then we can use the induced matrix norm (depending on what norm we chose above) of the Jacobian of $F$ to find some $L$, that is
$$DF = \begin{bmatrix}\partial_x f & \partial_y f \\ 1 & 0 \end{bmatrix}.$$
This approach can be generalized to recursion of arbitrary degree.