Что такое рекурсия?

Рекурсия в программировании

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

Основные компоненты рекурсии

Каждая рекурсивная функция должна содержать:

1. Базовый случай (base case) — условие выхода, которое предотвращает бесконечный цикл
2. Рекурсивный случай (recursive case) — вызов функции с упрощённым или меньшим аргументом
3. Прогресс к базовому случаю — каждый рекурсивный вызов должен приближаться к выходу

Простой пример: факториал

// Рекурсивный подход
function factorial(n) {
  // Базовый случай
  if (n === 0 || n === 1) {
    return 1;
  }
  // Рекурсивный случай
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120
// factorial(5) = 5 * factorial(4)
// factorial(4) = 4 * factorial(3)
// factorial(3) = 3 * factorial(2)
// factorial(2) = 2 * factorial(1)
// factorial(1) = 1 (базовый случай)

Стек вызовов

Важно понимать, как рекурсия работает в памяти. Каждый вызов функции добавляется в стек вызовов (call stack):

function printNumbers(n) {
  if (n === 0) return; // базовый случай
  console.log(n);
  printNumbers(n - 1);
}

printNumbers(3);
// Вывод:
// 3
// 2
// 1

// Стек вызовов:
// printNumbers(3) {
//   printNumbers(2) {
//     printNumbers(1) {
//       printNumbers(0) -> return
//     }
//   }
// }

Классические примеры

1. Поиск в дереве

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

function searchInTree(node, target) {
  // Базовый случай
  if (node === null) return false;
  
  if (node.value === target) return true;
  
  // Рекурсивный случай
  return searchInTree(node.left, target) || searchInTree(node.right, target);
}

2. Разбор вложенных структур

function sumAllNumbers(arr) {
  let sum = 0;
  
  for (let item of arr) {
    if (typeof item === 'number') {
      sum += item;
    } else if (Array.isArray(item)) {
      sum += sumAllNumbers(item); // рекурсия
    }
  }
  
  return sum;
}

console.log(sumAllNumbers([1, [2, [3, 4]], 5])); // 15

3. Обход директорий

const fs = require('fs');
const path = require('path');

function listFilesRecursive(dir) {
  const files = fs.readdirSync(dir);
  
  for (let file of files) {
    const fullPath = path.join(dir, file);
    const stat = fs.statSync(fullPath);
    
    if (stat.isDirectory()) {
      listFilesRecursive(fullPath); // рекурсия
    } else {
      console.log(fullPath);
    }
  }
}

Проблема: переполнение стека (Stack Overflow)

Слишком глубокая рекурсия может вызвать ошибку:

function infiniteRecursion() {
  infiniteRecursion(); // Нет базового случая!
}

infiniteRecursion();
// RangeError: Maximum call stack size exceeded

Решение — хвостовая рекурсия (tail recursion):

// Неоптимизированная рекурсия
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1); // умножение ПОСЛЕ рекурсии
}

// Хвостовая рекурсия (аккумулятор)
function factorialTail(n, acc = 1) {
  if (n === 1) return acc;
  return factorialTail(n - 1, n * acc); // ТОЛЬКО рекурсия, нет операций после
}

Рекурсия vs Итерация

Рекурсия:

• ✅ Естественна для деревьев, графов, разделяй-и-властвуй
• ✅ Более читаемый код для некоторых задач
• ❌ Медленнее из-за вызовов функций
• ❌ Может переполнить стек

Итерация:

• ✅ Быстрее
• ✅ Не требует много памяти
• ❌ Может быть менее понятной для сложных структур

// Рекурсия
function sumRecursive(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sumRecursive(arr.slice(1));
}

// Итерация (более эффективна)
function sumIterative(arr) {
  let sum = 0;
  for (let num of arr) {
    sum += num;
  }
  return sum;
}

Мемоизация для оптимизации

Рекурсивные функции часто переделывают одно и то же. Мемоизация кэширует результаты:

function fibonacci(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

console.log(fibonacci(50)); // Быстро благодаря кэшу

Практические рекомендации

1. Всегда определите базовый случай перед написанием рекурсивного кода
2. Убедитесь в прогрессе к базовому случаю в каждом рекурсивном вызове
3. Предпочитайте итерацию для простых циклов по массивам
4. Используйте рекурсию для деревьев, графов и задач "разделяй-и-властвуй"
5. Контролируйте глубину рекурсии и используйте мемоизацию при необходимости

Заключение

Рекурсия — мощный и элегантный инструмент программирования. Она незаменима при работе со сложными структурами данных и алгоритмами поиска. Однако требует дисциплины в определении базового случая и осознания стоимости в терминах производительности и использования памяти.