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]
CodePudding user response:
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
.
CodePudding user response:
The easiest way to explain IMO is to add more print
s 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]
.