Convert for loop to recursion to deep copy a nested list

Question

Need your help in converting this function to use only recursion. Currently it's using a for loop and recursion but it needs to use only recursion. The function gets a list or a nested list and needs to return a copied list (deep copy!).

And I can not import deepcopy from copy or use list comprehension.

def my_deepcopy(nested_list: List[Any]) -> List[Any]:
    results = []
    for item in nested_list:
        if not isinstance(item, list):
            results.append(item)
        else:
            results.append(my_deepcopy(item))
    return results

This is what I was asked for. If I could I would use it but unfortunately I can't — Avi Doe
– Avi Doe, Commented Aug 7, 2022 at 14:58

Samwise · Accepted Answer · 2022-08-07 14:46:36Z

3

The standard way to turn an iterative function into a recursive function is to have a base case for an empty list, and then add the recursive result from the first list item to the results for the remaining list items. E.g.:

>>> def list_deepcopy(item):
...     if not isinstance(item, list) or not item:
...         return item
...     return [list_deepcopy(item[0])] + list_deepcopy(item[1:])
...
>>> a = [1, 2, [3, 4, [5, 6]]]
>>> b = list_deepcopy(a)
>>> a[0] *= 10
>>> a[2][0] *= 10
>>> a[2][2][0] *= 10
>>> a
[10, 2, [30, 4, [50, 6]]]
>>> b
[1, 2, [3, 4, [5, 6]]]

edited Aug 7, 2022 at 14:46

answered Aug 7, 2022 at 14:39

Samwise

72.1k3 gold badges36 silver badges52 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Avi Doe Over a year ago

Thank you very much but I forgot to mention I can not use list comprehension also. I'm gonna update the post

Thierry Lathuille Over a year ago

@AviDoe There is no list comprehension here...

Avi Doe Over a year ago

Thank you! But now I wonder if there is a way to not use slicing on the list and achieve the same thing. If you have any idea how to do that I'd be glad to hear. Nevertheless your solution helped me

Mechanic Pig · Accepted Answer · 2022-08-07 15:55:04Z

1

Method without slicing:

def list_deepcopy(lst, start=0):
    if not isinstance(lst, list):
        return lst
    if start == len(lst):
        return []

    return [list_deepcopy(lst[start])] + list_deepcopy(lst, start + 1)

Some test:

>>> a = [1, [2, [3, [4, [5]]]]]
>>> b = list_deepcopy(a)
>>> a
[1, [2, [3, [4, [5]]]]]
>>> b
[1, [2, [3, [4, [5]]]]]
>>> from functools import reduce
>>> from itertools import repeat
>>> from operator import getitem
>>> for i in range(5):
...     reduce(getitem, repeat(1, i), a)[0] *= 10
... 
>>> a
[10, [20, [30, [40, [50]]]]]
>>> b
[1, [2, [3, [4, [5]]]]]

answered Aug 7, 2022 at 15:55

Mechanic Pig

7,7813 gold badges17 silver badges35 bronze badges

Collectives™ on Stack Overflow

Convert for loop to recursion to deep copy a nested list

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related