Просмотр исходного текста страницы Базовый случай и рекурсивный вызов

Рекурсия — это метод решения задачи, при котором функция вызывает саму себя. Рекурсивные функции состоят из двух основных частей: '''базового случая''' и '''рекурсивного вызова'''.

== Базовый случай (Base Case) ==

Базовый случай — это условие, при котором рекурсивная функция прекращает вызывать саму себя и возвращает значение напрямую. Это условие является критически важным для предотвращения бесконечной рекурсии. Без базового случая рекурсивная функция будет продолжать вызывать себя, пока не произойдет переполнение стека (stack overflow).

=== Характеристики базового случая: ===

*   '''Условие остановки''': Определяет, когда рекурсия должна прекратиться.
*   '''Прямой возврат''': Возвращает значение без дальнейших рекурсивных вызовов.
*   '''Простое решение''': Представляет собой наиболее простой случай задачи, который можно решить напрямую.

=== Пример базового случая (факториал): ===

В рекурсивной функции для вычисления факториала числа `n`, базовым случаем является `n = 0` или `n = 1`, когда функция возвращает `1`.

```
function factorial(n) {
    if (n === 0 || n === 1) {
        return 1; // Базовый случай: факториал 0 и 1 равен 1
    } else {
        // Рекурсивный вызов
        return n * factorial(n - 1);
    }
}
```

== Рекурсивный вызов (Recursive Call) ==

Рекурсивный вызов — это вызов функцией самой себя с другим набором аргументов. Важно, чтобы аргументы рекурсивного вызова приближали к базовому случаю, иначе рекурсия может никогда не завершиться.

=== Характеристики рекурсивного вызова: ===

*   '''Вызов функции внутри себя''': Функция вызывает себя с измененными аргументами.
*   '''Приближение к базовому случаю''': Каждый рекурсивный вызов должен упрощать задачу, приближая к базовому случаю.
*   '''Разбиение задачи''': Задача разбивается на более мелкие подзадачи, которые решаются рекурсивно.

=== Пример рекурсивного вызова (факториал): ===

В функции факториала, рекурсивный вызов выполняется с аргументом `n - 1`. Это приближает к базовому случаю `n = 0` или `n = 1`.

```
function factorial(n) {
    if (n === 0 || n === 1) {
        return 1; // Базовый случай
    } else {
        return n * factorial(n - 1); // Рекурсивный вызов
    }
}
```

== Пример (вычисление суммы элементов массива) ==

```
function sumArray(arr) {
    if (arr.length === 0) {
        return 0; // Базовый случай: пустой массив, сумма равна 0
    } else {
        return arr[0] + sumArray(arr.slice(1)); // Рекурсивный вызов: сумма первого элемента и суммы остатка массива
    }
}
```

В этом примере:

*   Базовый случай: `arr.length === 0` (пустой массив).
*   Рекурсивный вызов: `sumArray(arr.slice(1))` (вызов функции с остатком массива).

== Важность правильной реализации ==

Правильная реализация базового случая и рекурсивного вызова критически важна для корректной работы рекурсивных функций. Неправильная реализация может привести к:

*   '''Бесконечной рекурсии''': Функция никогда не завершается, что приводит к переполнению стека.
*   '''Некорректным результатам''': Функция возвращает неправильное значение из-за ошибок в логике рекурсии.

Рекурсия — мощный инструмент для решения задач, но требует тщательного проектирования и понимания принципов работы.