Implement a special kind of recurrence relation as a infinite list

A common recurrence has the form $$a_n=\{\begin{array}{ll}{\sum }_{i=0}^{\infty }{b}_i{a}_{n-m_i}& \text{if }n>k\\ c_n& \text{if }n\le k\end{array}$$ , where $m_i$ and $b_i$ are both infinite sequences, and $c_i$ is a finite sequence. $m_i\in \mathbb{N}$. $a_{-i}=0$ for all positive $i$. This is well defined as long as $b_i,a_i,c_i$ are in the same ring.

One can use a balanced binary tree to store the entire infinite list, and the time to generate the $n$th element is $O(d(n)\log n)$, where $d$ is the density function of $\left\{m_i\right\}$.

Using an array would make it $O(d(n))$, but it is too imperative for our taste, how about we only use list and achieve $O(d(n))$ time, elegantly?

The idea is that we are summing the first item of infinite many stacks. However we don’t have to really sum the infinite stacks, we only sum the stack we require. The code:

What’s a practical usage of this? Produce a infinite list of partition numbers, such that finding the first $n$ elements can be done in $O(n^{\frac{3}{2}})$ time and 3 lines of code. The code