Какие условия корректной рекурсии?

Рекурсия — это техника в программировании, когда функция вызывает саму себя для решения задачи, разбивая её на более мелкие подзадачи того же типа. Для того чтобы рекурсия работала корректно и безопасно, необходимо соблюдать два фундаментальных условия.

1. Базовый случай (Base Case)

Это условие, при котором функция завершает работу, не совершая новых рекурсивных вызовов. Базовый случай служит точкой остановки, предотвращая бесконечную цепочку вызовов. Без него рекурсия будет продолжаться до тех пор, пока не исчерпает стек вызовов, что приведёт к ошибке переполнения стека (stack overflow).

2. Рекурсивный случай (Recursive Case)

Это часть функции, где происходит вызов самой себя. Ключевое требование: каждый рекурсивный вызов должен приближать состояние задачи к базовому случаю. Обычно это означает, что аргументы функции изменяются (например, уменьшаются) с каждым шагом.

Пример: Вычисление факториала

Рассмотрим классический пример вычисления факториала числа n (n!).

function factorial(n) {
  // Базовый случай: факториал 0 или 1 равен 1
  if (n <= 1) {
    return 1;
  }
  // Рекурсивный случай: n! = n * (n-1)!
  // Аргумент (n-1) приближается к базовому случаю (1)
  return n * factorial(n - 1);
}

console.log(factorial(5)); // Вывод: 120

В этом примере базовый случай — n <= 1. Рекурсивный вызов factorial(n - 1) гарантирует, что значение n уменьшается с каждым шагом, в конечном итоге достигая 1.

Где применяется рекурсия?

Рекурсия широко используется в алгоритмах и структурах данных:

• Обход деревьев и графов (например, DOM-дерево в браузере).
• Алгоритмы "разделяй и властвуй" (быстрая сортировка, сортировка слиянием).
• Решение задач комбинаторики и динамического программирования.
• Обработка вложенных структур данных (JSON, XML).

Вывод: Рекурсию стоит применять, когда задача естественным образом разбивается на идентичные подзадачи, и вы можете чётко определить условие остановки. Это делает код часто более чистым и читаемым по сравнению с итеративными решениями для определённых классов задач (например, обход деревьев). Однако важно помнить о потенциальных затратах памяти из-за стека вызовов.