Рекурсия

Проблем

Колко подредби има?

На рафта има 5 книги. По колко начина можеш да ги подредиш? За първото място има 5 избора, за второто 4, после 3, 2 и 1: 5 · 4 · 3 · 2 · 1 = 120. Това е факториел, пише се 5!.

С цикъл вече го можеш:

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

System.out.println(factorialLoop(5));

Изход

120

Погледни го и така: 5! = 5 · 4!. А 4! = 4 · 3!. Задачата се решава чрез същата задача, само по-малка. Може ли методът да каже точно това?

Идеята

Метод, който вика себе си

Може. Метод, който вика сам себе си, се казва рекурсивен, а подходът е рекурсия.

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

System.out.println(factorial(5));

Изход

120

Две неща го правят да работи:

• Дъно. Случай, който се решава направо, без ново извикване. Тук: 1! = 1.
• По-малка задача. Всяко извикване вика себе си с число, по-близо до дъното: n - 1.

Виж го

Купчината от извиквания

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

System.out.println(factorial(3));  // 6

Стъпка по стъпка, с думи

1. main вика factorial(3).
2. Нова памет за factorial с n = 3.
3. 3 не е 1, затова методът вика factorial(2) и чака отговора.
4. Същото: factorial(2) вика factorial(1). Всяко извикване има свое n.
5. n е 1: това е дъното. Връща 1, без да вика повече.
6. Отговорът слиза надолу: 2 * 1 = 2.
7. И пак: 3 * 2 = 6.
8. factorial(3) връща 6 и main го отпечатва.

Всяко извикване получава своя памет със свое n. Те се трупат едно над друго и чакат. Тази купчина се казва стек от извиквания (call stack). Когато дъното върне 1, отговорите слизат надолу един по един и купчината се разтуря.

Пробвай

Слизане и качване

Какво ще отпечата програмата?

static void steps(int n) {
    if (n == 0) {
        return;
    }
    System.out.println("слизам " + n);
    steps(n - 1);
    System.out.println("качвам " + n);
}

steps(2);

Отговор

слизам 2
слизам 1
качвам 2
качвам 1

слизам 2
слизам 1
качвам 1
качвам 2

слизам 2
качвам 2
слизам 1
качвам 1

Провери

Пробвай

Намери грешката

sumTo(4) трябва да върне 1 + 2 + 3 + 4 = 10. Вместо това програмата спира с StackOverflowError. На кой ред е грешката?

Избери реда с грешката.

1static int sumTo(int n) {2 if (n == 1) {3 return 1;4 }5 return n + sumTo(n);6}

Провери

Идеята

Рекурсия или цикъл?

Факториелът става и с цикъл, и с рекурсия. Цикълът тук е по-добрият избор: не трупа памет за всяко извикване, а за 100 000 извиквания стекът няма да стигне.

Рекурсията е естествена там, където нещото съдържа по-малки неща от същия вид: папка с папки вътре, категория с подкатегории, разклонение с разклонения. Такива задачи ще срещнеш по-нататък в курса. Там цикълът става тромав, а рекурсивният метод остава кратък.

По-точно, за любопитните

• Факториелът често се пише с дъно 0! = 1 (if (n == 0)). Тогава работи и за 0.

• int стига до 12!. За 13! резултатът не се събира и числото излиза грешно. За по-големи стойности ползвай long.

Пробвай

Подреди редовете

Методът трябва да смята степен: power(2, 10) е 1024. Подреди редовете му.

1. return 1;↑↓
2. }↑↓
3. return base * power(base, exp - 1);↑↓
4. if (exp == 0) {↑↓
5. static int power(int base, int exp) {↑↓
6. }↑↓

Провери

Упражнение

Рекурсивни задачи

1. Факториел по два начина. Напиши factorialLoop(int n) с цикъл for и factorial(int n) с рекурсия. Прочети число и отпечатай резултата и от двата метода.

Вход

5

Изход

Факториел на 5 е 120
Факториел на 5 е 120

2. Сума на цифрите. sumDigits(int n): последната цифра (n % 10) плюс сумата на цифрите на останалото (n / 10). Дъното е едноцифрено число.

3. Фибоначи. Всяко число е сумата на предишните две: 0, 1, 1, 2, 3, 5, 8… fib(int n) връща n-тото число. Пробвай с 10, а после с 45. Защо е толкова бавно? Подсказка: колко пъти се смята всяко число?

4. Палиндром. isPalindrome(String s): първата и последната буква са еднакви и средата е палиндром. Дъното е дума с 0 или 1 букви.

Извикване

sumDigits(2024)
fib(10)
isPalindrome("капак")
isPalindrome("АБВГД")

Изход

8
55
true
false

Тест

Провери се

1. Какво е рекурсия?

Метод, който вика сам себе сиЦикъл вътре в методДва метода с едно и също име

2. Защо рекурсивният метод има нужда от дъно?

За да работи по-бързоЗа да може да връща резултатЗа да спре да вика себе си

3. factorial(3) вика factorial(2), той вика factorial(1). Колко променливи n има в паметта точно преди factorial(1) да върне?

Нито еднаЕднаТри

4. Какво става, ако дъното никога не се стигне?

Програмата се върти безкрайно, без грешкаМетодът връща 0Стекът се препълва и програмата спира с грешка

Провери

Започни урока отначало