Using list comprehension to create a list of lists in a recursive function
<p>I am experimenting with recursive functions. My goal is to produce:</p>

<blockquote>
  <p>A function <code>combo</code> that generates all non-increasing series that add up to n</p>
</blockquote>

<p>Some sample inputs/outputs:</p>

<pre><code>&gt;&gt;&gt; print (combo(3))
[[3], [2, 1], [1, 1, 1]]
&gt;&gt;&gt; print (combo(4))
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
&gt;&gt;&gt; print (combo(5))
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
</code></pre>

<p>After a lot of trial and error, I came up with the following function which does exactly what I want:</p>

<pre><code>def combo(n, limit=None):
    if not limit:
        limit = n
    # return [ LIST COMPREHENSION HERE ]
    res = []
    for i in range(limit, 0, -1):
        if i == n:
            res.append([i])
        else:
            res.extend([i] + x for x in combo(n - i, min(n - i, i)))
    return res
</code></pre>

<p>My question: <strong>Is there a way (pythonic or not) to return this same result using a single list comprehension, without appending to and extending <code>res</code></strong>?</p>

<p>Here are two things I've tried, along with their mangled results:</p>

<pre><code>return [[i] if i == n else [[i] + x for x in combo(n - i, min(n - i, i))] for i in range(limit, 0, -1)]
# lists get deeper: [[4], [[3, 1]], [[2, 2], [2, [1, 1]]], [[1, [1, [1, 1]]]]]

return [[i if i == n else ([i] + x for x in combo(n - i, min(n - i, i))) for i in range(limit, 0, -1)]]
# parentheses interpreted as generator: [[4, &lt;generator object combo.&lt;locals&gt;.&lt;listcomp&gt;.&lt;genexpr&gt; at 0x01D84E40&gt;, etc.]]
</code></pre>

<p>I realize that the answer may be quite ugly, but I've spent enough time trying that I just want to know if it is <em>possible</em>.</p>

<p>Convert <em>extending</em> to <em>appending</em> and it becomes easier to grok how to convert this:</p>

<pre><code>res = []
for i in range(limit, 0, -1):
    if i == n:
        res.append([i])
    else:
        # this is the generator expression pulled out of the res.extend() call
        for x in combo(n - i, min(n - i, i)):
            res.append([i] + x)
</code></pre>

<p>You can now move the <code>i == n</code> case into the other branch (using a helper <code>items</code> variable here for readability):</p>

<pre><code>res = []
for i in range(limit, 0, -1):
    items = [[]] if i == n else combo(n - i, min(n - i, i))
    for x in items:
        res.append([i] + x)
</code></pre>

<p>If <code>i == n</code>, this causes the loop iterate once and produce an empty list, so you effectively get <code>res.append([i])</code>.</p>

<p>This can then trivially be converted to a list comprehension (inlining <code>items</code> into the <code>for</code> loop):</p>

<pre><code>return [
    [i] + x
    for i in range(limit, 0, -1)
    for x in ([[]] if i == n else combo(n - i, min(n - i, i)))]
</code></pre>

<p>Wether or not you <em>should</em> is another matter; this is hardly easier to read.</p>

python recursion list-comprehension