Рекурсия

Проблем

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

На рафта има 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;
}

Console.WriteLine(FactorialLoop(5));

Изход

120

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

Идеята

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

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

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

Console.WriteLine(Factorial(5));

Изход

120

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

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

Виж го

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

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

Console.WriteLine(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;
    }
    Console.WriteLine("слизам " + n);
    Steps(n - 1);
    Console.WriteLine("качвам " + n);
}

Steps(2);

Отговор

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

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

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

Провери

Пробвай

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

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

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

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

Провери

Идеята

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

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

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

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

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

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

Пробвай

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

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

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

Провери

Упражнение

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

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Стекът се препълва и програмата спира с грешка

Провери

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