Заміна рекурсії на цикл

JavaScriptJunior~3 хв читання

Майже будь-яку рекурсію можна переписати в цикл, якщо акуратно замінити самовиклик на повторення дій зі зміною стану. Рекурсивний виклик несе стан у аргументах функції, а цикл несе той самий стан у звичайних змінних, тож переклад між ними механічний.

Теорія

TL;DR

Рекурсія завжди складається з двох частин: базовий випадок і рекурсивний крок.
Щоб отримати цикл, створюємо змінні для стану (колишніх аргументів).
Повторюємо кроки через while або for.
Виходимо з циклу тоді, коли рекурсія досягла б базового випадку.
Цикли зазвичай ефективніші: менше пам'яті, швидше, немає ризику переповнення стека.
Рекурсія буває логічно зрозуміліша, особливо для вкладених структур (наприклад, дерев).

Швидкий приклад

javascript

// Рекурсивна версія
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

// Циклічна версія
function factorialIterative(n) {
  let result = 1;
  while (n > 1) {
    result *= n;
    n--;
  }
  return result;
}

console.log(factorial(5));          // 120
console.log(factorialIterative(5)); // 120

Ми просто «розгорнули» рекурсію: замість багатьох викликів функції змінюємо n усередині циклу.

Загальний принцип

Рекурсія зазвичай складається з:

базового випадку, коли повертаємо результат без нового виклику;
рекурсивного кроку, коли функція викликає себе з новими аргументами.

Щоб перетворити це на цикл:

створюємо змінні для стану (тобто для аргументів);
повторюємо кроки через while або for;
перериваємося, коли досягнуто базового випадку.

Іншими словами, рекурсія зберігає стан у стеку викликів, а цикл зберігає той самий стан у локальних змінних. Уся робота при переписуванні зводиться до того, щоб знайти цей стан і зробити його явним.

Приклад: сума масиву

Рекурсія:

javascript

function sum(arr, i = 0) {
  if (i === arr.length) return 0;
  return arr[i] + sum(arr, i + 1);
}

Цикл:

javascript

function sumIterative(arr) {
  let result = 0;
  for (let i = 0; i < arr.length; i++) {
    result += arr[i];
  }
  return result;
}

Тут добре видно шаблон: індекс i був аргументом рекурсії, а став лічильником циклу. Накопичувач result замінив ланцюжок додавань, які раніше «чекали» у стеку, доки не повернеться найглибший виклик.

Приклад: числа Фібоначчі

Рекурсивно:

javascript

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Циклічно:

javascript

function fibIterative(n) {
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

Тут цикл працює значно ефективніше: наївна рекурсія виконує експоненційно багато викликів, бо перераховує ті самі значення знову і знову, а цикл робить лише n ітерацій і тримає в пам'яті два числа.

Загальний шаблон переходу

Елемент рекурсії	У циклі
Аргументи функції	Локальні змінні
Рекурсивний виклик	Ітерація циклу
Базовий випадок	Умова виходу (`if`, `while`)
Повернення значення	Повернення після циклу

Порядок дій завжди той самий: визначити базовий випадок і перетворити його на умову виходу, перенести стан у змінні, змінювати їх на кожній ітерації.

Коли цикл, а коли рекурсія

Будь-яку рекурсію можна записати циклом, якщо визначити базовий випадок, перенести стан у змінні та змінювати їх на кожній ітерації.
Цикли зазвичай ефективніші: менше пам'яті, швидше, немає RangeError: Maximum call stack size exceeded.
Рекурсія буває зрозумілішою логічно, особливо для вкладених структур (наприклад, дерев або DOM).
Коли рекурсія має кілька гілок (як обхід дерева), простий лічильник уже не рятує: стан переносять у явний стек-масив.

javascript

// Обхід дерева без рекурсії: власний стек замість стека викликів
function collectValues(root) {
  const out = [];
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    if (!node) continue;
    out.push(node.value);
    for (const child of node.children ?? []) stack.push(child);
  }
  return out;
}

Типові помилки

Забути умову виходу. Рекурсія без базового випадку падає з RangeError, а цикл без умови виходу просто вішає вкладку назавжди, і це помітити важче.
Не змінювати стан в тілі циклу. Якщо забути n-- або i++, умова ніколи не стане хибною.
Плутати порядок обчислень. Рекурсія n * factorial(n - 1) множить, повертаючись угору по стеку, тому при переписуванні на цикл треба стежити, з якого боку накопичується результат.
Вважати, що рекурсія завжди повільніша. Сама по собі вона не «повільна»: повільною наївний fib робить не рекурсія, а повторний перерахунок тих самих значень. З мемоізацією рекурсивний варіант теж лінійний.
Переписувати на цикл те, що читається краще рекурсивно. Для дерев і графів цикл із власним стеком часто довший і заплутаніший за три рядки рекурсії.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.