What is the running time of this recursive algorithm?
You can write your recurrence as
$$
T(n) = (n+1)(T(n-1) + 2T(n-2) + T(n-3) + 2T(n-4) + \cdots).
$$
In particular, $T(n) \geq (n+1) T(n-1)$. This means that the sequence $T(n)$ grows very rapidly, and in particular
$$
T(n-1) + 2T(n-2) + \cdots \leq T(n-1) \left[ 1 + \frac{2}{n} + \frac{1}{n(n-1)} + \frac{2}{n(n-1)(n-2)} + \cdots \right] = (1+O(1/n)) T(n-1).
$$
Therefore
$$
T(n) \leq (n+O(1)) T(n-1).
$$
This means that
$$
T(n) = O((n+O(1))!),
$$
and so
$$
T(n) = O\left(n^{O(1)} (n/e)^n\right).
$$
This improves on your bound by a square root.