Rekursiya və çağırış steki

Rekursiya yalnız gözəl yazılış deyil, proqramın icra mexanizmidir: hər çağırış çağırış stekində yeni çərçivə (frame) yaradır. Steki başa düşəndə rekursiyanın vaxtını, yaddaşını və RecursionError-un səbəbini görürsünüz. Bu dərs rekursiyaya giriş mövzusunu təhlil və stek tərəfdən dərinləşdirir.

Üç hissə

• Baza halı — rekursiyanı dayandıran ən sadə hal.
• Rekursiv addım — məsələni özünün daha kiçik versiyası ilə ifadə edir.
• Irəliləyiş — hər çağırış baza halına yaxınlaşmalıdır, yoxsa sonsuz rekursiya olur.

Çağırış stekinin izi

Faktorialın izində hər sətir bir çərçivənin yaranması, hər -> isə onun qiymət qaytarıb silinməsidir. Girinti dərinlikdir: fact(0) dövründə stekdə 4 çərçivə var.

def fact(n, depth=0):
    pad = "  " * depth
    print(f"{pad}fact({n})")
    if n == 0:
        print(f"{pad}-> 1")
        return 1
    result = n * fact(n - 1, depth + 1)
    print(f"{pad}-> {result}")
    return result

fact(3)

fact(3)
  fact(2)
    fact(1)
      fact(0)
      -> 1
    -> 1
  -> 2
-> 6

Stekin ölçüsü və RecursionError

CPython çağırış dərinliyini məhdudlaşdırır: standart limit sys.getrecursionlimit() ilə 1000-dir. Limit aşılanda RecursionError atılır, bu isə proqramı C yığınının dolub çökməsindən qoruyur.

import sys

def depth(n):
    return 0 if n == 0 else 1 + depth(n - 1)