How do python list items change if they are involved in recursive loops?

user_13966775 0
Viewed 77

This function reverses all the items found in the list. Even the inner lists get reversed. My problem is that I do not understand how the reversed_list keeps 7 and 6 after the recursion. Since once the deep_reverse is called, the reversed_list becomes empty and then it keeps the reverse of the inner list which is [5, 4, 3]. What I do not realize is that once this item is appended the reversed_list becomes [7, 6, [5, 4, 3]]

def deep_reverse(arr):
    
    # Terminaiton / Base condition
    if len(arr) < 1:
        return arr

    reversed_items = []  # final list to be returned
    for item in arr[::-1]:
        
        # If this item is a list itself, invoke deep_reverse to reverse the items recursively.
        if type(item) is list:
            item = deep_reverse(item)
        
        # append the item to the final list
        reversed_items.append(item)
        print(reversed_items)

    return reversed_items ```

deep_reverse([1, 2, [3, 4, 5], 6, 7])
#printing the reversed_list
[7]
[7, 6]
[5]
[5, 4]
[5, 4, 3]
[7, 6, [5, 4, 3]]
[7, 6, [5, 4, 3], 2]
[7, 6, [5, 4, 3], 2, 1]
recursive-datastructures recursion data-structures python
2 Answers

There's more than one reversed_list

You say:

once the deep_reverse is called, the reversed_list becomes empty

But there isn't just one reversed_list. Every call creates a new list (and happens to bind it to a local variable of the same name), but the original call's reversed_list continues to exist independently of the ones for each recursive call. This is the point of the program's call stack: Each invocation of a function gets its own space, with its own local variables, separate from that of all other calls (including those to the same function).

Each new call of deep_reverse puts another call frame on top of the existing one, with its own reversed_list. After it finishes populating it, it returns it, and the caller (which may be deep_reverse itself, given the recursion) can do what it likes with it. In the case of your recursive calls, this means rebinding item, which is now bound to the list previously stored in the recursive call's reversed_list, which can then be appended to the outer call's own reversed_list.

user_3646960

The easiest way to explain IMO is to add more prints to your function so you can visualize the call stack:

def deep_reverse(arr, level=0):
    if len(arr) < 1:
        return arr

    reversed_items = []  # final list to be returned
    print(level * "  ", f"deep_reverse({arr}) -> ...")
    for item in arr[::-1]:
        
        # If this item is a list itself, invoke deep_reverse to reverse the items recursively.
        if type(item) is list:
            item = deep_reverse(item, level+1)
        
        # append the item to the final list
        reversed_items.append(item)
        print(level * "  ", reversed_items)

    print(level * "  ", f"... -> {reversed_items}")
    return reversed_items

deep_reverse([1, 2, [3, 4, 5], 6, 7])

prints:

 deep_reverse([1, 2, [3, 4, 5], 6, 7]) -> ...
 [7]
 [7, 6]
   deep_reverse([3, 4, 5]) -> ...
   [5]
   [5, 4]
   [5, 4, 3]
   ... -> [5, 4, 3]
 [7, 6, [5, 4, 3]]
 [7, 6, [5, 4, 3], 2]
 [7, 6, [5, 4, 3], 2, 1]
 ... -> [7, 6, [5, 4, 3], 2, 1]

The [3, 4, 5] -> [5, 4, 3] is a separate call to deep_reverse, with its own arr and reversed_items, which you can hopefully visualize more easily now that it's got an extra level of indentation.

When it's done, its result is appended to the outer call's reversed_items, and the outer call continues on with the remaining items in arr[::-1].

user_37997590
Related