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.
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ı).
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(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.
return isə onu yuxarıdan aşağı boşaldır.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: 24Stek 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:
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.
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.
Burada
- F(n)
- n-ci Fibonaççi ədədi
Addım iki həddi geriyə baxdığı üçün iki baza halı lazımdır.
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]
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
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:
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.
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ı.
Boş aralıq
lo > hiolarsa, qiymət yoxdur:-1qaytar (baza halı).Orta element
mid = (lo + hi) // 2;items[mid] == targetolarsa,mid-i qaytar (baza halı).Sağ yarı
items[mid] < targetolarsa,[mid + 1..hi]aralığında axtar.Sol yarı
Əks halda
[lo..mid − 1]aralığında axtar.
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
İnteraktiv
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.
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:
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:
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
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ət | Daha yaxşı seçim | Səbəb |
|---|---|---|
| sadə ardıcıllıq: 1…n cəmi, faktorial, geri sayım | dövr | stek yoxdur, dərinlik həddi yoxdur, adətən daha sürətlidir |
| ağacvari verilənlər: iç-içə siyahılar, qovluqlar, JSON, HTML | rekursiya | kod 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ıralama | rekursiya | də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övr | hər qiymət bir dəfə hesablanır |
| dərinlik minlərlə səviyyəyə çata bilər | açıq stekli dövr | RecursionError olmur |
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
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ə.
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.
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ımNoneqaytarı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.