Рекурсия

Базовый случай и рекурсивный шаг, факториал, Фибоначчи, стек вызовов и рекурсия vs цикл

Что такое рекурсия?

Представьте, что вы стоите между двумя зеркалами. Вы смотрите в одно зеркало и видите своё отражение, а в этом отражении — ещё одно отражение, и так далее, бесконечно вглубь. Это и есть рекурсия — процесс, при котором метод вызывает сам себя.

Другая аналогия — матрёшка. Вы открываете одну куколку, а внутри ещё одна, которая похожа на предыдущую, только меньше. Вы открываете следующую — опять такая же, но ещё меньше. И так до тех пор, пока не дойдёте до самой маленькой куколки, которую уже нельзя открыть. Вот эта самая маленькая куколка — это и есть базовый случай, о котором мы поговорим чуть позже.

В программировании рекурсия — это техника, при которой метод решает задачу, вызывая себя же, но с изменёнными параметрами. Каждый следующий вызов работает с чуть более простой версией задачи. И так — до тех пор, пока задача не станет настолько простой, что её можно решить напрямую, без дополнительных вызовов.

Давайте разберём это на простом примере. Представьте, что вас попросили посчитать, сколько человек стоит в очереди за вами. Вы можете:

• Спросить у человека, стоящего за вами: «Сколько людей за тобой?»
• Этот человек задаёт тот же вопрос следующему за ним
• Так продолжается до последнего человека в очереди
• Последний человек говорит: «Позади меня никого нет» — это и есть базовый случай
• Ответ передаётся в обратном направлении, пока не вернётся к вам

Вы не знаете общее количество людей, но каждый человек в очереди задаёт тот же вопрос следующему, пока кто-то не скажет «ноль». Затем ответы складываются по цепочке. Это классический пример рекурсивного подхода к решению задачи.

Два обязательных компонента рекурсии

Каждая рекурсивная функция обязана иметь два компонента, без которых она просто не будет работать корректно. Если вы забудете хотя бы один из них, ваша программа либо зациклится и упадёт с ошибкой, либо не будет работать как надо. Давайте разберём каждый из них подробно.

Вот формула хорошей рекурсивной функции:

Если задача — самая простая (базовый случай):
    Вернуть известный ответ
Иначе (рекурсивный шаг):
    Вызвать функцию с более простой версией задачи
    Использовать результат для построения ответа

Давайте рассмотрим конкретный пример. Допустим, у нас есть функция, которая считает сумму чисел от 1 до n:

public static int sumUpTo(int n) {
    if (n == 1) {
        return 1;
    }
    return n + sumUpTo(n - 1);
}

Здесь базовый случай — n == 1: если n равно 1, просто возвращаем 1. Рекурсивный шаг — n + sumUpTo(n - 1): складываем n с суммой всех чисел от 1 до n-1. Каждый вызов уменьшает n на 1, приближаясь к базовому случаю.

Факториал: подробный разбор

Факториал числа — это одна из самых классических задач для изучения рекурсии. Факториал числа n (обозначается как n!) — это произведение всех натуральных чисел от 1 до n. Например:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 4! = 4 × 3 × 2 × 1 = 24
• 3! = 3 × 2 × 1 = 6
• 1! = 1
• 0! = 1 (по определению)

Заметили закономерность? 5! = 5 × 4!, 4! = 4 × 3!, и так далее. Это и есть рекурсивная формула: n! = n × (n-1)!. Каждое число можно выразить через.factoriал предыдущего числа. Это делает факториал идеальной задачей для рекурсии.

public class Factorial {
    public static long factorial(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println("0! = " + factorial(0));
        System.out.println("1! = " + factorial(1));
        System.out.println("5! = " + factorial(5));
        System.out.println("10! = " + factorial(10));
        System.out.println("20! = " + factorial(20));
    }
}

Вывод программы:

0! = 1
1! = 1
5! = 120
10! = 3628800
20! = 2432902008176640000

Давайте пошагово разберём, как выполняется factorial(5):

1. factorial(5): n = 5, это не 0 и не 1, поэтому вызываем 5 * factorial(4)
2. factorial(4): n = 4, это не 0 и не 1, поэтому вызываем 4 * factorial(3)
3. factorial(3): n = 3, это не 0 и не 1, поэтому вызываем 3 * factorial(2)
4. factorial(2): n = 2, это не 0 и не 1, поэтому вызываем 2 * factorial(1)
5. factorial(1): n = 1, это базовый случай! Возвращаем 1

Теперь результаты «всплывают» обратно:

1. factorial(2) получает 1, возвращает 2 * 1 = 2
2. factorial(3) получает 2, возвращает 3 * 2 = 6
3. factorial(4) получает 6, возвращает 4 * 6 = 24
4. factorial(5) получает 24, возвращает 5 * 24 = 120

Как видите, задача разбивается на простейшую часть (factorial(1) = 1) и затем результаты собираются обратно. Это и есть суть рекурсии — разделяй и властвуй. Сначала вы спускаетесь вглубь, пока не дойдёте до базового случая, а затем поднимаетесь обратно, собирая ответ.

Фибоначчи: рекурсивная версия и её проблемы

Последовательность Фибоначчи — ещё один классический пример рекурсии. Каждое число в этой последовательности — это сумма двух предыдущих:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Формула: fib(n) = fib(n-1) + fib(n-2), при этом fib(0) = 0 и fib(1) = 1.

Рекурсивная реализация:

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.println("fib(" + i + ") = " + fibonacci(i));
        }
    }
}

Вывод:

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55

Эlegantная и простая реализация. Но вот проблема — эта рекурсия крайне неэффективна. Почему?

Посмотрите, как вычисляется fib(5):

                        fib(5)
                       /      \
                  fib(4)        fib(3)
                 /      \       /     \
            fib(3)    fib(2)  fib(2)  fib(1)
           /     \    /    \   /    \
        fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
        /    \
    fib(1) fib(0)

Обратите внимание: fib(3) вычисляется дважды, fib(2) — трижды. Чем больше n, тем больше дублирования. Для fib(40) программа будет работать несколько секунд, а для fib(50) — несколько минут!

Это называется проблемой повторных вычислений. Рекурсивная версия Фибоначчи имеет экспоненциальную сложность — O(2^n). Каждое увеличение n примерно удваивает время работы.

Давайте измерим, сколько времени занимает вычисление разных чисел Фибоначчи:

public class FibonacciBenchmark {
    public static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        int[] testValues = {10, 20, 30, 35, 40};
        for (int n : testValues) {
            long start = System.currentTimeMillis();
            int result = fibonacci(n);
            long end = System.currentTimeMillis();
            System.out.println("fib(" + n + ") = " + result
                + " | время: " + (end - start) + " мс");
        }
    }
}

Примерный вывод:

fib(10) = 55   | время: 0 мс
fib(20) = 6765 | время: 1 мс
fib(30) = 832040 | время: 108 мс
fib(35) = 9227465 | время: 1189 мс
fib(40) = 102334155 | время: 14213 мс

Видите, как время растёт? С увеличением n на 5, время увеличивается примерно в 10-15 раз. Это экспоненциальный рост.

public class FibonacciMemo {
    private static long[] memo = new long[100];

    public static long fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (memo[n] != 0) return memo[n];
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return memo[n];
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println("fib(40) = " + fibonacci(40));
        long end = System.currentTimeMillis();
        System.out.println("Время: " + (end - start) + " мс");
    }
}

Теперь fib(40) вычисляется практически мгновенно — менее 1 миллисекунды вместо 14 секунд! Мемоизация снижает сложность с O(2^n) до O(n).

public static long fibonacciIterative(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    long prev = 0;
    long curr = 1;
    for (int i = 2; i <= n; i++) {
        long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

Эта версия не использует рекурсию вообще — просто цикл, который идёт от 2 до n. Она работает за O(n) времени и O(1) памяти. Для Фибоначчи итеративный подход обычно предпочтительнее рекурсивного.

Стек вызовов (Call Stack)

Чтобы понять, как рекурсия работает «под капотом», нужно разобраться с понятием стека вызовов (call stack). Стек — это структура данных, работающая по принципу «последний пришёл — первый вышел» (LIFO). Представьте стопку тарелок — вы кладёте сверху новую и снимаете верхнюю. Стек вызовов работает точно так же.

Каждый раз, когда метод вызывается, Java создаёт новый стековый фрейм (stack frame) и помещает его на вершину стека. Фрейм содержит:

• Локальные переменные метода
• Параметры метода
• Адрес возврата (куда вернуться после завершения метода)
• Промежуточные значения выражений

Когда метод завершается, его фрейм убирается из стека, и управление возвращается к предыдущему методу.

Давайте проследим стек вызовов для factorial(3):

Шаг 1: Вызывается factorial(3). На стеке появляется фрейм:

┌─────────────────────┐
│  factorial(3)       │  ← вершина стека
│  n = 3              │
│  ожидает: 3 * ?     │
└─────────────────────┘

Шаг 2: factorial(3) вызывает factorial(2):

┌─────────────────────┐
│  factorial(2)       │  ← вершина стека
│  n = 2              │
│  ожидает: 2 * ?     │
├─────────────────────┤
│  factorial(3)       │
│  n = 3              │
│  ожидает: 3 * ?     │
└─────────────────────┘

Шаг 3: factorial(2) вызывает factorial(1):

┌─────────────────────┐
│  factorial(1)       │  ← вершина стека
│  n = 1              │
│  возвращает: 1      │
├─────────────────────┤
│  factorial(2)       │
│  n = 2              │
│  ожидает: 2 * ?     │
├─────────────────────┤
│  factorial(3)       │
│  n = 3              │
│  ожидает: 3 * ?     │
└─────────────────────┘

Шаг 4: factorial(1) достигает базового случая и возвращает 1. Его фрейм удаляется:

┌─────────────────────┐
│  factorial(2)       │  ← вершина стека
│  n = 2              │
│  получает: 1        │
│  вычисляет: 2 * 1 = 2│
├─────────────────────┤
│  factorial(3)       │
│  n = 3              │
│  ожидает: 3 * ?     │
└─────────────────────┘

Шаг 5: factorial(2) вычисляет 2 * 1 = 2 и возвращает результат:

┌─────────────────────┐
│  factorial(3)       │  ← вершина стека
│  n = 3              │
│  получает: 2        │
│  вычисляет: 3 * 2 = 6│
└─────────────────────┘

Шаг 6: factorial(3) вычисляет 3 * 2 = 6 и возвращает результат. Стек пуст:

┌─────────────────────┐
│                     │  ← стек пуст
└─────────────────────┘

Как видите, каждый рекурсивный вызов добавляет новый фрейм на стек. Когда вызовов много, стек растёт. И если он вырастет слишком сильно — произойдёт ошибка StackOverflowError.

StackOverflowError

StackOverflowError — это ошибка, которая возникает, когда стек вызовов заполняется полностью. Каждый поток в Java имеет свой стек, и у него есть ограниченный размер. По умолчанию это около 512 КБ — 1 МБ.

Когда рекурсия слишком глубокая (слишком много вложенных вызовов), стек переполняется и Java выбрасывает StackOverflowError.

Давайте посмотрим, как это происходит:

public class StackOverflowDemo {
    public static void infinite() {
        infinite();
    }

    public static void main(String[] args) {
        try {
            infinite();
        } catch (StackOverflowError e) {
            System.out.println("Произошла ошибка: стек переполнен!");
        }
    }
}

Программа выведет:

Произошла ошибка: стек переполнен!

Типичные причины StackOverflowError:

1. Отсутствует базовый случай: метод вызывает себя без условий, и рекурсия никогда не останавливается
2. Базовый случай недостижим: условие остановки написано неправильно, и рекурсия проходит мимо него
3. Рекурсивный шаг не приближает к базовому случаю: например, вместо n - 1 написано n + 1
4. Слишком большая глубина рекурсии: даже правильная рекурсия может переполнить стек, если n слишком велико

Давайте рассмотрим каждый случай подробнее:

Случай 1: Нет базового случая

public static void bad() {
    bad();
}

Случай 2: Базовый случай недостижим

public static int badFactorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * badFactorial(n + 1);
}

badFactorial(5);

Здесь n растёт (5, 6, 7, 8, ...) и никогда не достигнет 0. Программа упадёт с StackOverflowError.

Случай 3: Слишком большая глубина

public static long factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

factorial(100000);

Здесь рекурсия правильная, но 100 000 вложенных вызовов переполняют стек.

Как избежать StackOverflowError:

• Всегда проверяйте наличие базового случая
• Убедитесь, что рекурсивный шаг приближает к базовому случаю
• Для больших значений используйте итеративный подход
• Используйте мемоизацию для уменьшения глубины рекурсии
• Можно увеличить размер стека через параметр JVM: -Xss2m

Рекурсия vs цикл: когда что использовать

Многие задачи можно решить как рекурсивно, так и итеративно (с помощью циклов). Давайте сравним два подхода на примере факториала:

Рекурсивная версия:

public static long factorialRecursive(int n) {
    if (n == 0) return 1;
    return n * factorialRecursive(n - 1);
}

Итеративная версия:

public static long factorialIterative(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Обе версии выдают одинаковый результат. Но какой подход лучше?

Преимущества рекурсии:

• Код более элегантный и читаемый для задач, которые естественным образом рекурсивны (обход дерева, файловой системы)
• Решение задачи разбивается на подзадачи — принцип «разделяй и властвуй»
• Некоторые структуры данных (деревья, графы) проще обходить рекурсивно
• Рекурсия хорошо подходит для задач с вложенной структурой (например, файлы в папках)

Преимущества итеративного подхода:

• Не использует дополнительную память стека — работает за O(1) памяти
• Не может привести к StackOverflowError
• Обычно быстрее (нет накладных расходов на создание фреймов стека)
• Проще отлаживать — нет глубокой вложенности вызовов
• Понятнее для других программистов, которые могут не знать рекурсию

Когда использовать рекурсию:

• Задача естественным образом разбивается на подзадачи (фракталы, деревья, разделяй и властвуй)
• Обход связных структур данных (деревья, графы, связные списки)
• Алгоритмы сортировки (быстрая сортировка, сортировка слиянием)
• Поиск в глубину (DFS)
• Когда элегантность и ясность важнее производительности

Когда использовать итерацию:

• Простые линейные задачи (сумма,.factorial, поиск в массиве)
• Когда важна производительность и потребление памяти
• Когда рекурсия会导致 слишком глубокую вложенность
• Когда задача не имеет естественной рекурсивной структуры
• В продакшен-коде, где надёжность критична

Хвостовая рекурсия

Хвостовая рекурсия (tail recursion) — это особый вид рекурсии, при котором рекурсивный вызов является последней операцией метода. Никаких вычислений после вызова — только возврат результата.

Давайте сравним обычную и хвостовую рекурсию для факториала:

Обычная рекурсия (НЕ尾递归):

public static int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

Здесь после вызова factorial(n-1) происходит умножение на n. Значит, метод должен «помнить» значение n, пока ждёт результат рекурсивного вызова.

Хвостовая рекурсия (尾递归):

public static int factorialTail(int n, int accumulator) {
    if (n == 0) return accumulator;
    return factorialTail(n - 1, n * accumulator);
}

Здесь рекурсивный вызов — последняя операция. Результат накапливается в параметре accumulator. Вызов выглядит так: factorialTail(5, 1).

Почему хвостовая рекурсия важна? Потому что некоторые компиляторы (в том числе certains реализации Java) могут оптимизировать хвостовую рекурсию, превращая её в цикл. Это называется оптимизация хвостового вызова (tail call optimization, TCO). В результате рекурсивная функция работает так же эффективно, как цикл, не используя дополнительную память стека.

Практические примеры

Теперь давайте рассмотрим несколько практических примеров, где рекурсия применяется для решения реальных задач. Каждый пример покажет, как разбить задачу на подзадачи и найти базовый случай.

1. Степень числа

Возвести число a в степень n означает умножить a на себя n раз. Рекурсивная формула: power(a, n) = a * power(a, n-1). Базовый случай: power(a, 0) = 1.

public class Power {
    public static double power(double base, int exponent) {
        if (exponent == 0) {
            return 1.0;
        }
        if (exponent < 0) {
            return 1.0 / power(base, -exponent);
        }
        return base * power(base, exponent - 1);
    }

    public static void main(String[] args) {
        System.out.println("2^0 = " + power(2, 0));
        System.out.println("2^1 = " + power(2, 1));
        System.out.println("2^5 = " + power(2, 5));
        System.out.println("3^3 = " + power(3, 3));
        System.out.println("2^-3 = " + power(2, -3));
    }
}

Вывод:

2^0 = 1.0
2^1 = 2.0
2^5 = 32.0
3^3 = 27.0
2^-3 = 0.125

2. Сумма цифр числа

Сумма цифр числа — это последняя цифра плюс сумма цифр оставшихся. Например, для числа 1234: 4 + сумма цифр(123). Базовый случай: если число однозначное, возвращаем его.

public class DigitSum {
    public static int sumDigits(int number) {
        number = Math.abs(number);
        if (number < 10) {
            return number;
        }
        return number % 10 + sumDigits(number / 10);
    }

    public static void main(String[] args) {
        System.out.println("Цифры 1234: " + sumDigits(1234));
        System.out.println("Цифры 999: " + sumDigits(999));
        System.out.println("Цифры 7: " + sumDigits(7));
        System.out.println("Цифры 0: " + sumDigits(0));
        System.out.println("Цифры 1000: " + sumDigits(1000));
    }
}

Вывод:

Цифры 1234: 10
Цифры 999: 27
Цифры 7: 7
Цифры 0: 0
Цифры 1000: 1

Как это работает для sumDigits(1234):

• 1234 % 10 = 4, 1234 / 10 = 123
• 123 % 10 = 3, 123 / 10 = 12
• 12 % 10 = 2, 12 / 10 = 1
• 1 — базовый случай, возвращаем 1
• Складываем: 4 + 3 + 2 + 1 = 10

3. Реверс строки

Реверс строки — это классическая рекурсивная задача. Идея: взять последний символ и поставить его перед результатом реверса оставшейся строки. Базовый случай: пустая строка возвращается как есть.

public class ReverseString {
    public static String reverse(String str) {
        if (str.isEmpty()) {
            return str;
        }
        return reverse(str.substring(1)) + str.charAt(0);
    }

    public static void main(String[] args) {
        System.out.println(reverse("привет"));
        System.out.println(reverse("Java"));
        System.out.println(reverse("а"));
        System.out.println(reverse(""));
        System.out.println(reverse("мадам"));
    }
}

Вывод:

тевирп
avaJ
а

мадам

Обратите внимание: reverse("мадам") возвращает "мадам" — это палиндром! Мы это используем в следующем примере.

4. Палиндром

Палиндром — это слово, которое читается одинаково в обе стороны. «мадам», «а роза упала на лапу Азора», «12321». Рекурсивный подход: сравнивать первый и последний символы, а затем проверять внутреннюю часть.

public class Palindrome {
    public static boolean isPalindrome(String str) {
        str = str.toLowerCase().replaceAll("\\s+", "");
        return checkPalindrome(str, 0, str.length() - 1);
    }

    private static boolean checkPalindrome(String str,
                                          int left,
                                          int right) {
        if (left >= right) {
            return true;
        }
        if (str.charAt(left) != str.charAt(right)) {
            return false;
        }
        return checkPalindrome(str, left + 1, right - 1);
    }

    public static void main(String[] args) {
        System.out.println("мадам: " + isPalindrome("мадам"));
        System.out.println("привет: " + isPalindrome("привет"));
        System.out.println(" level: " + isPalindrome(" level "));
        System.out.println("12321: " + isPalindrome("12321"));
        System.out.println("hello: " + isPalindrome("hello"));
    }
}

Вывод:

мадам: true
привет: false
 level: true
12321: true
hello: false

5. Числа Фибоначчи — итеративная и рекурсивная версии

Мы уже рассматривали Фибоначчи выше, но давайте ещё раз посмотрим на разницу между рекурсивной и итеративной версиями. Это лучший пример того, когда итеративный подход лучше рекурсивного.

public class FibonacciComparison {
    public static int fibRecursive(int n) {
        if (n <= 1) return n;
        return fibRecursive(n - 1) + fibRecursive(n - 2);
    }

    public static long fibIterative(int n) {
        if (n <= 1) return n;
        long prev = 0;
        long curr = 1;
        for (int i = 2; i <= n; i++) {
            long next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }

    public static void main(String[] args) {
        int n = 40;
        long start1 = System.currentTimeMillis();
        int r = fibRecursive(n);
        long time1 = System.currentTimeMillis() - start1;

        long start2 = System.currentTimeMillis();
        long it = fibIterative(n);
        long time2 = System.currentTimeMillis() - start2;

        System.out.println("Рекурсивно: " + r + " (" + time1 + " мс)");
        System.out.println("Итеративно: " + it + " (" + time2 + " мс)");
    }
}

6. Быстрое возведение в степень

Этот пример показывает мощь рекурсии. Вместо того чтобы умножать a на себя n раз (что требует n умножений), мы можем использовать свойство: a^n = (a^(n/2))^2 при чётном n, и a^n = a * a^(n-1) при нечётном. Это снижает количество операций с O(n) до O(log n).

public class FastPower {
    public static long fastPower(long base, int exponent) {
        if (exponent == 0) return 1;
        if (exponent == 1) return base;

        long half = fastPower(base, exponent / 2);
        if (exponent % 2 == 0) {
            return half * half;
        } else {
            return half * half * base;
        }
    }

    public static void main(String[] args) {
        System.out.println("2^10 = " + fastPower(2, 10));
        System.out.println("3^5 = " + fastPower(3, 5));
        System.out.println("5^0 = " + fastPower(5, 0));
    }
}

Вывод:

2^10 = 1024
3^5 = 243
5^0 = 1

7. Пирамида из звёздочек

Вывести пирамиду из звёздочек высотой n. Рекурсивный подход: вывести верхушку (1 звёздочку), а затем рекурсивно вывести пирамиду высотой n-1, но со сдвигом. Базовый случай: n == 0.

public class Pyramid {
    public static void printPyramid(int n, int indent) {
        if (n == 0) return;

        String spaces = " ".repeat(indent);
        String stars = "* ".repeat(n);
        System.out.println(spaces + stars);

        printPyramid(n - 1, indent + 1);
    }

    public static void main(String[] args) {
        printPyramid(5, 0);
    }
}

Вывод:

* * * * *
 * * * *
  * * *
   * *
    *

8. Рекурсивный поиск в массиве

Поиск элемента в массиве можно реализовать рекурсивно. Идея: проверить первый элемент, если не он — искать в оставшейся части массива. Базовый случай: дошли до конца массива.

public class RecursiveSearch {
    public static int search(int[] arr, int target, int index) {
        if (index == arr.length) {
            return -1;
        }
        if (arr[index] == target) {
            return index;
        }
        return search(arr, target, index + 1);
    }

    public static void main(String[] args) {
        int[] numbers = {10, 25, 30, 45, 50, 65};
        System.out.println("Индекс 30: " + search(numbers, 30, 0));
        System.out.println("Индекс 50: " + search(numbers, 50, 0));
        System.out.println("Индекс 99: " + search(numbers, 99, 0));
    }
}

Вывод:

Индекс 30: 2
Индекс 50: 4
Индекс 99: -1

Советы по написанию рекурсивных методов

Написание рекурсивных методов — это навык, который приходит с практикой. Вот пошаговый алгоритм, который поможет вам решать задачи рекурсивно:

Дополнительные советы:

• Начинайте с малого: сначала решите задачу для самых простых случаев, затем добавляйте сложность
• Рисуйте дерево вызовов: представьте, как рекурсия разворачивается для маленького значения n
• Не бойтесь использовать вспомогательные параметры: иногда проще передать дополнительный параметр (аккумулятор, индекс), чем пытаться обойтись без него
• Помните о памяти: каждый рекурсивный вызов использует память стека. Для n = 10000 это может быть проблемой
• Используйте отладчик: поставьте斷点 на рекурсивный вызов и проследите, как стек растёт и уменьшается
• Проверяйте edge cases: что будет при n = 0, n = 1, n = отрицательное?
• Документируйте базовый случай: в комментарии укажите, при каком условии рекурсия останавливается

Вот ещё один полезный приём — инвариант рекурсии. Это утверждение, которое верно для каждого вызова. Для факториала: «factorial(n) всегда возвращает n!». Если вы можете доказать, что инвариант сохраняется при рекурсивном вызове, то рекурсия корректна. Это похоже на индукцию в математике.

Частые ошибки при работе с рекурсией

Давайте разберём самые частые ошибки, которые допускают новички при написании рекурсивных методов:

Ошибка 1: Забыли базовый случай

public static int badSum(int n) {
    return n + badSum(n - 1);
}

Этот метод никогда не остановится и вызовет StackOverflowError.

Ошибка 2: Базовый случай не обрабатывает все варианты

public static int badFactorial(int n) {
    if (n == 1) return 1;
    return n * badFactorial(n - 1);
}

badFactorial(0);

Если n = 0, метод вызовет badFactorial(-1), затем badFactorial(-2), и так далее до StackOverflowError. Проверяйте все возможные входные значения!

Ошибка 3: Рекурсивный шаг не приближает к базовому случаю

public static int wrongDirection(int n) {
    if (n == 0) return 1;
    return wrongDirection(n + 1);
}

wrongDirection(5);

Здесь n растёт (5, 6, 7, ...) вместо того, чтобы уменьшаться. Рекурсия никогда не достигнет базового случая.

Ошибка 4: Двойной рекурсивный вызов без мемоизации

public static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

fib(40);

Этот код корректен, но крайне неэффективен. Для n = 40 он выполняет более миллиарда операций.

Ошибка 5: Неправильная обработка отрицательных чисел

public static int badSum(int n) {
    if (n == 0) return 0;
    return n + badSum(n - 1);
}

badSum(-5);

Если n = -5, метод вызовет badSum(-6), затем badSum(-7), и так далее. Добавьте проверку на отрицательные числа!

Итоги урока

• ✅ Рекурсия — это метод, который вызывает сам себя для решения задачи, разбивая её на более мелкие подзадачи
• ✅ Каждая рекурсивная функция обязана иметь базовый случай (условие остановки) и рекурсивный шаг (приближение к базовому случаю)
• ✅ Факториал — классический пример: n! = n × (n-1)!, базовый случай: 0! = 1
• ✅ Числа Фибоначчи показывают проблему повторных вычислений — рекурсивная версия имеет экспоненциальную сложность O(2^n)
• ✅ Стек вызовов (call stack) хранит информацию о каждом активном вызове метода. Каждый рекурсивный вызов добавляет новый фрейм на стек
• ✅ StackOverflowError возникает, когда стек переполняется — из-за отсутствия базового случая, недостижимого базового случая или слишком большой глубины рекурсии
• ✅ Рекурсия vs цикл: рекурсия элегантнее для вложенных структур, цикл эффективнее для простых задач. Золотое правило: используйте рекурсию там, где она делает код значительно проще
• ✅ Хвостовая рекурсия — рекурсивный вызов в конце метода. В Java не оптимизируется, но полезна в других языках
• ✅ Мемоизация (запоминание результатов) значительно ускоряет рекурсивные алгоритмы с повторными вычислениями
• ✅ При написании рекурсии: определите базовый случай → напишите рекурсивный шаг → проверьте корректность → проверьте глубину
• ✅ Используйте итерацию, когда рекурсия не даёт преимуществ в читаемости или когда важна производительность

Следующий урок

Классы и объекты — основы объектно-ориентированного программирования