Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Заміна рекурсії на цикл». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Майже будь-яку рекурсію можна переписати в цикл: досить замінити самовиклик на повторення тих самих дій зі зміною стану.** Рекурсія складається з базового випадку (повертаємо результат без нового виклику) і рекурсивного кроку (функція викликає себе з новими аргументами). Щоб перетворити її на цикл, аргументи рекурсивної функції стають локальними змінними, рекурсивний виклик стає ітерацією `while` або `for`, а базовий випадок стає умовою виходу. Цикл зазвичай ефективніший, бо не витрачає стек викликів на кожен рівень, але рекурсія часто логічно зрозуміліша для вкладених структур на кшталт дерев. ```javascript // recursive function factorial(n) { if (n === 1) return 1; return n * factorial(n - 1); } // iterative function factorialIterative(n) { let result = 1; while (n > 1) { result *= n; n--; } return result; } ``` **Ключове:** стан переносимо у змінні, базовий випадок стає умовою виходу, самовиклик стає ітерацією.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення**Майже будь-яку рекурсію можна переписати в цикл, якщо акуратно замінити самовиклик на повторення дій зі зміною стану.** Рекурсивний виклик несе стан у аргументах функції, а цикл несе той самий стан у звичайних змінних, тож переклад між ними механічний. ## Теорія ### 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` усередині циклу. ### Загальний принцип Рекурсія зазвичай складається з: 1. **базового випадку**, коли повертаємо результат без нового виклику; 2. **рекурсивного кроку**, коли функція викликає себе з новими аргументами. Щоб перетворити це на цикл: - створюємо змінні для стану (тобто для аргументів); - повторюємо кроки через `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` робить не рекурсія, а повторний перерахунок тих самих значень. З мемоізацією рекурсивний варіант теж лінійний. - **Переписувати на цикл те, що читається краще рекурсивно.** Для дерев і графів цикл із власним стеком часто довший і заплутаніший за три рядки рекурсії.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.