Рекурсия

Проблем

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

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

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

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result


print(factorial_loop(5))

Изход

120

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

Идеята

Функция, която вика себе си

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

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(5))

Изход

120

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

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

Виж го

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

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(3))  # 6

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

1. Програмата вика 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 и програмата го отпечатва.

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

Пробвай

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

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

def steps(n):
    if n == 0:
        return
    print(f"слизам {n}")
    steps(n - 1)
    print(f"качвам {n}")


steps(2)

Отговор

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

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

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

Провери

Пробвай

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

sum_to(4) трябва да върне 1 + 2 + 3 + 4 = 10. Вместо това програмата спира с RecursionError: maximum recursion depth exceeded. На кой ред е грешката?

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

1def sum_to(n):2 if n == 1:3 return 14 return n + sum_to(n)

Провери

Идеята

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

Факториелът става и с цикъл, и с рекурсия. Цикълът тук е по-добрият избор: не трупа памет за всяко извикване. А Python слага граница на стека: при около 1000 вложени извиквания спира програмата с RecursionError. Още factorial(1100) не минава, а цикълът смята и него.

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

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

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

• Целите числа в Python нямат граница: колкото е голям резултатът, толкова цифри има. 30! излиза точно:

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(30))

Изход

265252859812191058636308480000000

• Границата на стека може да се вдигне с sys.setrecursionlimit(), но това рядко е добра идея: за дълбоки сметки пиши цикъл.

Пробвай

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

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

1. def power(base, exp):↑↓
2. return 1↑↓
3. return base * power(base, exp - 1)↑↓
4. if exp == 0:↑↓

Провери

Упражнение

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

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

Вход

5

Изход

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

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

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

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

Извикване

sum_digits(2024)
fib(10)
is_palindrome("капак")
is_palindrome("АБВГД")

Изход

8
55
True
False

Тест

Провери се

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

Функция, която вика сама себе сиЦикъл вътре във функцияДве функции с едно и също име

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

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

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

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

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

Програмата се върти безкрайно, без грешкаФункцията връща 0Стекът се препълва и програмата спира с RecursionError

Провери

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