Рекурсия

Рекурсия — ин вақтест, ки функсия худашро даъват мекунад. Аҷиб садо медиҳад, вале ин роҳи табиии ҳалли масъалаҳоест, ки ба ҳамин гуна масъалаи хурдтар оварда мешаванд.

Мисоли содда

Суммаи ададҳо аз 1 то n ба n ҷамъ суммаи аз 1 то n - 1 баробар аст. Суммаи аз 1 то 0 бошад — танҳо 0. Ҳамин тавр менависем:

def total(n):
    if n == 0:          # асос: ҷавоб фавран маълум аст
        return 0
    return n + total(n - 1)   # қадам: ба масъалаи хурдтар меорем

print(total(5))   # 15

Ҳар функсияи рекурсивӣ ду қисм дорад:

1. Асос — ҳолате, ки ҷавоб бе даъватҳои нав маълум аст. Бе он рекурсия қатъ намешавад.
2. Қадам — овардани масъала ба ҳамон масъала, вале хурдтар, тавре ки дер ё зуд ба асос расем.

Ин чӣ тавр иҷро мешавад

Ҳар даъват интизор мешавад, то даъвати дарунӣ баргардад:

total(3) = 3 + total(2)
               total(2) = 2 + total(1)
                              total(1) = 1 + total(0)
                                             total(0) = 0
                              total(1) = 1
               total(2) = 3
total(3) = 6

Даъватҳо «тӯда» мешаванд, баъд ба қафо кушода мешаванд. Ин намоён аст, агар пеш ва пас аз даъвати дарунӣ чоп кунем:

def countdown(n):
    if n == 0:
        print("Старт!")
        return
    print(n)
    countdown(n - 1)

countdown(3)    # 3, 2, 1, Старт!

Чуқурии рекурсия

Python чуқуриро маҳдуд мекунад — тақрибан 1000 даъвати дарунӣ. Баъд RecursionError мешавад. Барои рекурсияи чуқур ҳадро баланд кардан мумкин аст:

import sys
sys.setrecursionlimit(10000)

Вале агар рекурсия танҳо давраи «аз n то 0» бо як миллион қадам бошад, давра навиштан беҳтар аст.

Нисф кардан

Рекурсия махсусан вақте хуб аст, ки масъала ба нисфҳо тақсим мешавад. Он гоҳ чуқурӣ хурд аст: барои n = 10^18 — ҳамагӣ тақрибан 60 сатҳ.

Мисол: ададро чанд бор нисф кардан (бутун) мумкин аст, то он як шавад?

def halvings(n):
    if n == 1:
        return 0
    return 1 + halvings(n // 2)

print(halvings(1000))   # 9

Чунин ғоя — «барои нисф ҳал кун ва ҷавобро пурра соз» — дар бисёр алгоритмҳои тез вомехӯрад.

Ададҳои Фибоначчи ва ҳисобкуниҳои такрорӣ

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Код дуруст аст, вале барои n = 40 хеле дароз кор мекунад: fib(38) ду бор, fib(37) се бор ҳисоб карда мешавад ва ҳамин тавр. Шумораи даъватҳо мисли худи ададҳои Фибоначчи меафзояд.

Бо дар хотир нигоҳ доштани ҳисобшуда табобат мешавад:

memo = {}
def fib(n):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print(fib(90))   # 2880067194370816120

Гузаштан аз вариантҳо

Қувваи асосии рекурсия — гузаштан аз ҳамаи вариантҳо (перебор), вақте сохтори онҳо «шоха мезанад». Масалан, ҳамаи сатрҳои дуии дарозиаш n: дар ҳар мавқеъ 0 ё 1 мегузорем ва боқимондаро рекурсивӣ пур мекунем.

def binary(prefix, n):
    if len(prefix) == n:
        print(prefix)
        return
    binary(prefix + "0", n)
    binary(prefix + "1", n)

binary("", 3)    # 000 001 010 011 100 101 110 111

Аз ҳар даъват ду шоха мебарояд, бинобар ин сатрҳо 2 ** n тоанд. Ин бисёр аст: ҳангоми n = 20 аллакай як миллион, ҳангоми n = 40 — як триллион. Бо гузаштан масъалаҳоеро ҳал мекунанд, ки дар онҳо n хурд аст: дар шарт инро одатан аз маҳдудиятҳое мисли n ≤ 20 дидан мумкин аст.

Ба ҳамин монанд интихобҳои «элементро гирифтан ё нагирифтан», ҷойгиркуниҳо, роҳҳоро мегузаранд — нақшаи умумӣ:

1. агар варианти ҷорӣ пурра ҷамъ шуда бошад — онро коркард кун;
2. вагарна барои ҳар қадами имконпазири навбатӣ: қадам гузор, рекурсивӣ идома деҳ, қадамро бекор кун.

Банди «қадамро бекор кун» вақте муҳим аст, ки рӯйхати умумиро тағйир медиҳӣ: элемент илова кардӣ — пас аз даъвати рекурсивӣ онро гир (pop).

Хулоса

• функсияи рекурсивӣ худашро даъват мекунад; он ҳатман асос ва қадам дорад;
• чуқурӣ маҳдуд аст (~1000), sys.setrecursionlimit ҳадро баланд мекунад;
• нисф кардани масъала чуқурии хурд ва алгоритмҳои тез медиҳад;
• ҳисобкуниҳои такрорӣ бо дар хотир нигоҳ доштан дар луғат табобат мешаванд;
• гузаштани рекурсивӣ: интихоб кун → рекурсия → интихобро бекор кун; шумораи вариантҳо хеле зуд меафзояд.