📋 План лекции

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

Рекурсия (от латинского «recursio» — возвращение назад) — это приём в программировании, при котором функция (или метод) вызывает сама себя для решения задачи.

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

🌍 Рекурсия вокруг нас

Рекурсия встречается не только в программировании, но и в повседневной жизни:

• 🪞 Зеркала напротив друг друга — в отражении видно отражение, в нём ещё одно отражение, и так далее (бесконечная рекурсия).
• 🌳 Дерево — ствол делится на ветки, ветки на веточки, веточки на листья. Каждая ветка устроена по тому же принципу, что и всё дерево.
• 📁 Папки в компьютере — в папке могут быть другие папки, в них ещё папки, и так до любой глубины.
• 📖 Словарь — определение слова содержит другие слова, которые тоже нужно искать в словаре.
• 🧅 Матрёшка — внутри большой матрёшки средняя, внутри средней маленькая, и так далее.

📚 Как работает рекурсия: стек вызовов

Чтобы понять рекурсию, нужно разобраться, как Java хранит информацию о вызовах функций. Для этого используется специальная область памяти, которая называется стек вызовов (call stack).

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

Когда функция вызывает другую функцию (или саму себя), Java делает следующее:

1. 📥 Кладёт на стек «карточку» с информацией о текущем вызове: какие параметры переданы, на какой строке остановились, какие локальные переменные есть.
2. 🚀 Запускает вызванную функцию.
3. 📤 Когда функция завершается, Java снимает её «карточку» со стека и возвращается к предыдущей.

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

Любая рекурсивная функция должна содержать два обязательных элемента, иначе она будет работать бесконечно:

1. Базовый случай (base case)

Это условие, при котором функция перестаёт вызывать саму себя и просто возвращает результат. Это «конец цепочки», точка остановки.

2. Рекурсивный случай (recursive case)

Это условие, при котором функция вызывает саму себя, но с более простыми входными данными. Каждый такой вызов должен приближать нас к базовому случаю.

🧮 Первый пример: факториал числа

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

Например: 5! = 1 × 2 × 3 × 4 × 5 = 120

Заметим важную закономерность: 5! = 4! × 5, 4! = 3! × 4, и так далее. То есть:

Запишем это на Java:

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

🔍 Пошаговая трассировка factorial(4)

Посмотрим, как Java вычисляет factorial(4), шаг за шагом:

factorial(4)
├─ 4 * factorial(3)
│   ├─ 3 * factorial(2)
│   │   ├─ 2 * factorial(1)
│   │   │   └─ 1  ← базовый случай, возвращаем 1
│   │   └─ возвращаем 2 * 1 = 2
│   └─ возвращаем 3 * 2 = 6
└─ возвращаем 4 * 6 = 24

Обратите внимание на два этапа:

1. 📥 Погружение (раскрутка) — функция вызывает саму себя, каждый раз откладывая вычисление на стек. Мы идём «вглубь», пока не достигнем базового случая.
2. 📤 Всплытие (свёртка) — начиная с базового случая, значения возвращаются обратно по цепочке, и на каждом шаге происходит умножение.

💻 Полный пример: факториал

public class Factorial {
    
    public static int factorial(int n) {
        // Базовый случай: 0! = 1 и 1! = 1
        if (n == 0 || n == 1) {
            return 1;
        }
        // Рекурсивный случай: n! = n * (n-1)!
        return n * factorial(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println("0! = " + factorial(0)); // 1
        System.out.println("1! = " + factorial(1)); // 1
        System.out.println("5! = " + factorial(5)); // 120
        System.out.println("10! = " + factorial(10)); // 3628800
    }
}

🐰 Числа Фибоначчи

Числа Фибоначчи — это знаменитая последовательность, в которой каждое число равно сумме двух предыдущих:

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

Эта последовательность была описана итальянским математиком Леонардо Фибоначчи в 1202 году при решении задачи о размножении кроликов. Удивительно, но числа Фибоначчи встречаются в природе: в расположении лепестков цветов, в спиралях раковин, в сосновых шишках.

Рекурсивное определение:

💻 Наивная рекурсия для Фибоначчи

public class Fibonacci {
    
    public static long fib(int n) {
        // Базовые случаи
        if (n == 0) return 0;
        if (n == 1) return 1;
        // Рекурсивный случай
        return fib(n - 1) + fib(n - 2);
    }
    
    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.println("F(" + i + ") = " + fib(i));
        }
    }
}

Этот код работает, но... есть огромная проблема. Давайте разберёмся, в чём она.

🐢 Проблема: экспоненциальная сложность

Когда мы вычисляем fib(5), происходит следующее:

fib(5)
├─ fib(4)
│   ├─ fib(3)
│   │   ├─ fib(2)
│   │   │   ├─ fib(1) → 1
│   │   │   └─ fib(0) → 0
│   │   └─ fib(1) → 1  ← уже считали!
│   └─ fib(2)          ← уже считали!
│       ├─ fib(1) → 1
│       └─ fib(0) → 0
└─ fib(3)              ← уже считали!
    ├─ fib(2)          ← уже считали!
    └─ fib(1) → 1

⚡ Решение: мемоизация

Мемоизация (от латинского «memorabilis» — достойный запоминания) — это приём, при котором мы сохраняем результаты уже вычисленных значений, чтобы не пересчитывать их повторно.

Проще говоря: «посчитал — запомнил — в следующий раз просто взял из памяти».

public class FibonacciMemo {
    // Массив для хранения уже посчитанных значений
    private static long[] memo;
    
    public static long fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        // Если уже считали — берём из памяти
        if (memo[n] != 0) {
            return memo[n];
        }
        
        // Иначе считаем и сохраняем
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }
    
    public static void main(String[] args) {
        memo = new long[100];
        System.out.println("F(50) = " + fib(50));   // Мгновенно!
        System.out.println("F(90) = " + fib(90));   // Мгновенно!
    }
}

⚖️ Рекурсия vs итерация

Почти любую рекурсивную задачу можно решить с помощью цикла (итерации). Когда что использовать?

🔁 Факториал через цикл

Для сравнения, вот итеративная версия факториала — она быстрее и не использует стек:

public class FactorialIterative {
    
    public static long factorial(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));   // 120
        System.out.println("20! = " + factorial(20)); // 2432902008176640000
    }
}

Эта версия работает быстрее и не рискует переполнить стек. Но рекурсивная версия красивее и ближе к математическому определению.

🗼 Ханойские башни — классика рекурсии

Ханойские башни — это знаменитая головоломка, придуманная французским математиком Эдуардом Люка в 1883 году.

Условия задачи:

• Есть три стержня (A, B, C).
• На стержне A надета пирамидка из n дисков разного размера (большие внизу, маленькие вверху).
• Нужно перенести всю пирамидку на стержень C.
• Правила: за один раз можно переносить только один диск; нельзя класть больший диск на меньший.

💡 Рекурсивное решение

Идея решения удивительно проста:

1. Перенести верхние n-1 дисков с A на B (используя C как вспомогательный).
2. Перенести самый большой диск с A на C.
3. Перенести n-1 дисков с B на C (используя A как вспомогательный).

public class HanoiTowers {
    
    public static void hanoi(int n, char from, char to, char help) {
        if (n == 0) return; // Базовый случай
        
        // 1. Переносим n-1 дисков с 'from' на 'help' через 'to'
        hanoi(n - 1, from, help, to);
        
        // 2. Переносим самый большой диск с 'from' на 'to'
        System.out.println("Диск " + n + ": " + from + " → " + to);
        
        // 3. Переносим n-1 дисков с 'help' на 'to' через 'from'
        hanoi(n - 1, help, to, from);
    }
    
    public static void main(String[] args) {
        hanoi(3, 'A', 'C', 'B');
    }
}

📋 Результат для 3 дисков

Вызов hanoi(3, 'A', 'C', 'B') выведет:

Диск 1: A → C
Диск 2: A → B
Диск 1: C → B
Диск 3: A → C
Диск 1: B → A
Диск 2: B → C
Диск 1: A → C

Всего 7 перемещений. Для n дисков нужно 2ⁿ − 1 перемещений:

📁 Практический пример: обход файловой системы

Рекурсия идеально подходит для обхода папок, потому что папки — это дерево: в папке могут быть другие папки, в них ещё папки, и так до любой глубины.

import java.io.File;

public class FileWalker {
    
    public static void listFiles(File folder, int depth) {
        // Перебираем все файлы и папки в текущей папке
        for (File file : folder.listFiles()) {
            // Выводим отступы для наглядности
            for (int i = 0; i < depth; i++) {
                System.out.print("  ");
            }
            System.out.println(file.getName());
            
            // Если это папка — рекурсивно заходим в неё
            if (file.isDirectory()) {
                listFiles(file, depth + 1);
            }
        }
    }
    
    public static void main(String[] args) {
        File folder = new File("C:\\Users");
        listFiles(folder, 0);
    }
}

💥 Типичная ошибка: StackOverflowError

Если забыть базовый случай или сделать так, что рекурсия никогда не остановится, Java выдаст ошибку StackOverflowError (ошибка переполнения стека).

// ❌ ОШИБКА: нет базового случая!
public static int badFactorial(int n) {
    return n * badFactorial(n - 1); // Бесконечная рекурсия
}

// ❌ ОШИБКА: рекурсия не приближается к базовому случаю
public static int wrongFactorial(int n) {
    if (n == 0) return 1;
    return n * wrongFactorial(n); // n не уменьшается!
}

// ✅ ПРАВИЛЬНО: есть базовый случай и движение к нему
public static int factorial(int n) {
    if (n == 0) return 1;         // Базовый случай
    return n * factorial(n - 1);  // n уменьшается → приближаемся к 0
}

🛡️ Защита от некорректных данных

Хорошая рекурсивная функция должна проверять входные данные:

public static int factorial(int n) {
    // Защита от некорректных данных
    if (n < 0) {
        throw new IllegalArgumentException(
            "Факториал отрицательного числа не определён: " + n
        );
    }
    
    // Базовый случай
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // Рекурсивный случай
    return n * factorial(n - 1);
}

public static void main(String[] args) {
    System.out.println(factorial(5));   // 120
    // System.out.println(factorial(-3)); // Ошибка!
}

🔢 Пример: сумма цифр числа

Напишем рекурсивную функцию, которая считает сумму цифр числа. Например, для 1234: 1 + 2 + 3 + 4 = 10.

Идея: Чтобы получить последнюю цифру, берём остаток от деления на 10 (n % 10). Чтобы отбросить последнюю цифру, делим на 10 нацело (n / 10).

public static int sumOfDigits(int n) {
    // Защита от отрицательных чисел
    n = Math.abs(n);
    
    // Базовый случай: однозначное число
    if (n < 10) {
        return n;
    }
    
    // Рекурсивный случай: последняя цифра + сумма остальных
    return (n % 10) + sumOfDigits(n / 10);
}

public static void main(String[] args) {
    System.out.println(sumOfDigits(1234)); // 10
    System.out.println(sumOfDigits(9876)); // 30
    System.out.println(sumOfDigits(0));    // 0
}

⚡ Пример: возведение в степень

Вычислим xⁿ рекурсивно. Заметим, что:

• x⁰ = 1 (базовый случай)
• xⁿ = x × xⁿ⁻¹ (рекурсивный случай)

public static double power(double x, int n) {
    // Базовый случай
    if (n == 0) return 1;
    
    // Для отрицательной степени: x⁻ⁿ = 1 / xⁿ
    if (n < 0) {
        return 1.0 / power(x, -n);
    }
    
    // Рекурсивный случай
    return x * power(x, n - 1);
}

public static void main(String[] args) {
    System.out.println(power(2, 10));   // 1024
    System.out.println(power(3, 5));    // 243
    System.out.println(power(2, -3));   // 0.125
}

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

Обычная рекурсия делает n вызовов. Но можно быстрее! Используем наблюдение:

• Если n чётное: xⁿ = (x²)ⁿ/²
• Если n нечётное: xⁿ = x × xⁿ⁻¹

public static double fastPower(double x, int n) {
    if (n == 0) return 1;
    if (n < 0) return 1.0 / fastPower(x, -n);
    
    if (n % 2 == 0) {
        // Чётная степень: xⁿ = (x²)ⁿ/²
        double half = fastPower(x, n / 2);
        return half * half;
    } else {
        // Нечётная степень: xⁿ = x × xⁿ⁻¹
        return x * fastPower(x, n - 1);
    }
}

// Для power(2, 100) обычный метод сделает 100 вызовов,
// а fastPower — всего около 7! (логарифмическая сложность)

⚠️ Типичные ошибки при работе с рекурсией

1. Отсутствие базового случая — рекурсия никогда не остановится, будет StackOverflowError.
2. Рекурсия не приближается к базовому случаю — например, вызов factorial(n) вместо factorial(n-1).
3. Неправильный базовый случай — например, для факториала проверить только n == 0, но вызвать с отрицательным числом.
4. Забыть вернуть значение — в рекурсивной ветке забыли написать return.
5. Наивная рекурсия для Фибоначчи — экспоненциальная сложность, программа «виснет».
6. Использование рекурсии там, где нужен цикл — например, для простого перебора массива.

💪 Задачи для самостоятельного решения

1. Напишите рекурсивную функцию для вычисления суммы чисел от 1 до n: sum(5) = 1 + 2 + 3 + 4 + 5 = 15.
2. Напишите рекурсивную функцию для проверки, является ли строка палиндромом (читается одинаково слева направо и справа налево): «казак», «шалаш».
3. Напишите рекурсивную функцию для нахождения наибольшего общего делителя (НОД) двух чисел по алгоритму Евклида: НОД(a, b) = НОД(b, a mod b).
4. Напишите рекурсивную функцию, которая переворачивает строку: reverse("привет") = "тевирп".
5. Напишите рекурсивную функцию для вывода всех перестановок символов в строке.
6. Модифицируйте программу «Ханойские башни» так, чтобы она считала и выводила общее количество перемещений.

✅ Итоги лекции

• Рекурсия — это когда функция вызывает сама себя для решения задачи.
• Любая рекурсия должна иметь базовый случай (где остановиться) и рекурсивный случай (где сделать шаг к базовому).
• Java хранит информацию о вызовах функций в стеке вызовов.
• Если рекурсия бесконечная — будет ошибка StackOverflowError.
• Мемоизация — приём сохранения уже посчитанных значений для ускорения рекурсии.
• Рекурсия идеальна для древовидных структур: папки, деревья, графы, Ханойские башни.
• Для линейных задач (сумма, факториал) часто лучше использовать цикл.

🚀 Что дальше?

На следующих лекциях мы продолжим изучать подпрограммы и структуры данных:

• 📦 Множества (Set) — коллекции без дубликатов
• 📁 Файлы прямого доступа — работа с файлами на низком уровне
• 🎯 Коллекции Java — ArrayList, HashMap и другие
• 🔗 Связанные списки — структуры данных на основе указателей

📚 Спасибо за внимание!

Вопросы?

← Вернуться на главную страницу