Pythons objects can be recursive
Python objects can be recursive! for example, to a list you can add itself as an element.
NOTE: In an interview I was asked to serialize a given python object. The object can be any valid type in python, for ex: list, dict, tuple, set etc and it can also be a primitive type. In that I was asked to identify if do you prevent infinite recursion if the object is added to itself somewhere inside.
For example,
a = [1,2,3]
a.append(a)
print(a)
Python’s copy module highlights this problem. To find recursive objects and prevent processing them, we can keep track of the id’s of the objects. Python objects will have unique id.
def has_recursion(obj, seen=None):
if seen is None:
seen = set()
obj_id = id(obj)
if obj_id in seen:
return True
seen.add(obj_id)
if isinstance(obj, dict):
for k, v in obj.items():
if has_recursion(k, seen) or has_recursion(v, seen):
return True
elif isinstance(obj, (list, tuple, set)):
for item in obj:
if has_recursion(item, seen):
return True
seen.remove(obj_id)
return False
# Example
a = []
a.append(a)
print(has_recursion(a)) # True
b = [1, 2, 3, [4, 5]]
print(has_recursion(b)) # False
We can’t use == because it checks for elements in the objects to be equal which is not we wanted, we wanted if two objects are referring to the same memory location.
a = [1, 2]
b = [1, 2]
print(a == b) # True, same *values*
a = []
a.append(a)
print(a == a) # Fine
print(a == [a]) # Also fine, same structure
b = [a]
# If you compare a and b deeply, equality would loop forever.