Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке рекурсивний випадок?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Рекурсивний випадок** - це частина рекурсивної функції, де вона викликає сама себе зі зменшеною або спрощеною версією вихідної задачі. Цей виклик обов'язково робить прогрес до базового випадку і зазвичай комбінує частковий результат із поточним станом. **Ключове:** рекурсивний випадок повинен робити перевірюваний прогрес до базового випадку - інакше виникає нескінченна рекурсія і переповнення стека.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь Рекурсивний випадок - це частина рекурсивної функції, де вона викликає сама себе зі зменшеною або спрощеною версією вихідної задачі. Цей виклик обов'язково робить прогрес до базового випадку і зазвичай комбінує частковий результат із поточним станом. ## Докладно У будь-якій коректній рекурсивній функції є два ключові компоненти: базовий випадок (умова зупинки) і рекурсивний випадок (крок, який розбиває задачу і викликає функцію знову). Рекурсивний випадок повинен зменшувати складність задачі і приводити до одного або кількох подальших викликів, після чого результати цих викликів об'єднуються. ### Структура рекурсивної функції - Базовий випадок: умова, за якої функція більше не викликає себе і одразу повертає відповідь (наприклад, порожня колекція, n = 0/1, вихід за межі). - Рекурсивний випадок: гілка, де функція викликає сама себе зі спрощеною підзадачею. Важливо: вона робить перевірюваний прогрес до базового випадку і, як правило, об'єднує отриманий підрезультат із поточним контекстом. - Крок прогресу: чітке зменшення задачі - n → n - 1, діапазон [l, r] → одна половина, вузол дерева → його діти, список → «голова» + «хвіст». - Комбінація результатів: як із часткових відповідей отримати підсумок (наприклад, n * factorial(n - 1), sum(left) + sum(right), concat(flatten(child))). - Практичний момент (JS): оптимізація хвостової рекурсії в більшості середовищ не гарантована, тому глибоко рекурсивні задачі краще переписувати ітеративно або обмежувати глибину. ### Приклади реалізації #### Факторіал (JavaScript) ``` function factorial(n) { if (n < 0) throw new Error('n must be non-negative'); // Базовий випадок: 0! = 1, 1! = 1 if (n === 0 || n === 1) return 1; // Рекурсивний випадок: n! = n * (n - 1)! return n * factorial(n - 1); } console.log(factorial(5)); // 120 ``` Тут рекурсивний випадок зменшує n на 1 і просувається до базового випадку n = 1 або 0, після чого результати перемножуються. #### Обхід дерева (DFS) ``` const tree = { value: 1, children: [ { value: 2, children: [] }, { value: 3, children: [{ value: 4, children: [] }] } ] }; function dfs(node, visit) { // Базовий випадок: порожній вузол if (!node) return; visit(node); // Рекурсивний випадок: обійти кожну дитину for (const child of node.children || []) { dfs(child, visit); } } dfs(tree, n => console.log(n.value)); // 1 2 3 4 ``` Рекурсивний випадок - для кожного дочірнього вузла викликаємо dfs, тим самим розбиваючи дерево на піддерева. #### Сума вкладеного масиву ``` function sumNested(arr) { let sum = 0; for (const item of arr) { if (Array.isArray(item)) { // Рекурсивний випадок: підсумувати підмасив sum += sumNested(item); } else { // Базовий випадок: примітивне число sum += item; } } return sum; } console.log(sumNested([1, [2, [3, 4]], 5])); // 15 ``` Рекурсивний випадок обробляє вкладений масив, поки не дійде до чисел (базовий випадок). #### Бінарний пошук (розділяй і володарюй) ``` function binarySearch(arr, target, left = 0, right = arr.length - 1) { // Базовий випадок: діапазон порожній if (left > right) return -1; const mid = Math.floor((left + right) / 2); if (arr[mid] === target) return mid; // Базовий випадок: знайдено // Рекурсивний випадок: звузити пошук в одну з половин if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1); return binarySearch(arr, target, mid + 1, right); } console.log(binarySearch([1, 2, 3, 4, 5], 4)); // 3 ``` Рекурсивний випадок зменшує розмір діапазону вдвічі на кожному кроці, гарантуючи прогрес до базового випадку. ### Часті помилки в рекурсивному випадку - Немає базового випадку, або він недосяжний - нескінченна рекурсія і переповнення стека. - Немає прогресу - аргументи рекурсивного виклику не наближають до зупинки (наприклад, ви передаєте ті самі значення). - Експоненційне дублювання підзадач - класичний fib(n) без мемоізації (два рекурсивних виклики, великі перекриття). Рішення: мемоізація/динамічне програмування або ітерація. - Забули повернути результат рекурсивного виклику - функція завжди повертає undefined/невірний результат. - Мутація спільної структури між гілками - важко відстежувані баги. Краще робити чисті функції або копії, якщо потрібно. ### Як перевірити коректність рекурсивного випадку 1. Ясно сформулюйте базовий випадок і покажіть, що він досяжний. 2. Доведіть прогрес: на кожному кроці вхід стає "меншим" (розмір, глибина, відстань, діапазон). 3. Визначте інваріант - що залишається істинним до і після рекурсивного кроку. 4. Перевірте комбінування результатів: чи коректно ви збираєте підсумок із підрезультатів. 5. Оцініть складність (часову і просторову) і уникайте надлишкових викликів (використовуйте мемоізацію, якщо потрібно). 6. Покрийте граничні випадки тестами: порожні входи, мінімальні/максимальні значення, глибока вкладеність. ### Шаблон для співбесіди ``` function solve(problem) { // 1) Базовий випадок(и) if (isBase(problem)) return baseAnswer(problem); // 2) Прогрес: спростити задачу const smaller = reduce(problem); // 3) Рекурсивний випадок: розв'язати підзадачу const partial = solve(smaller); // 4) Комбінація результатів return combine(problem, partial); } ``` ### Коли використовувати рекурсію - Дерева і графи: обходи (DFS), обчислення на піддеревах, пошук шляхів (з урахуванням множини відвіданих). - Розділяй і володарюй: бінарний пошук, швидке сортування, злиття, побудова сегментних дерев. - Бектрекінг: перебір з відкатами (генерація перестановок, N-ферзів, парсинг). - Задачі з природною рекурсивною структурою даних або формулою (наприклад, рекурсивні визначення). ### Хвостова рекурсія та ітерація Хвостова рекурсія - коли рекурсивний виклик є останньою операцією функції і результат повертається напряму. Це дозволяє потенційно оптимізувати стек, але в JavaScript така оптимізація не гарантована. Для великих глибин переважна ітерація або явний стек.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.