Краткий ответ

За это отвечает таблица уже скопированных объектов — memo. copy.deepcopy сопоставляет идентификатор исходного объекта с его копией, поэтому циклические ссылки не вызывают бесконечную рекурсию, а несколько ссылок на один исходный объект указывают на один объект-копию.

Если класс определяет __deepcopy__, Python передаёт ему этот словарь. Пользовательская реализация должна зарегистрировать создаваемую копию в memo до рекурсивного копирования вложенных объектов.

Исторический контекст

Поверхностного копирования достаточно для простых структур, но оно сохраняет ссылки на вложенные изменяемые объекты. Глубокое копирование решает другую задачу: построить независимый граф объектов, сохранив его структуру.

В произвольном графе возможны циклы и несколько путей к одному объекту. Поэтому простой рекурсивный обход недостаточен: нужен механизм запоминания уже обработанных объектов.

Постановка проблемы

Рассмотрим объект, который ссылается сам на себя, либо два поля, указывающие на один общий дочерний объект. Наивная реализация глубокого копирования либо уйдёт в бесконечную рекурсию, либо создаст разные копии одного исходного объекта.

Это может нарушить инварианты программы. Например, после копирования два поля, которые должны ссылаться на один общий объект состояния, начнут ссылаться на независимые объекты.

Подробное решение

deepcopy использует словарь memo, где ключом обычно служит id исходного объекта, а значением — уже созданная копия. Перед рекурсивным копированием содержимого новая копия помещается в этот словарь.

При повторной встрече того же исходного объекта deepcopy возвращает объект из memo, не создавая новую копию и не обходя его повторно. Так одновременно сохраняются циклы и разделяемые ссылки.

Пользовательский класс может настроить копирование через __deepcopy__(memo). Метод сам создаёт экземпляр, сразу записывает его в memo, а вложенные значения копирует вызовом copy.deepcopy(value, memo).

import copy

class Node:
    def __init__(self, child=None):
        self.child = child

    def __deepcopy__(self, memo):
        clone = type(self).__new__(type(self))
        memo[id(self)] = clone
        clone.child = copy.deepcopy(self.child, memo)
        return clone

shared = Node()
root = Node(shared)
result = copy.deepcopy([root, shared])
print(result[0].child is result[1])  # True

Ключевой компромисс состоит в том, что пользовательская реализация получает контроль и может сохранить нужную структуру, но несёт ответственность за корректную регистрацию в memo. Если сделать это после копирования вложенных объектов, цикл всё ещё может привести к рекурсии, а если копировать вложенные значения без передачи того же memo, разделяемые ссылки будут потеряны.

Без собственного __deepcopy__ модуль copy использует встроенные правила для стандартных типов и механизмов объектов. Однако для ресурсов вроде файлов, сокетов или внешних дескрипторов глубокая копия обычно не имеет осмысленной семантики, поэтому класс может явно запретить её или вернуть специально созданное представление.

Ситуация из практики

В объектной модели документа несколько узлов могут совместно ссылаться на один объект стиля, а некоторые контейнеры допускают обратные ссылки на родителя. Обычный рекурсивный обход без memo либо зависает на обратной ссылке, либо размножает стиль при каждом обращении.

Вариант с ручным обходом всех полей даёт полный контроль, но дублирует логику copy и легко ошибается при добавлении нового поля. Поверхностная копия проще и быстрее, но оставляет изменяемые вложенные объекты общими.

Практичное решение — реализовать __deepcopy__, создавать экземпляр без повторного вызова обычного конструктора, немедленно помещать его в memo и передавать тот же словарь всем рекурсивным вызовам. Это сохраняет циклы и совместное использование объектов, а также позволяет отдельно обработать поля, которые нельзя или не нужно копировать.

Что кандидаты часто упускают

Можно ли просто вызвать конструктор класса внутри __deepcopy__?

Не всегда. Конструктор может требовать внешние зависимости, выполнять побочные эффекты или создавать состояние, которое затем будет заменено копируемыми полями. Часто безопаснее выделить экземпляр через __new__, а затем явно восстановить его состояние.
Что произойдёт, если передать новый словарь memo при копировании каждого вложенного поля?

Граф объектов будет разбит на независимые подграфы. Один и тот же исходный объект может получить несколько копий, а цикл перестанет корректно разрешаться или приведёт к рекурсии. Все рекурсивные вызовы в рамках одной операции должны использовать один и тот же memo.
Почему нельзя считать id исходного объекта постоянным идентификатором для хранения результата копирования?

id уникален только среди живых объектов в текущем процессе. После удаления объекта его идентификатор позднее может быть переиспользован Python для другого объекта. Поэтому memo является временной таблицей конкретной операции копирования, а не постоянным реестром соответствий между объектами.