  Let $(G_n(x))_{n=0}^\infty$ be a $d$-th order linear recurrence sequence
having polynomial characteristic roots, one of which has degree strictly
greater than the others. Moreover, let $m\geq 2$ be a given integer. We ask for
$n\in\mathbb{N}$ such that the equation $G_n(x)=g\circ h$ is satisfied for a
polynomial $g\in\mathbb{C}[x]$ with deg$g=m$ and some polynomial
$h\in\mathbb{C}[x]$ with deg$h>1$. We prove that for all but finitely many $n$
these decompositions can be described in "finite terms" coming from a generic
decomposition parameterized by an algebraic variety. All data in this
description will be shown to be effectively computable.
