Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке базовий випадок рекурсії?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Базовий випадок рекурсії** - це умова, за якої рекурсивна функція припиняє подальші виклики і повертає безпосередній результат. Він гарантує завершення алгоритму і коректність на мінімально простих входах. **Ключове:** без базового випадку рекурсія може стати нескінченною і переповнити стек.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь Базовий випадок рекурсії - це умова, за якої рекурсивна функція припиняє подальші виклики і повертає безпосередній результат. Він гарантує завершення алгоритму і коректність на мінімально простих входах. ## Докладне пояснення У рекурсивних алгоритмах розв'язання задачі зводиться до розв'язання її ж, але для меншого або простішого входу. Базовий випадок визначає, на якому мінімальному вході рекурсія повинна зупинитися і яку відповідь потрібно повернути без подальшої декомпозиції. - Умова зупинки: логічна перевірка, за якої функція не робить рекурсивний виклик. - Повернення простого результату: відповідь відома напряму (наприклад, порожня колекція, нуль, одиниця, null-вузол). - Досяжність: кожен рекурсивний крок повинен наближати вхід до базового випадку. - Покриття граничних значень: базовий випадок коректно обробляє мінімальні/порожні входи. - Можливі кілька базових випадків: наприклад, для чисел Фібоначчі n = 0 і n = 1. ## Чому базовий випадок важливий - Гарантія завершення: без нього рекурсія може стати нескінченною і переповнити стек. - Коректність: забезпечує правильну відповідь на мінімальних підзадачах, на якій будується індуктивний доказ. - Продуктивність: занадто вузький або недосяжний базовий випадок веде до зайвої роботи. - Безпека: запобігає переповненню стека та помилкам часу виконання. ## Приклади реалізації ### Факторіал (JS) ```javascript function factorial(n) { if (n < 0) throw new Error('n must be >= 0'); if (n === 0 || n === 1) return 1; // базовий випадок return n * factorial(n - 1); // рекурсивний крок } console.log(factorial(5)); // 120 ``` Базовий випадок: n === 0 або n === 1. Рекурсивний крок зменшує n і робить базу досяжною. ### Сума елементів масиву (JS) ```javascript function sum(arr) { if (arr.length === 0) return 0; // базовий випадок const [head, ...tail] = arr; return head + sum(tail); // рекурсивний крок } console.log(sum([1,2,3,4])); // 10 ``` Базовий випадок: порожній масив дає 0. Кожен крок зменшує масив, наближаючи його до порожнього. ### НСД (алгоритм Евкліда) ```javascript function gcd(a, b) { if (b === 0) return Math.abs(a); // базовий випадок return gcd(b, a % b); // рекурсивний крок } console.log(gcd(48, 18)); // 6 ``` Базовий випадок: коли другий аргумент 0, відповідь відома напряму. ### Кілька базових випадків: числа Фібоначчі ```javascript function fib(n) { if (n < 0) throw new Error('n must be >= 0'); if (n === 0) return 0; // базовий випадок 1 if (n === 1) return 1; // базовий випадок 2 return fib(n - 1) + fib(n - 2); } console.log(fib(6)); // 8 ``` Тут два базових випадки: для n = 0 і n = 1. Без них рекурсія не завершиться. На практиці для ефективності використовують мемоізацію або ітерацію. ## Поширені помилки - Відсутній базовий випадок, або він не перевіряється першим. - Недосяжний базовий випадок: параметр не змінюється в бік бази (наприклад, n збільшується). - Занадто вузький базовий випадок: обробляє не всі граничні значення (наприклад, тільки n === 0, але не n === 1). - Побічні ефекти до перевірки бази: логувати/змінювати стан до того, як переконалися, що рекурсія не потрібна. ## Як спроектувати базовий випадок 1. Визначте мінімальний вхід задачі: порожня структура, нульовий розмір, нульова глибина. 2. Сформулюйте відповідь на цьому мінімальному вході без рекурсії. 3. Переконайтеся, що кожен рекурсивний крок зменшує «розмір» задачі і досягає бази. 4. Перевірте граничні випадки: порожні, нульові, одиничні елементи. 5. Протестуйте на малих даних, де легко простежити хід виконання. ## Базовий випадок у структурах даних У рекурсивних обходах структур базою зазвичай є «порожня» форма структури: - Списки/масиви: порожній список/масив, індекс вийшов за межі. - Дерева: null-вузол (відсутність дочірнього елемента). - Графи: вершина вже відвідана (щоб зупинити повторні обходи). - Діапазони (divide-and-conquer): діапазон порожній або одиничної довжини (наприклад, length < 2). ### Обхід бінарного дерева (JS) ```javascript function inorder(node) { if (node == null) return; // базовий випадок: порожній вузол inorder(node.left); console.log(node.value); inorder(node.right); } ``` Базовий випадок зупиняє заглиблення, коли досягнуто відсутній дочірній вузол. ## Підсумки Базовий випадок - це чітка і досяжна умова зупинки рекурсії з безпосередньою відповіддю. Проектуйте його виходячи з мінімального входу, перевіряйте першим і переконайтеся, що кожен рекурсивний крок робить його досяжним. За потреби використовуйте кілька базових випадків.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.