Rekursiya: özünü çağıran funksiyalar

Funksiya məsələni özünün kiçik variantını çağırmaqla necə həll edir: baza halı və rekursiv addım, çağırış steki və `RecursionError`, faktorial, Fibonaççi, rəqəmlərin cəmi, rekursiv ikili axtarış, iç-içə siyahılar və qovluq ağacları, həmçinin dövrün və ya `lru_cache`-in daha yaxşı olduğu hallar.

  • Orta
  • 22 dəq
  • 12 sual
  • 66 dərsdən 11-cisi

Bu dərsdə öyrənəcəksən

  • Düzgün baza halı və ona doğru irəliləyən rekursiv addımı olan funksiya yazmaq
  • Çağırış stekinin necə böyüyüb kiçildiyini və RecursionError-un niyə yarandığını izah etmək
  • Klassik məsələləri rekursiya ilə həll etmək: faktorial, Fibonaççi, rəqəmlərin cəmi, ikili axtarış
  • İç-içə verilənləri (siyahılar, qovluqlar) emal etmək və rekursiya, dövr və lru_cache arasında seçim etmək

Qovluqda fayllar və başqa qovluqlar var, o qovluqların içində də yenə fayllar və qovluqlar. İç-içəliyin nə qədər dərin olduğunu bilmədən bütün faylları necə saymaq olar? for dövrü nəyin üzərindən keçəcəyini əvvəlcədən bilməlidir. Amma bu məsələnin gözəl xassəsi var: alt qovluqdakı faylları saymaq eyni məsələdir, sadəcə daha kiçikdir. Məsələni onun kiçik hissəsi üçün özünü çağırmaqla həll edən funksiyaya rekursiv funksiya deyilir. «Funksiyalar» dərsində funksiya yaratmağı və çağırmağı öyrəndin, indi funksiya özü-özünü çağıracaq.

RekursiyaTərif

Funksiyanın özünü daha kiçik və ya sadə girişlə çağırdığı həll üsulu. Hər rekursiv funksiyanın iki hissəsi var: yeni çağırış etmədən cavabı dərhal verən baza halı və məsələni kiçildib funksiyanı yenidən çağıran rekursiv addım.

Baza halı və rekursiv addım

Ən sadə nümunə geri sayımdır. countdown(3) 3 yazır, qalan işi — 2-dən geri saymağı — countdown(2)-yə verir. n 0-a çatanda funksiya Start! yazıb dayanır: bu, baza halıdır. Faktorial da belə qurulub: 5!-u tapmaq üçün 4! lazımdır, 4! üçün 3! və s., ta 1! = 1-ə qədər.

n! = n · (n − 1)!0! = 1! = 1

Burada

n
natural ədəd
n!
1 · 2 · … · n hasili

Qaydada eyni əməl daha kiçik ədəd üçün təkrarlanır (rekursiv addım) və hesablamadan bildiyimiz qiymət var (baza halı).

Python
def countdown(n):
    if n == 0:               # base case
        print('Start!')
        return
    print(n)
    countdown(n - 1)         # recursive step


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


countdown(3)
print(factorial(5), factorial(10))
Gözlənilən nəticə
3
2
1
Start!
120 3628800
countdown heç nə qaytarmır, sadəcə çap edir; factorial isə nəticəni return ilə yuxarıdakı çağırışa qaytarır.

Nümunə: factorial(4) addım-addım

Məsələ

Kodu işə salmadan factorial(4)-ü addım-addım hesabla və neçə çağırış olduğunu de.

Həllini göstərHəllini gizlət

Həll

factorial(4) = 4 · factorial(3)
factorial(3) = 3 · factorial(2)
factorial(2) = 2 · factorial(1)
factorial(1) = 1 — baza halı, yeni çağırış yoxdur.
İndi nəticələr geri qayıdır: 2 · 1 = 2, 3 · 2 = 6, 4 · 6 = 24.
Cəmi 4 çağırış olur: n = 4, 3, 2, 1 üçün bir dəfə.

Davamını oxumaq üçün pulsuz qeydiyyatdan keç

Dərsin qalan bölmələri, test və qeydlər Educora hesabı ilə açılır. Qeydiyyat bir dəqiqə çəkir; irəliləyişin bütün cihazlarında saxlanılır.

Çağırış steki və RecursionError

Bir funksiya eyni anda bir neçə dəfə necə işləyə bilər? Hər çağırış öz çərçivəsini (frame) alır: öz parametrləri və lokal dəyişənləri olan kiçik yaddaş sahəsi. Çərçivələr çağırış stekində saxlanılır: yeni çağırış ən üstə qoyulur, return ilə bitən çağırışın çərçivəsi isə götürülür və nəticə aşağıdakı çərçivəyə ötürülür. factorial(1) işləyərkən factorial(4), factorial(3) və factorial(2) stekdə gözləyir, hər birinin öz n-i var.

Çağırış stekiTərif

Başlamış, amma hələ bitməmiş funksiya çağırışlarının «son gələn — ilk gedər» qaydası ilə düzülmüş siyahısı. Ən üstdəki çərçivə hazırda işləyəndir, qalanları onun nəticəsini gözləyir.

↑ yeni çağırış üstə qoyulurqaytarırfactorial(1)baza halı: 1 qaytarırfactorial(2)gözləyir: 2 · factorial(1)factorial(3)gözləyir: 3 · factorial(2)print(factorial(3))proqram nəticəni gözləyir126
Çağırışlar steki yuxarı böyüdür, return isə onu yuxarıdan aşağı boşaldır.
Python
def factorial(n, depth=0):
    pad = '    ' * depth
    print(f'{pad}factorial({n}) called')
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(f'{pad}factorial({n}) returns {result}')
    return result


print('answer:', factorial(4))
Gözlənilən nəticə
factorial(4) called
    factorial(3) called
        factorial(2) called
            factorial(1) called
            factorial(1) returns 1
        factorial(2) returns 2
    factorial(3) returns 6
factorial(4) returns 24
answer: 24
Girinti stekin dərinliyini göstərir. Çağırışlar baza halına qədər enir, nəticələr isə əks sıra ilə geri qayıdır.

Stek sonsuz deyil. CPython susmaya görə təxminən 1000 iç-içə çağırışa icazə verir (sys.getrecursionlimit() həddi göstərir). Baza halı yoxdursa və ya ona heç vaxt çatılmırsa, çağırışlar bitmir, hədd aşılır və Python proqramı RecursionError: maximum recursion depth exceeded xətası ilə dayandırır. Aşağıda broken-in ümumiyyətlə baza halı yoxdur, also_broken-in isə var, amma tək n üçün n − 2 addımı 0-ın üstündən tullanır:

Python
def broken(n):
    return n * broken(n - 1)          # no base case


def also_broken(n):
    if n == 0:
        return 0
    return n + also_broken(n - 2)     # an odd n jumps over 0


for func, arg in ((broken, 5), (also_broken, 6), (also_broken, 7)):
    try:
        print(func.__name__, arg, '->', func(arg))
    except RecursionError:
        print(func.__name__, arg, '-> RecursionError')
Gözlənilən nəticə
broken 5 -> RecursionError
also_broken 6 -> 12
also_broken 7 -> RecursionError
also_broken(6) = 6 + 4 + 2 + 0 = 12. 7 ilə ardıcıllıq 7, 5, 3, 1, −1, … olur və 0-a heç vaxt rast gəlmir. Daha etibarlı baza halı if n <= 0 olardı.

`return` unudulub

def digit_sum(n):
    if n < 10:
        return n
    n % 10 + digit_sum(n // 10)

düzgün

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)
return olmadan digit_sum(25) None qaytarır, 2026 üçün isə proqram hətta çökür: bir səviyyə yuxarıda Python 2 + None hesablamalı olur və TypeError: unsupported operand type(s) for +: 'int' and 'NoneType' verir.

Klassik məsələlər: rəqəmlərin cəmi, Fibonaççi, ikili axtarış

Riyaziyyatda bir çox tərif artıq rekursivdir. Ədədin rəqəmlərinin cəmi onun son rəqəmi (n % 10) üstəgəl bu rəqəmsiz ədədin (n // 10) rəqəmlərinin cəmidir; birrəqəmli ədədin rəqəmlərinin cəmi isə ədədin özüdür. Fibonaççi ədədləri ardıcıllığın əvvəlki iki həddi ilə təyin olunur.

S(n) = n % 10 + S(n // 10)S(n) = n, if n < 10

Burada

S(n)
n ədədinin rəqəmlərinin cəmi
n % 10
10-a bölünmədən qalıq — son rəqəm
n // 10
tam bölmə — son rəqəmi atır

S(2026) = 6 + S(202) = 6 + 2 + S(20) = 6 + 2 + 0 + S(2) = 10.

F(n) = F(n − 1) + F(n − 2)F(0) = 0F(1) = 1

Burada

F(n)
n-ci Fibonaççi ədədi

Addım iki həddi geriyə baxdığı üçün iki baza halı lazımdır.

Python
def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)


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


print(digit_sum(2026), digit_sum(4096), digit_sum(987654321))
print([fib(n) for n in range(12)])
Gözlənilən nəticə
10 19 45
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
4096 → 6 + 9 + 0 + 4 = 19; 987654321 → 9 + 8 + … + 1 = 45.

Nümunələr: nəticəni qabaqcadan de

Məsələ

1) digit_sum(507); 2) fib(7); 3) 6 rəqəmli ədəd üçün digit_sum neçə dəfə çağırılır?

Həllini göstərHəllini gizlət

Həll

1) 7 + digit_sum(50) = 7 + 0 + digit_sum(5) = 7 + 0 + 5 = 12.
2) F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8, F(7) = 13.
3) Hər çağırış bir rəqəmi atır, ta bir rəqəm qalana qədər: 6 rəqəmli ədəd üçün 6 çağırış (k rəqəm — k çağırış).

Fibonaççi funksiyası qısadır, amma çox yavaşdır. Hər çağırış daha iki çağırış edir və eyni qiymətlər təkrar-təkrar hesablanır: fib(5) fib(3)-ü iki dəfə, fib(2)-ni üç dəfə hesablayır. Çağırışların sayı demək olar ki, Fibonaççi ədədlərinin özü qədər sürətlə artır:

calls(n) = 2 · F(n + 1) − 1

Burada

calls(n)
sadə fib(n)-in etdiyi çağırışların sayı

n = 20 üçün F(21) = 10946, deməli 2 · 10946 − 1 = 21891 çağırış — aşağıdakı proqram da məhz bu qədər sayır.

Python
from functools import lru_cache

calls = 0


def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)


for n in (10, 20, 25):
    calls = 0
    value = fib(n)
    print(f'fib({n}) = {value}: {calls} calls')


@lru_cache(maxsize=None)
def fib_cached(n):
    return n if n < 2 else fib_cached(n - 1) + fib_cached(n - 2)


def fib_loop(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


print(fib_cached(90), fib_loop(90), fib_cached.cache_info().misses)
Gözlənilən nəticə
fib(10) = 55: 177 calls
fib(20) = 6765: 21891 calls
fib(25) = 75025: 242785 calls
2880067194370816120 2880067194370816120 91
lru_cache hər nəticəni yadda saxlayır, ona görə fib_cached(90) yalnız 91 real hesablama (misses) edir — 0-dan 90-a qədər hər n üçün bir dəfə. Dövr variantı yalnız son iki ədədi saxlayır və steksiz işləyir. lru_cache-in necə işlədiyi «Dekoratorlar və qapanmalar» dərsində izah olunur.

İkili axtarış sıralanmış siyahıda qiyməti hər addımda aralığı yarıya bölməklə tapır — hər addım eyni məsələni yarı verilənlər üzərində həll edir. Siyahını kəsmək əvəzinə lo və hi sərhədlərini ötürürük, çünki hər kəsik elementlərin surətini çıxarardı.

  1. Boş aralıq

    lo > hi olarsa, qiymət yoxdur: -1 qaytar (baza halı).

  2. Orta element

    mid = (lo + hi) // 2; items[mid] == target olarsa, mid-i qaytar (baza halı).

  3. Sağ yarı

    items[mid] < target olarsa, [mid + 1..hi] aralığında axtar.

  4. Sol yarı

    Əks halda [lo..mid − 1] aralığında axtar.

Python
def binary_search(items, target, lo=0, hi=None):
    if hi is None:
        hi = len(items) - 1
    if lo > hi:                          # base case: nothing left
        return -1
    mid = (lo + hi) // 2
    print(f'  range [{lo}..{hi}], items[{mid}] = {items[mid]}')
    if items[mid] == target:             # base case: found
        return mid
    if items[mid] < target:
        return binary_search(items, target, mid + 1, hi)
    return binary_search(items, target, lo, mid - 1)


scores = [12, 25, 31, 47, 58, 63, 77, 84, 90, 96]
print('77 at index', binary_search(scores, 77))
print('50 at index', binary_search(scores, 50))
Gözlənilən nəticə
  range [0..9], items[4] = 58
  range [5..9], items[7] = 84
  range [5..6], items[5] = 63
  range [6..6], items[6] = 77
77 at index 6
  range [0..9], items[4] = 58
  range [0..3], items[1] = 25
  range [2..3], items[2] = 31
  range [3..3], items[3] = 47
50 at index -1
10 element üçün ən çoxu 4 addım lazımdır: aralıq 10 → 5 → 2 → 1 olur. Milyon element üçün təxminən 20 addım kifayətdir, çünki 2²⁰ ≈ 10⁶.

İnteraktiv

Simulyasiya yüklənir…
İkili axtarışın aralığı addım-addım necə yarıya böldüyünə bax.

Rekursiv verilənlər: iç-içə siyahılar və qovluq ağacları

Rekursiya ən təbii görünür, əgər verilənlərin özü rekursivdirsə: siyahıların içində siyahılar, qovluqların içində qovluqlar, cavabların da cavabları olan şərhlər. Funksiyanın quruluşu verilənlərin quruluşunu təkrarlayır: adi element üçün baza halı işləyir, iç-içə element üçün funksiya yenidən çağırılır.

Python
def total(data):
    result = 0
    for item in data:
        if isinstance(item, list):
            result += total(item)        # a smaller list of the same kind
        else:
            result += item
    return result


def depth(data):
    if not isinstance(data, list):
        return 0
    return 1 + max((depth(x) for x in data), default=0)


expenses = [120, [30, 45, [5, 5]], 60, [[10], 20]]
print(total(expenses), depth(expenses))
print(total([]), depth([]), depth(7))
Gözlənilən nəticə
295 3
0 1 0
total istənilən dərinlikdəki bütün ədədləri toplayır: 120 + 30 + 45 + 5 + 5 + 60 + 10 + 20 = 295. depth mötərizə səviyyələrini sayır; default=0 boş siyahını idarə edir.

Qovluq ağacını iç-içə lüğətlərlə təsvir etmək olar: açar addır, ədəd KB ilə fayl ölçüsüdür, lüğət isə alt qovluqdur. Funksiya ağacı çap edir və ölçüsünü qaytarır; hər alt qovluğu eyni funksiya bir səviyyə dərində emal edir:

Python
tree = {
    'school': {
        'math': {'algebra.pdf': 320, 'geometry.pdf': 410},
        'photos': {'trip': {'baku.jpg': 2048, 'quba.jpg': 1730}, 'class.png': 960},
        'plan.txt': 12,
    }
}


def show(folder, indent=0):
    size = 0
    for name, content in folder.items():
        if isinstance(content, dict):          # a folder: recurse
            print('    ' * indent + name + '/')
            size += show(content, indent + 1)
        else:                                  # a file: base case
            print('    ' * indent + f'{name} ({content} KB)')
            size += content
    return size


print('Total:', show(tree), 'KB')
Gözlənilən nəticə
school/
    math/
        algebra.pdf (320 KB)
        geometry.pdf (410 KB)
    photos/
        trip/
            baku.jpg (2048 KB)
            quba.jpg (1730 KB)
        class.png (960 KB)
    plan.txt (12 KB)
Total: 5480 KB

İndi əsl disk. pathlib modulunda Path.iterdir() qovluğun içindəkiləri sadalayır, is_dir() isə qovluğu fayldan ayırır. Proqram əvvəlcə kiçik layihə qovluğu yaradır (bu da rekursivdir), sonra onu gəzir və hər qovluqdakı faylların sayını və bayt həcmini bildirir:

Python
from pathlib import Path


def make(folder, spec):
    for name, content in spec.items():
        path = folder / name
        if isinstance(content, dict):
            path.mkdir()
            make(path, content)
        else:
            path.write_text('x' * content)


def report(folder, indent=0):
    files, size = 0, 0
    for path in sorted(folder.iterdir()):
        if path.is_dir():
            f, s = report(path, indent + 1)
            print('  ' * indent + f'{path.name}/  files={f}, bytes={s}')
            files, size = files + f, size + s
        else:
            files, size = files + 1, size + path.stat().st_size
    return files, size


root = Path('project')
root.mkdir()
make(root, {'docs': {'a.txt': 120, 'b.txt': 80, 'old': {'c.txt': 300}},
            'src': {'main.py': 450}, 'readme.md': 50})
print(report(root))
print(sum(p.stat().st_size for p in root.rglob('*') if p.is_file()))
Gözlənilən nəticə
  old/  files=1, bytes=300
docs/  files=3, bytes=500
src/  files=1, bytes=450
(5, 1000)
1000
Qovluğun sətri onun alt qovluqlarının sətirlərindən sonra çap olunur, çünki yekunlar yalnız onlar sayılandan sonra məlum olur. rglob('*') ağacı sənin əvəzinə gəzir və eyni 1000 baytı verir: real skriptlərdə hazır alətlər rglob və os.walk-dur, amma içəridə onlar da məhz bunu edir.

Rekursiya, yoxsa dövr?

İstənilən rekursiv funksiyanı dövrlə yenidən yazmaq olar (lazım gələrsə, öz stek siyahınla) və əksinə. Hansını seçmək məsələnin quruluşundan asılıdır:

VəziyyətDaha yaxşı seçimSəbəb
sadə ardıcıllıq: 1…n cəmi, faktorial, geri sayımdövrstek yoxdur, dərinlik həddi yoxdur, adətən daha sürətlidir
ağacvari verilənlər: iç-içə siyahılar, qovluqlar, JSON, HTMLrekursiyakod verilənlərin quruluşunu təkrarlayır
«böl və hökm sür»: ikili axtarış, birləşdirmə ilə sıralama, sürətli sıralamarekursiyadərinlik cəmi log₂ n qədərdir
eyni alt məsələlər təkrar-təkrar (Fibonaççi)rekursiya + lru_cache və ya dövrhər qiymət bir dəfə hesablanır
dərinlik minlərlə səviyyəyə çata biləraçıq stekli dövrRecursionError olmur
Python
def sum_rec(n):
    return 0 if n == 0 else n + sum_rec(n - 1)


def sum_loop(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total


print(sum_rec(100), sum_loop(100))
try:
    print(sum_rec(100_000))
except RecursionError:
    print('sum_rec(100000): RecursionError')
print(sum_loop(100_000))
Gözlənilən nəticə
5050 5050
sum_rec(100000): RecursionError
5000050000
Hər rekursiv çağırış bir çərçivə əlavə edir, ona görə sum_rec(100000) 100 000 çərçivə tələb edir və uğursuz olur, dövrə isə heç biri lazım deyil. Python «quyruq» rekursiyasını optimallaşdırmır, ona görə funksiyanı başqa formada yazmaq da kömək etmir.

Tapşırıq

power(x, n) rekursiv funksiyasını yaz: xⁿ = x · xⁿ⁻¹, x⁰ = 1 (n ≥ 0 tam ədəddir). ** operatorundan və pow-dan istifadə etmə. Başlanğıc koddakı üç çağırışı dəyişmə.

Tapşırıq · Python
def power(x, n):
    # base case: n == 0
    # recursive step: x * power(x, n - 1)
    pass


print(power(2, 10))
print(power(3, 4))
print(power(5, 0))
Gözlənilən nəticə
1024
81
1

Tapşırıq

count_files(folder) funksiyası iç-içə lüğətdə faylların sayını qaytarsın: qiyməti lüğət olan açar alt qovluqdur, ədəd olan açar isə fayldır. Boş qovluqda 0 fayl var.

Tapşırıq · Python
tree = {
    'docs': {'cv.pdf': 120, 'letters': {'a.txt': 4, 'b.txt': 6}},
    'music': {},
    'photo.jpg': 900,
}


def count_files(folder):
    # a dict value is a subfolder, a number is a file
    pass


print(count_files(tree))
print(count_files(tree['docs']))
print(count_files(tree['music']))
Gözlənilən nəticə
4
3
0

Yadda saxla

  • Rekursiv funksiya özünü daha kiçik girişlə çağırır; ona baza halı və ona həqiqətən yaxınlaşan addım lazımdır.
  • Hər çağırış çağırış stekində öz çərçivəsini alır; nəticələr çağırışların əks sırası ilə qayıdır.
  • Çatılan baza halı olmadan stek dolur: RecursionError (CPython-da susmaya görə təxminən 1000 səviyyə). return-süz addım None qaytarır.
  • Rekursiya ağacvari verilənlərə və «böl və hökm sür» məsələlərinə yaraşır: iç-içə siyahılar, qovluq ağacları, ikili axtarış.
  • Təkrarlanan alt məsələlər → functools.lru_cache; sadə və ya çox dərin ardıcıllıqlar → dövr.
Dərsdə səhv və ya qeyri-dəqiqlik gördün?

Özünü yoxla

12 sual. Hər düzgün cavab XP qazandırır.

Sual 1 / 12

Sual 1 / 12. Rekursiv funksiyanın iki mütləq hissəsi hansılardır?