Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Які задачі розв'язує рекурсія». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Рекурсію застосовують там, де велику задачу можна природно розділити на підзадачі того самого типу: математичні обчислення (факторіал, числа Фібоначчі, піднесення до степеня), обхід дерев і графів (DOM, файлова система, DFS), робота з масивами та вкладеними структурами (сума елементів, flatten), алгоритми «розділяй і володарюй» (QuickSort, MergeSort, бінарний пошук, Ханойська вежа) і комбінаторні задачі (перестановки, пошук шляху в лабіринті, задача про рюкзак).** ```javascript function pow(x, n) { if (n === 0) return 1; return x * pow(x, n - 1); } ``` **Ключове:** рекурсія пасує, коли задачу можна виразити через простішу версію самої себе.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення**Рекурсію часто застосовують для задач, де велику задачу можна природно розділити на підзадачі того самого типу.** Нижче найтиповіші класи таких задач із прикладами на JavaScript. ## Теорія ### TL;DR - Математичні обчислення: факторіал, числа Фібоначчі, піднесення до степеня. - Обхід структур даних: дерева (DOM, файлова система), графи, DFS. - Робота з масивами: сума, пошук, фільтрація через «голова плюс хвіст». - Алгоритми «розділяй і володарюй»: QuickSort, MergeSort, бінарний пошук, Ханойська вежа. - Обробка вкладених структур: flatten масиву, обхід довільно вкладених об'єктів. - Логічні та комбінаторні задачі: перестановки, шлях у лабіринті, рюкзак. ### Швидкий приклад ```javascript // Піднесення до степеня через поділ задачі function pow(x, n) { if (n === 0) return 1; // базовий випадок return x * pow(x, n - 1); // рекурсивний крок } console.log(pow(2, 10)); // 1024 ``` ### Математичні обчислення Класика, бо формула вже задана рекурентно. - **Факторіал числа**: `n! = n * (n-1)!` - **Числа Фібоначчі**: `F(n) = F(n-1) + F(n-2)` - **Піднесення до степеня** через поділ задачі: ```javascript function pow(x, n) { if (n === 0) return 1; return x * pow(x, n - 1); } ``` Рекурсивний код тут майже дослівно повторює математичний запис, тому його легко перевірити очима. ### Обхід структур даних Дерево складається з піддерев, тому обхід дерева це обхід кожного піддерева. - **Дерева (наприклад, DOM, файлова система):** ```javascript function traverse(node) { console.log(node.value); node.children.forEach(traverse); } ``` - **Графи**: пошук у глибину (DFS) записується рекурсивно майже без зусиль; пошук у ширину (BFS) зазвичай реалізують через чергу, бо він іде рівнями, а не вглиб. Для графів обов'язково запам'ятовуйте відвідані вузли у `Set`, інакше цикл у даних зациклить обхід. ### Масиви та вкладені структури Масив зручно розглядати як «перший елемент плюс решта масиву». - Сума елементів, пошук, фільтрація: ```javascript function sum(arr) { if (arr.length === 0) return 0; return arr[0] + sum(arr.slice(1)); } ``` - Розгортання (flatten) масиву: ```javascript function flatten(arr) { return arr.reduce((acc, val) => acc.concat(Array.isArray(val) ? flatten(val) : val), []); } ``` Саме вкладені структури, де глибина наперед невідома, є найсильнішим аргументом на користь рекурсії: циклом довелося б вести власний стек. ### Алгоритми «розділяй і володарюй» Задача ділиться на кілька менших, кожна розв'язується тим самим алгоритмом, потім результати збираються докупи. - **Швидке сортування (QuickSort)** - **Сортування злиттям (MergeSort)** - **Бінарний пошук** - **Алгоритм Ханойської вежі** ```javascript function binarySearch(arr, target, lo = 0, hi = arr.length - 1) { if (lo > hi) return -1; // базовий випадок: нічого не лишилося const mid = (lo + hi) >> 1; if (arr[mid] === target) return mid; return arr[mid] < target ? binarySearch(arr, target, mid + 1, hi) : binarySearch(arr, target, lo, mid - 1); } ``` ### Логічні та комбінаторні задачі - Перебір усіх комбінацій і перестановок; - пошук шляху в лабіринті; - розв'язання «зважених» задач типу рюкзака (knapsack). ```javascript function permutations(items) { if (items.length <= 1) return [items]; // базовий випадок return items.flatMap((item, i) => { const rest = [...items.slice(0, i), ...items.slice(i + 1)]; return permutations(rest).map((p) => [item, ...p]); }); } console.log(permutations(['a', 'b', 'c']).length); // 6 ``` Тут рекурсія природно описує перебір з поверненням (backtracking): зробили вибір, пішли глибше, повернулися і спробували наступний. ### Типові помилки - **Рекурсія там, де достатньо циклу.** Лінійний прохід масивом циклом простіший і не має обмеження глибини стека. - **`arr.slice(1)` на великому масиві.** Кожен виклик копіює хвіст, тож замість `O(n)` виходить `O(n^2)` за часом і пам'яттю; краще передавати індекс. - **Наївний `fib` без мемоізації.** `fib(n - 1) + fib(n - 2)` дає експоненційну кількість викликів; кеш або цикл роблять його лінійним. - **Обхід графа без множини відвіданих вузлів.** Цикл у даних перетворює обхід на нескінченний. - **Глибока рекурсія по великих даних.** Обхід мільйона елементів впаде з `RangeError: Maximum call stack size exceeded`, навіть коли логіка правильна. - **Забутий базовий випадок у комбінаторних задачах.** Найчастіше це `items.length <= 1` або порожня гілка дерева.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.