Solving recurrence relations that involve all previous terms I'm not sure if this a proper recurance relation per se but I'd be interested in the methodology in solving a recurrence relation of the following form:
$Z_0 = 1$
$Z_1 = x_1$
$Z_2 = x_1Z_1 + x_2 = x_1^2 + x_2$
$Z_3 = x_1Z_2 + x_2Z_1 + x_3 = x_1^3 + x_1x_2 + x_1x_2 + x_3$
$Z_n = x_1 Z_{n-1} + x_2 Z_{n-2} + ... + x_n Z_0$
As written, each term requires the knowledge of the previous terms. Is it possible to write down a closed form for $Z_n$? For this particular recurrence, I can write down the result  of $Z_n$  but I would be very interested in seeing how one can derive this from the recurrence relation itself. My gut feeling is that a generating function is lurking underneath all this.

To answer the general question in the title ("solving recurrence relations that involve all previous terms"), such relations can be thought of as path- or history-dependent calculations and one tries to replace them by equivalent state-dependent (Markovian) calculations that retain a finite amount of state information and keep transforming the state, but not remembering any additional information. 
For example, if the recurrence is
$S_n = S_0 + S_1 + \dots S_{n-1}$     
this is equivalent, for $n>1$,  to $S_n = S_{n-1} + S_{n-1} = 2S_{n-1}$, and remembering the previous term is enough to reproduce the recurrence as iterated doubling (after the first two terms).
The example in the question is also an iteration of a single transformation, but on an unbounded-dimensional state space.
