  The Fibonacci numbers are the prototypical example of a recursive sequence,
but grow too quickly to enumerate sets of integer partitions. The same is true
for the other classical sequences $a(n)$ defined by Fibonacci-like recursions:
the tribonacci, Padovan, Pell, Narayana's cows, and Lucas sequences. For each
sequence $a(n)$, however, we can define a related sequence $\textrm{sa}(n)$ by
defining $\textrm{sa}(n)$ to have the same recurrence and initial conditions as
$a(n)$, except that $\textrm{sa}(2n)=\textrm{sa}(n)$. Growth is no longer a
problem: for each $n$ we construct recursively a set $\mathcal{SA}(n)$ of
partitions of $n$ such that the cardinality of $\mathcal{SA}(n)$ is
$\textrm{sa}(n)$. We study the properties of partitions in $\mathcal{SA}(n)$
and in each case we give non-recursive descriptions. We find congruences for
$\textrm{sa}(n)$ and also for $\textrm{psa}(n)$, the total number of parts in
all partitions in $\mathcal{SA}(n)$.
