Что возвращать в рекурсии при пустом узле?

Что возвращать в рекурсии при пустом узле?

В рекурсивных алгоритмах, работающих с деревьями или связанными списками, пустой узел (null) является базовым случаем (base case). Он сигнализирует о том, что дальнейшая рекурсия не нужна, и алгоритм должен вернуть некоторое значение, которое корректно завершит вычисления.

Общие правила

• Если функция ищет элемент или проверяет условие, при null возвращается null или false.
• Если функция вычисляет сумму, количество или другую агрегированную величину, при null возвращается нейтральный элемент (0 для суммы, 1 для произведения, пустой массив для сбора данных).
• Если функция строит новую структуру данных, при null возвращается null или пустая структура.

Примеры

Поиск элемента в бинарном дереве поиска:

function searchBST(root, val) {
  if (root === null) return null; // базовый случай
  if (root.val === val) return root;
  if (val < root.val) return searchBST(root.left, val);
  return searchBST(root.right, val);
}

Подсчёт суммы всех узлов дерева:

function sumTree(root) {
  if (root === null) return 0; // нейтральный элемент для суммы
  return root.val + sumTree(root.left) + sumTree(root.right);
}

Сбор всех значений в массив (обход в глубину):

function collectValues(root) {
  if (root === null) return []; // пустой массив для конкатенации
  return [root.val, ...collectValues(root.left), ...collectValues(root.right)];
}

Вывод

Правильный выбор возвращаемого значения для пустого узла критичен для корректной работы рекурсии. Всегда определяйте, какое значение является нейтральным для вашей операции (null, 0, пустой массив, false), и используйте его в базовом случае. Это обеспечит правильное завершение рекурсии и корректный результат.