Understanding list comprehension that uses recursion

Question

I am currently learning about list comprehension and come across this line of recursive code:

ans = [sort(a, i + 1) for a in ans]

I have tried substituting that line with the following:

for a in ans:
    ans = (sort(a, i + 1))

Could somebody please help me understand where I have made a mistake?

thanks!

Answer 1

The for loop and the list comprehension are not equivalent.

Imagine we have:

>>> def sort(a, _): return 2*a
...
>>> i=0

Then:

>>> ans=list(range(5))
>>> ans = [sort(a, i + 1) for a in ans]
>>> ans
[0, 2, 4, 6, 8]

But:

>>> ans=list(range(5))
>>> for a in ans: ans=(sort(a, i+1))
>>> ans
8

The list comprehension basically:

• applies sort(a, i+1) to every a in ans
• then assigns the result to the variable ans itself.

As said by @chepner in a comment, there is no recursion here^[1]. It's equivalent to:

>>> ans=list(range(5))
>>> new_ans = [sort(a, i + 1) for a in ans]
>>> ans = new_ans
>>> new_ans
[0, 2, 4, 6, 8]

While the for loop:

• iterates over ans:
• assigns sort(a, i+1) to ans for every a

Hence, the assignements give: ans = sort(ans[0], i+1), then ans = sort(ans[1], i+1), ..., ans = sort(ans[-1], i+1) where ans[-1] is the last element of the original ans².

The loop equivalent of your list comprehension is:

>>> ans=list(range(5))
>>> new_ans=[]
>>> for a in ans: new_ans.append(sort(a, i+1))
>>> ans = new_ans # assignement here
>>> ans
[0, 2, 4, 6, 8]

---

^[1] A function may use recursion, but I'm not sure what recursion would mean for a list comprehension unless you use some dirty hack: for the record https://stackoverflow.com/a/221874/6914441.

^[2] Note that the reassignement of the variable ans does not modify the original list:

• when the loop begins, Python creates an iterator over the list and keeps a reference on the list;
• when the ans is reaffected, the for loop has still the reference on the original list.

It would be different if you modify the list from within the loop body (strongly discouraged):

>>> xs=list(range(5))
>>> for x in xs: print(x, xs);_=xs.pop(0)
...
0 [0, 1, 2, 3, 4]
2 [1, 2, 3, 4]
4 [2, 3, 4]

We remove the first element for every iteration, but the index continues to grow:

[*0*, 1, 2, 3, 4] # then pop 0
[1, *2*, 3, 4] # then pop 1
[2, 3, *4*] # then pop 2