IlmHamroh
Python kursi/Funksiyalar13/14-dars36 daqiqa
Mundarija (21)

7.13-dars: Rekursiya

7-QISM — FUNKSIYALAR · 13-dars

1. Kirish va motivatsiya

Rekursiya — funksiya o'zini chaqiradi:

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

faktorial(5)                    # 120

Ba'zi masalalar rekursiv tabiatan:

python
# Fayl tizimi daraxti
def hajm(yol):
    if yol.is_file():
        return yol.stat().st_size
    return sum(hajm(x) for x in yol.iterdir())

# JSON ichma-ich tuzilmasi
def barglar(d):
    for v in d.values():
        if isinstance(v, dict):
            yield from barglar(v)
        else:
            yield v

Lekin Pythonda rekursiya bilan uch muammo bor:

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

fib(35)                         # ⚠️ ~5 soniya — eksponensial
python
def sanagich(n):
    return 0 if n == 0 else 1 + sanagich(n - 1)

sanagich(2000)                  # ❌ RecursionError
python
def yigindi(r):
    return 0 if not r else r[0] + yigindi(r[1:])     # ⚠️ O(n²) — kesim

Bu darsda:

  • Rekursiyaning ikki qismi: asos va qadam
  • Chuqurlik chegarasi va nega u bor
  • Memoizatsiya — eksponensialdan chiziqliga
  • Rekursiya vs iteratsiya — qachon qaysi biri
  • Quyruqli rekursiya va nega Pythonda yo'q
  • Amaliy naqshlar: daraxtlar, "bo'l va hukmronlik qil", backtracking

2. Nazariya — chuqur tushuntirish

2.1. Ikki qism

Har rekursiv funksiyada ikki narsa bo'lishi shart:

1. Asos holat (base case) — rekursiyani to'xtatadi:

python
def faktorial(n):
    if n <= 1:                  # ⭐ ASOS
        return 1
    return n * faktorial(n - 1)  # ⭐ QADAM

2. Rekursiv qadam — masalani kichraytiradi.

Asos holat yo'q → cheksiz rekursiya:

python
def yomon(n):
    return n * yomon(n - 1)     # ❌ RecursionError

def yomon2(n):
    if n <= 1:
        return 1
    return n * yomon2(n)        # ❌ kichraymaydi

Asos holat yetib bo'lmaydigan:

python
def yomon3(n):
    if n == 0:                  # ⚠️ manfiy son bilan yetib bo'lmaydi
        return 1
    return n * yomon3(n - 1)

yomon3(-1)                      # ❌ RecursionError

Xavfsiz shakl:

python
def faktorial(n):
    if n < 0:
        raise ValueError("manfiy son")
    if n <= 1:
        return 1
    return n * faktorial(n - 1)

2.2. Chuqurlik chegarasi

python
import sys
sys.getrecursionlimit()         # 1000 (sukut)

Amaldagi chegara kamroq — freym stekida joy kerak:

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

sanagich(996)                   # ✅ (taxminan)
sanagich(1000)                  # ❌ RecursionError

Chegarani oshirish:

python
sys.setrecursionlimit(10_000)   # ⚠️ ehtiyot bo'ling

Bu xavfli — haqiqiy chegara C stek hajmi:

RecursionError  →  Python xatosi, ushlash mumkin
Segmentation fault  →  jarayon o'ladi, ushlab bo'lmaydi

Nega chegara bor:

Har funksiya chaqiruvi freym obyekti yaratadi:

python
import sys
def f(): return sys._getframe()
frame = f()
sys.getsizeof(frame)            # ~100-500 bayt

Chegarasiz cheksiz rekursiya butun xotirani yeydi yoki C stekni to'ldiradi (segfault).

Xavfsiz oshirish (threading bilan):

python
import sys, threading

sys.setrecursionlimit(100_000)
threading.stack_size(64 * 1024 * 1024)      # 64 MB stek

def ish():
    chuqur_rekursiya()

t = threading.Thread(target=ish)
t.start()
t.join()

Yaxshiroq — iterativ yechim (2.5-bo'lim).

2.3. Memoizatsiya

Muammo — takroriy hisoblash:

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

fib(5) uchun chaqiruvlar daraxti:

                fib(5)
          /              \
      fib(4)            fib(3)
     /     \           /     \
  fib(3)  fib(2)   fib(2)  fib(1)
  /   \    /   \    /   \
fib(2) fib(1) ...  ...

fib(3) ikki marta, fib(2) uch marta hisoblanadi. Murakkablik — O(2ⁿ).

Yechim — natijalarni eslab qolish:

python
from functools import cache        # Python 3.9+

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

fib(100)                        # bir zumda

Murakkablik: O(2ⁿ) → O(n).

lru_cache — chegara bilan:

python
from functools import lru_cache

@lru_cache(maxsize=128)
def qimmat(x): ...

qimmat.cache_info()             # CacheInfo(hits=..., misses=...)
qimmat.cache_clear()

Talablar:

  • Argumentlar hashlanadigan bo'lishi kerak
  • Funksiya toza bo'lishi kerak (bir xil kirish → bir xil chiqish)
python
@cache
def f(r: list): ...             # ❌ TypeError: unhashable type

@cache
def f(t: tuple): ...            # ✅

Qo'lda memoizatsiya:

python
def fib(n, _kesh={0: 0, 1: 1}):     # ⚠️ o'zgaruvchan sukut (7.3-dars)
    if n not in _kesh:
        _kesh[n] = fib(n - 1) + fib(n - 2)
    return _kesh[n]

Ishlaydi, lekin @cache aniqroq va cache_clear bor.

2.4. Rekursiya vs iteratsiya

Har rekursiv funksiyani sikl bilan yozish mumkin (Church–Turing).

python
# Rekursiv
def faktorial(n):
    return 1 if n <= 1 else n * faktorial(n - 1)

# Iterativ
def faktorial(n):
    natija = 1
    for i in range(2, n + 1):
        natija *= i
    return natija

Solishtirish:

Rekursiya Iteratsiya
Xotira O(chuqurlik) — stek O(1)
Tezlik Sekinroq (freym) Tezroq
Chuqurlik ~1000 Cheksiz
O'qilishi Daraxt/graf uchun Chiziqli uchun
Debug Qiyinroq Osonroq

Qachon rekursiya:

  • Ma'lumot rekursiv tuzilma (daraxt, graf, JSON)
  • "Bo'l va hukmronlik qil" (quicksort, mergesort, binar qidiruv)
  • Backtracking (labirint, N-vazir, sudoku)
  • Chuqurlik kichik va cheklangan

Qachon iteratsiya:

  • Chiziqli o'tish (for x in r)
  • Chuqurlik katta yoki noma'lum
  • Tezlik muhim
  • Oddiy akkumulyatsiya

Tezlik farqi:

python
faktorial_rekursiv(20)          # ~1.8 µs
faktorial_iterativ(20)          # ~1.1 µs
math.factorial(20)              # ~0.1 µs  ⭐ C da

2.5. Rekursiyani iteratsiyaga aylantirish

1. Chiziqli rekursiya → sikl:

python
# Rekursiv
def yigindi(r, i=0):
    return 0 if i >= len(r) else r[i] + yigindi(r, i + 1)

# Iterativ
def yigindi(r):
    natija = 0
    for x in r:
        natija += x
    return natija

2. Daraxt aylanishi → aniq stek:

python
# Rekursiv
def barglar(d):
    for v in d.values():
        if isinstance(v, dict):
            yield from barglar(v)
        else:
            yield v

# Iterativ (stek bilan)
def barglar(d):
    stek = [d]
    while stek:
        joriy = stek.pop()
        if isinstance(joriy, dict):
            stek.extend(joriy.values())
        else:
            yield joriy

Tartib o'zgaradi — stek.pop() oxiridan oladi. Bir xil tartib uchun reversed().

3. Quyruqli rekursiya → sikl:

python
# Quyruqli (natija to'g'ridan-to'g'ri qaytariladi)
def yigindi(r, i=0, jami=0):
    if i >= len(r):
        return jami
    return yigindi(r, i + 1, jami + r[i])       # ⭐ quyruqli chaqiruv

# Sikl
def yigindi(r):
    jami = 0
    for x in r:
        jami += x
    return jami

Python quyruqli rekursiyani optimallashtirmaydi (2.6-bo'lim).

2.6. Quyruqli rekursiya va Python

Quyruqli chaqiruv (tail call) — rekursiv chaqiruv funksiyaning oxirgi amali:

python
def quyruqli(n, akk=1):
    if n <= 1:
        return akk
    return quyruqli(n - 1, akk * n)         # ⭐ quyruqli

def quyruqsiz(n):
    if n <= 1:
        return 1
    return n * quyruqsiz(n - 1)             # ⚠️ ko'paytirish qoladi

Quyruqli rekursiya nazariy jihatdan siklga aylantirilishi mumkin — freym qayta ishlatiladi, stek o'smaydi.

Python buni QILMAYDI:

python
quyruqli(10_000)                # ❌ RecursionError

Guido nima uchun rad etgan (2009, "Tail Recursion Elimination"):

  1. Traceback yo'qoladi — debug qiyinlashadi
  2. Python — funksional til emas — sikl tabiiy
  3. Yashirin optimallashtirish — "Aniq yashirinlikdan yaxshi"
  4. Kutubxona qo'llab-quvvatlashi — barcha amalga oshirish qo'llab-quvvatlashi kerak

"I don't think it's a good idea to try to encourage a Python programming style that relies on tail recursion... Python has excellent looping constructs."

Qaysi tillar qo'llab-quvvatlaydi:

Til Quyruqli optimallashtirish
Scheme, Haskell, Erlang Kafolatlangan
Scala, Kotlin (@tailrec, tailrec)
JavaScript (ES6) Spetsifikatsiyada bor, amalda deyarli yo'q
Python, Java, C#
C, C++, Rust Kompilyator ba'zan qiladi

Amaliy natija: Pythonda quyruqli rekursiya yozishning ma'nosi yo'q — sikl yozing.

2.7. Amaliy naqshlar

1. Daraxt aylanishi:

python
def aylanish(tugun, daraja=0):
    yield tugun, daraja
    for bola in tugun.bolalar:
        yield from aylanish(bola, daraja + 1)

2. "Bo'l va hukmronlik qil":

python
def binar_qidiruv(r, x, chap=0, ong=None):
    ong = len(r) - 1 if ong is None else ong
    if chap > ong:
        return -1
    orta = (chap + ong) // 2
    if r[orta] == x:
        return orta
    if r[orta] < x:
        return binar_qidiruv(r, x, orta + 1, ong)
    return binar_qidiruv(r, x, chap, orta - 1)

3. Backtracking:

python
def permutatsiyalar(r):
    if len(r) <= 1:
        yield r
        return
    for i in range(len(r)):
        for p in permutatsiyalar(r[:i] + r[i+1:]):
            yield [r[i]] + p

4. O'zaro rekursiya:

python
def juftmi(n):
    return True if n == 0 else toqmi(n - 1)

def toqmi(n):
    return False if n == 0 else juftmi(n - 1)

5. Yordamchi funksiya bilan:

python
def yigindi(r):
    """Ochiq API — oddiy imzo."""
    def ichki(i, jami):
        return jami if i >= len(r) else ichki(i + 1, jami + r[i])
    return ichki(0, 0)

Umumiy tuzoqlar:

python
# ❌ Kesim — O(n²)
def yigindi(r):
    return 0 if not r else r[0] + yigindi(r[1:])     # har chaqiruvda nusxa

# ✅ Indeks bilan
def yigindi(r, i=0):
    return 0 if i >= len(r) else r[i] + yigindi(r, i + 1)

# ❌ O'zgaruvchan sukut
def yig(r, natija=[]): ...                          # 7.3-dars tuzog'i

# ✅
def yig(r, natija=None):
    natija = [] if natija is None else natija

3. Tez ma'lumotnoma

Ikki qism

python
def f(n):
    if ASOS_SHART:      ⭐ ASOS — to'xtatadi
        return ASOS_QIYMAT
    return ... f(KICHRAYTIRILGAN)   ⭐ QADAM

⚠️ Asos yo'q yoki kichraymasa → RecursionError

Chuqurlik

python
sys.getrecursionlimit()         1000 (sukut)
sys.setrecursionlimit(n)        ⚠️ segfault xavfi

Xavfsiz oshirish:
  threading.stack_size(64*1024*1024)
  + alohida oqimda ishga tushirish

⭐ Yaxshiroq: iterativ yechim (stek bilan)

Memoizatsiya

python
from functools import cache, lru_cache

@cache                  cheksiz (3.9+)
@lru_cache(maxsize=128) chegara bilan

fib: O(2ⁿ) → O(n)

⚠️ Argumentlar HASHLANADIGAN bo'lsin
⚠️ Funksiya TOZA bo'lsin

Rekursiya vs iteratsiya

Rekursiya:  daraxt, graf, bo'l-va-hukmronlik, backtracking
Iteratsiya: chiziqli, katta chuqurlik, tezlik muhim

Xotira:  O(chuqurlik) vs O(1)
Tezlik:  sekinroq vs tezroq

Quyruqli rekursiya

python
return f(...)           quyruqli chaqiruv

Python OPTIMALLASHTIRMAYDI (Guido ataylab rad etgan)
→ Pythonda quyruqli rekursiya yozishning ma'nosi yo'q

Tuzoqlar

python
f(r[1:])                ❌ O(n²) — kesim nusxa yaratadi
f(r, i+1)               ✅ indeks
def f(r, n=[])          ❌ o'zgaruvchan sukut
@cache + list argument  ❌ unhashable

4. Batafsil misollar

Misol 1 — Asoslar va chuqurlik

python
"""Rekursiyaning ikki qismi va chegaralari."""

import sys
import time

print("=== 1. Asos va qadam ===")


def faktorial(n):
    """✅ To'g'ri rekursiya."""
    if n < 0:
        raise ValueError(f"manfiy son: {n}")
    if n <= 1:                          # ⭐ ASOS
        return 1
    return n * faktorial(n - 1)         # ⭐ QADAM


print(f"  def faktorial(n):")
print(f"      if n <= 1: return 1        ← ASOS")
print(f"      return n * faktorial(n-1)  ← QADAM\n")

for n in [0, 1, 5, 10, 20]:
    print(f"    faktorial({n:>2}) = {faktorial(n):,}")

try:
    faktorial(-1)
except ValueError as e:
    print(f"\n    faktorial(-1) → ❌ {e}")


print("\n=== 2. ⚠️ Noto'g'ri rekursiya ===")


def asossiz(n):
    """❌ Asos holat yo'q."""
    return n * asossiz(n - 1)


def kichraymaydi(n):
    """❌ Argument kichraymaydi."""
    if n <= 1:
        return 1
    return n * kichraymaydi(n)


def yetib_bolmaydi(n):
    """❌ Asos holatga yetib bo'lmaydi."""
    if n == 0:
        return 1
    return n * yetib_bolmaydi(n - 1)


XATOLAR = [
    ("Asos yo'q",           asossiz, 5),
    ("Kichraymaydi",        kichraymaydi, 5),
    ("Asosga yetib bo'lmaydi", yetib_bolmaydi, -1),
]

print(f"  {'Xato turi':<26} {'Natija'}")
print("  " + "─" * 56)
for nom, f, arg in XATOLAR:
    try:
        f(arg)
        natija = "✅ ishladi"
    except RecursionError:
        natija = "❌ RecursionError"
    print(f"  {nom:<26} {natija}")

print(f"\n  ⭐ Uch shart:")
print(f"     1. ASOS holat bor")
print(f"     2. Har qadamda argument KICHRAYADI")
print(f"     3. Asos holatga YETIB BORADI")


print("\n=== 3. Chuqurlik chegarasi ===")


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


print(f"  sys.getrecursionlimit() = {sys.getrecursionlimit()}\n")


def maksimal_chuqurlik():
    """Amaldagi chegarani topadi."""
    chap, ong = 1, sys.getrecursionlimit() * 2
    while chap < ong:
        orta = (chap + ong + 1) // 2
        try:
            sanagich(orta)
            chap = orta
        except RecursionError:
            ong = orta - 1
    return chap


maks = maksimal_chuqurlik()
print(f"  Amaldagi maksimal chuqurlik: {maks}")
print(f"  ⚠️ Chegaradan kam — chunki freymlar joriy stekda ham bor\n")

for n in [100, 500, maks, maks + 1, 2000]:
    try:
        natija = sanagich(n)
        holat = f"✅ {natija}"
    except RecursionError:
        holat = "❌ RecursionError"
    print(f"    sanagich({n:>5}) → {holat}")


print("\n=== 4. Chegarani oshirish ===")

asl_chegara = sys.getrecursionlimit()

print(f"  ⚠️ sys.setrecursionlimit(10_000):")
sys.setrecursionlimit(10_000)
try:
    natija = sanagich(5000)
    print(f"    sanagich(5000) → ✅ {natija}")
except RecursionError:
    print(f"    sanagich(5000) → ❌ RecursionError")

sys.setrecursionlimit(asl_chegara)

print(f"""
  ⚠️ XAVF: haqiqiy chegara — C STEK hajmi.

     RecursionError       → Python xatosi, ushlash mumkin
     Segmentation fault   → jarayon o'ladi, ushlab bo'lmaydi

     sys.setrecursionlimit(1_000_000) → deyarli aniq segfault
""")

print(f"  ✅ Xavfsiz oshirish (alohida oqim + katta stek):")
print(f"""
    import sys, threading

    sys.setrecursionlimit(100_000)
    threading.stack_size(64 * 1024 * 1024)      # 64 MB

    t = threading.Thread(target=chuqur_ish)
    t.start(); t.join()
""")

import threading

natija_konteyner = []


def chuqur_ish():
    try:
        natija_konteyner.append(sanagich(50_000))
    except RecursionError:
        natija_konteyner.append("RecursionError")


sys.setrecursionlimit(100_000)
asl_stek = threading.stack_size()
try:
    threading.stack_size(64 * 1024 * 1024)
    t = threading.Thread(target=chuqur_ish)
    t.start()
    t.join()
    print(f"  Sinov: 64 MB stek bilan sanagich(50_000) → {natija_konteyner[0]}")
except (ValueError, RuntimeError) as e:
    print(f"  Sinov: {e}")
finally:
    threading.stack_size(asl_stek)
    sys.setrecursionlimit(asl_chegara)


print("\n=== 5. Freym stekini ko'rish ===")


def daraja_1():
    return daraja_2()


def daraja_2():
    return daraja_3()


def daraja_3():
    import traceback
    stek = traceback.extract_stack()
    return [q.name for q in stek[-5:]]


print(f"  Chaqiruv zanjiri:")
for i, nom in enumerate(daraja_1(), 1):
    print(f"    {i}. {nom}")

print(f"\n  Freym hajmi:")


def freym_ol():
    return sys._getframe()


f = freym_ol()
print(f"    sys.getsizeof(frame) = {sys.getsizeof(f)} bayt")
print(f"    1000 chuqurlik ≈ {sys.getsizeof(f) * 1000 / 1024:.0f} KB")


print("\n=== 6. Rekursiya chuqurligini kuzatish ===")


def kuzatilgan_faktorial(n, daraja=0):
    otstup = "  " * daraja
    print(f"    {otstup}→ faktorial({n})")
    if n <= 1:
        print(f"    {otstup}← 1  (ASOS)")
        return 1
    natija = n * kuzatilgan_faktorial(n - 1, daraja + 1)
    print(f"    {otstup}← {natija}")
    return natija


print(f"  faktorial(4):\n")
kuzatilgan_faktorial(4)

print(f"\n  ⭐ Rekursiya IKKI yo'nalishda ishlaydi:")
print(f"     → pastga (asosga qadar)")
print(f"     ← yuqoriga (natijalarni birlashtirib)")

Natijaning muhim qismi:

text
=== 2. ⚠️ Noto'g'ri rekursiya ===
  Xato turi                  Natija
  ────────────────────────────────────────────────────────
  Asos yo'q                  ❌ RecursionError
  Kichraymaydi               ❌ RecursionError
  Asosga yetib bo'lmaydi     ❌ RecursionError

=== 3. Chuqurlik chegarasi ===
  sys.getrecursionlimit() = 1000

  Amaldagi maksimal chuqurlik: 997

    sanagich(  100) → ✅ 100
    sanagich(  997) → ✅ 997
    sanagich( 2000) → ❌ RecursionError

=== 6. Rekursiya chuqurligini kuzatish ===
  faktorial(4):

    → faktorial(4)
      → faktorial(3)
        → faktorial(2)
          → faktorial(1)
          ← 1  (ASOS)
        ← 2
      ← 6
    ← 24

Nima ko'rsatdi: 2.1, 2.2-bo'limlar.

Misol 2 — Memoizatsiya

python
"""Eksponensialdan chiziqliga."""

import time
import sys
from functools import cache, lru_cache

print("=== 1. Muammo: takroriy hisoblash ===")

chaqiruvlar = [0]


def fib_sekin(n):
    chaqiruvlar[0] += 1
    return n if n < 2 else fib_sekin(n - 1) + fib_sekin(n - 2)


print(f"  def fib(n): return n if n<2 else fib(n-1) + fib(n-2)\n")
print(f"  {'n':>4} {'Natija':>12} {'Chaqiruvlar':>14} {'Vaqt':>10}")
print("  " + "─" * 46)

for n in [10, 20, 25, 30]:
    chaqiruvlar[0] = 0
    boshlandi = time.perf_counter()
    natija = fib_sekin(n)
    vaqt = time.perf_counter() - boshlandi
    print(f"  {n:>4} {natija:>12,} {chaqiruvlar[0]:>14,} "
          f"{vaqt * 1000:>8.1f} ms")

print(f"\n  ⚠️ Chaqiruvlar soni EKSPONENSIAL o'sadi — O(2ⁿ)")


print("\n=== 2. Chaqiruvlar daraxti ===")


def fib_daraxt(n, daraja=0, kuzatuv=None):
    if kuzatuv is None:
        kuzatuv = []
    kuzatuv.append((daraja, n))
    if n < 2:
        return n, kuzatuv
    a, _ = fib_daraxt(n - 1, daraja + 1, kuzatuv)
    b, _ = fib_daraxt(n - 2, daraja + 1, kuzatuv)
    return a + b, kuzatuv


natija, kuzatuv = fib_daraxt(5)

print(f"  fib(5) chaqiruvlar daraxti:\n")
for daraja, n in kuzatuv[:16]:
    print(f"    {'  ' * daraja}fib({n})")
print(f"    ...")

from collections import Counter
hisob = Counter(n for _, n in kuzatuv)
print(f"\n  Har qiymat necha marta hisoblandi:")
for n in sorted(hisob, reverse=True):
    print(f"    fib({n}) × {hisob[n]}  {'█' * hisob[n]}")

print(f"\n  Jami chaqiruv: {len(kuzatuv)}")


print("\n=== 3. ⭐ @cache bilan ===")


@cache
def fib_kesh(n):
    return n if n < 2 else fib_kesh(n - 1) + fib_kesh(n - 2)


print(f"  @cache")
print(f"  def fib(n): return n if n<2 else fib(n-1) + fib(n-2)\n")

print(f"  {'n':>5} {'Natija':>26} {'Vaqt':>12}")
print("  " + "─" * 48)
for n in [30, 50, 100, 200, 500]:
    boshlandi = time.perf_counter()
    natija = fib_kesh(n)
    vaqt = time.perf_counter() - boshlandi
    korinish = f"{natija:,}" if natija < 10 ** 15 else f"{natija:.3e}"
    print(f"  {n:>5} {korinish:>26} {vaqt * 1_000_000:>9.1f} µs")

print(f"\n  Kesh: {fib_kesh.cache_info()}")

print(f"\n  Solishtirish (n=30):")
chaqiruvlar[0] = 0
boshlandi = time.perf_counter()
fib_sekin(30)
sekin_vaqt = time.perf_counter() - boshlandi
sekin_chaqiruv = chaqiruvlar[0]

fib_kesh.cache_clear()
boshlandi = time.perf_counter()
fib_kesh(30)
kesh_vaqt = time.perf_counter() - boshlandi

print(f"    Keshsiz:  {sekin_chaqiruv:>10,} chaqiruv, "
      f"{sekin_vaqt * 1000:>8.1f} ms")
print(f"    @cache:   {fib_kesh.cache_info().misses:>10,} chaqiruv, "
      f"{kesh_vaqt * 1000:>8.3f} ms")
print(f"    Tezlik:   {sekin_vaqt / kesh_vaqt:>10,.0f}x")

print(f"\n  ⭐ Murakkablik: O(2ⁿ) → O(n)")


print("\n=== 4. @cache vs @lru_cache ===")


@cache
def a(n): return n


@lru_cache(maxsize=None)
def b(n): return n


@lru_cache(maxsize=3)
def c(n): return n


for i in range(6):
    c(i)

print(f"  {'Dekorator':<24} {'maxsize':<10} {'Xatti-harakat'}")
print("  " + "─" * 62)
print(f"  {'@cache':<24} {'None':<10} cheksiz, eng tez (3.9+)")
print(f"  {'@lru_cache(maxsize=None)':<24} {'None':<10} cheksiz")
print(f"  {'@lru_cache(maxsize=128)':<24} {'128':<10} LRU chegara")

print(f"\n  @lru_cache(maxsize=3), 6 ta chaqiruv:")
print(f"    {c.cache_info()}")
print(f"    ⭐ Eng kam ishlatilganlar chiqarildi")

print(f"\n  Metodlar:")
print(f"    cache_info()   → statistika")
print(f"    cache_clear()  → tozalash")
print(f"    __wrapped__    → asl funksiya")

fib_kesh.cache_clear()
print(f"\n  cache_clear() dan keyin: {fib_kesh.cache_info()}")


print("\n=== 5. ⚠️ Kesh talablari ===")


@cache
def hashlanadigan(n: int, t: tuple = ()):
    return n + len(t)


TALABLAR = [
    ("int",             (5,), {}),
    ("tuple",           (5, (1, 2)), {}),
    ("frozenset",       (5, frozenset([1])), {}),
    ("str",             ("abc",), {}),
    ("list",            (5, [1, 2]), {}),
    ("dict",            (5, {"a": 1}), {}),
    ("set",             (5, {1, 2}), {}),
]

print(f"  {'Argument turi':<16} {'Natija'}")
print("  " + "─" * 56)
for nom, args, kwargs in TALABLAR:
    try:
        hashlanadigan(*args, **kwargs)
        natija = "✅ keshlandi"
    except TypeError as e:
        natija = f"❌ {str(e)[:36]}"
    print(f"  {nom:<16} {natija}")

print(f"\n  ✅ Yechim — o'zgarmas turga aylantirish:")
print(f"""
    @cache
    def _ichki(t: tuple): ...

    def ommaviy(r: list):
        return _ichki(tuple(r))
""")


@cache
def _yigindi(t: tuple):
    return sum(t)


def yigindi(r: list):
    return _yigindi(tuple(r))


print(f"    yigindi([1,2,3]) = {yigindi([1, 2, 3])}")
print(f"    yigindi([1,2,3]) = {yigindi([1, 2, 3])}  (keshdan)")
print(f"    {_yigindi.cache_info()}")

print(f"\n  ⚠️ Funksiya TOZA bo'lishi kerak:")


@cache
def notoza(n):
    return n + time.time()          # ⚠️ har safar boshqa


a1 = notoza(1)
time.sleep(0.01)
a2 = notoza(1)
print(f"    notoza(1) ikki marta: {a1 == a2}   ⚠️ kesh eski qiymatni beradi")


print("\n=== 6. Qo'lda memoizatsiya ===")


def fib_qolda(n, _kesh={0: 0, 1: 1}):
    """⚠️ O'zgaruvchan sukut — ataylab."""
    if n not in _kesh:
        _kesh[n] = fib_qolda(n - 1, _kesh) + fib_qolda(n - 2, _kesh)
    return _kesh[n]


def fib_yopilma():
    """✅ Yopilma bilan."""
    kesh = {0: 0, 1: 1}

    def ichki(n):
        if n not in kesh:
            kesh[n] = ichki(n - 1) + ichki(n - 2)
        return kesh[n]

    ichki.kesh = kesh
    ichki.tozala = lambda: (kesh.clear(), kesh.update({0: 0, 1: 1}))
    return ichki


fib_y = fib_yopilma()

USULLAR = [
    ("@cache",              fib_kesh),
    ("O'zgaruvchan sukut",  fib_qolda),
    ("Yopilma",             fib_y),
]

print(f"  {'Usul':<24} {'fib(50)':>18} {'Kesh hajmi':>12}")
print("  " + "─" * 58)
for nom, f in USULLAR:
    natija = f(50)
    if nom == "@cache":
        hajm = f.cache_info().currsize
    elif nom == "Yopilma":
        hajm = len(f.kesh)
    else:
        hajm = len(f.__defaults__[0])
    print(f"  {nom:<24} {natija:>18,} {hajm:>12}")

print(f"\n  ⭐ @cache afzalliklari:")
print(f"     • cache_info(), cache_clear()")
print(f"     • maxsize chegarasi (lru_cache)")
print(f"     • Niyat aniq")
print(f"     • C da yozilgan — tezroq")

import timeit
SOZLASH = "from __main__ import fib_kesh, fib_qolda, fib_y"
print(f"\n  Tezlik (1M chaqiruv, keshdan):")
for nom, kod in [("@cache", "fib_kesh(30)"),
                 ("Sukut", "fib_qolda(30)"),
                 ("Yopilma", "fib_y(30)")]:
    vaqt = timeit.timeit(kod, setup=SOZLASH, number=1_000_000)
    print(f"    {nom:<12} {vaqt:.3f} s")

Natijaning muhim qismi:

text
=== 1. Muammo: takroriy hisoblash ===
     n       Natija    Chaqiruvlar       Vaqt
  ──────────────────────────────────────────────
    10           55            177      0.1 ms
    20        6,765         21,891      5.2 ms
    25       75,025        242,785     54.8 ms
    30      832,040      2,692,537    736.4 ms

=== 3. ⭐ @cache bilan ===
      n                     Natija         Vaqt
  ────────────────────────────────────────────────
     30                    832,040      96.4 µs
    100                  3.542e+20      91.7 µs
    500                 1.394e+104     803.3 µs

  Solishtirish (n=30):
    Keshsiz:   2,692,537 chaqiruv,    645.4 ms
    @cache:           31 chaqiruv,    0.042 ms
    Tezlik:       15,404x

=== 5. ⚠️ Kesh talablari ===
  Argument turi    Natija
  ────────────────────────────────────────────────────────
  int              ✅ keshlandi
  tuple            ✅ keshlandi
  list             ❌ unhashable type: 'list'
  dict             ❌ unhashable type: 'dict'

Nima ko'rsatdi: 2.3-bo'lim.

Misol 3 — Rekursiya vs iteratsiya

python
"""Qachon qaysi biri."""

import sys
import time
import timeit
from collections import deque

print("=== 1. Chiziqli: faktorial ===")


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


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


import math

SOZLASH = "from __main__ import faktorial_rekursiv, faktorial_iterativ\nimport math"

print(f"  faktorial(20):\n")
print(f"  {'Usul':<24} {'Vaqt':>12} {'Nisbat':>9}")
print("  " + "─" * 48)
natijalar = []
for nom, kod in [
    ("Rekursiv", "faktorial_rekursiv(20)"),
    ("Iterativ", "faktorial_iterativ(20)"),
    ("math.factorial", "math.factorial(20)"),
]:
    vaqt = timeit.timeit(kod, setup=SOZLASH, number=200_000)
    natijalar.append((nom, vaqt))

eng_tez = min(v for _, v in natijalar)
for nom, vaqt in natijalar:
    print(f"  {nom:<24} {vaqt:>10.3f} s {vaqt / eng_tez:>8.1f}x")

print(f"\n  Chuqurlik chegarasi:")
for n in [900, 1500]:
    try:
        faktorial_rekursiv(n)
        r = "✅"
    except RecursionError:
        r = "❌ RecursionError"
    faktorial_iterativ(n)
    print(f"    n={n:<6} rekursiv: {r:<22} iterativ: ✅")

print(f"\n  ⭐ Chiziqli masalada — ITERATSIYA")


print("\n=== 2. Daraxt: rekursiya tabiiy ===")

DARAXT = {
    "loyiha": {
        "src": {
            "main.py": 1200,
            "utils": {"helper.py": 800, "config.py": 400},
        },
        "testlar": {"test_main.py": 600},
        "README.md": 3100,
    }
}


def hajm_rekursiv(tugun):
    """✅ Tabiiy va qisqa."""
    if isinstance(tugun, int):
        return tugun
    return sum(hajm_rekursiv(v) for v in tugun.values())


def hajm_iterativ(tugun):
    """⚠️ Stek bilan — uzunroq."""
    jami = 0
    stek = [tugun]
    while stek:
        joriy = stek.pop()
        if isinstance(joriy, int):
            jami += joriy
        else:
            stek.extend(joriy.values())
    return jami


print(f"  Fayl daraxti hajmi:\n")
print(f"    Rekursiv: {hajm_rekursiv(DARAXT):,} bayt")
print(f"    Iterativ: {hajm_iterativ(DARAXT):,} bayt")

print(f"\n  Kod uzunligi:")
import inspect
for f in [hajm_rekursiv, hajm_iterativ]:
    qatorlar = len([q for q in inspect.getsource(f).splitlines()
                    if q.strip() and not q.strip().startswith(('"""', "#"))])
    print(f"    {f.__name__:<20} {qatorlar} qator")

print(f"\n  ⭐ Daraxt uchun — REKURSIYA (qisqaroq va aniqroq)")


print("\n=== 3. Daraxtni chizish ===")


def chiz(tugun, prefiks="", nom="/"):
    """Rekursiv — daraxt tuzilishi tabiiy."""
    if isinstance(tugun, int):
        print(f"    {prefiks}{nom}  ({tugun:,} B)")
        return
    print(f"    {prefiks}{nom}")
    elementlar = list(tugun.items())
    for i, (k, v) in enumerate(elementlar):
        oxirgi = i == len(elementlar) - 1
        belgi = "└── " if oxirgi else "├── "
        yangi_prefiks = prefiks + ("    " if oxirgi else "│   ")
        if isinstance(v, dict):
            print(f"    {prefiks}{belgi}{k}/")
            chiz_ichki(v, yangi_prefiks)
        else:
            print(f"    {prefiks}{belgi}{k}  ({v:,} B)")


def chiz_ichki(tugun, prefiks):
    elementlar = list(tugun.items())
    for i, (k, v) in enumerate(elementlar):
        oxirgi = i == len(elementlar) - 1
        belgi = "└── " if oxirgi else "├── "
        if isinstance(v, dict):
            print(f"    {prefiks}{belgi}{k}/")
            chiz_ichki(v, prefiks + ("    " if oxirgi else "│   "))
        else:
            print(f"    {prefiks}{belgi}{k}  ({v:,} B)")


print(f"  Fayl daraxti:\n")
chiz_ichki(DARAXT, "")


print("\n=== 4. Aylanish tartibi ===")

ICHMA_ICH = {"a": {"b": 1, "c": {"d": 2, "e": 3}}, "f": 4}


def barglar_rekursiv(d):
    for k, v in d.items():
        if isinstance(v, dict):
            yield from barglar_rekursiv(v)
        else:
            yield k, v


def barglar_stek(d):
    stek = [d]
    while stek:
        joriy = stek.pop()
        if isinstance(joriy, dict):
            stek.extend(joriy.items())
        elif isinstance(joriy, tuple):
            k, v = joriy
            if isinstance(v, dict):
                stek.extend(v.items())
            else:
                yield k, v


def barglar_navbat(d):
    navbat = deque([d])
    while navbat:
        joriy = navbat.popleft()
        if isinstance(joriy, dict):
            navbat.extend(joriy.items())
        elif isinstance(joriy, tuple):
            k, v = joriy
            if isinstance(v, dict):
                navbat.extend(v.items())
            else:
                yield k, v


print(f"  Ma'lumot: {ICHMA_ICH}\n")
print(f"  {'Usul':<24} {'Natija'}")
print("  " + "─" * 56)
for nom, f in [("Rekursiv (DFS)", barglar_rekursiv),
               ("Stek (DFS, teskari)", barglar_stek),
               ("Navbat (BFS)", barglar_navbat)]:
    print(f"  {nom:<24} {list(f(ICHMA_ICH))}")

print(f"""
  ⭐ Rekursiv — chuqurlik bo'yicha (DFS), tabiiy tartib
     Stek — DFS, lekin TESKARI tartib
     Navbat — kenglik bo'yicha (BFS)
""")


print("\n=== 5. Chuqur tuzilma ===")


def chuqur_yarat(n):
    d = {"qiymat": "eng chuqur"}
    for _ in range(n):
        d = {"daraja": d}
    return d


def chuqurlik_rekursiv(d, n=0):
    if not isinstance(d, dict):
        return n
    return max((chuqurlik_rekursiv(v, n + 1) for v in d.values()), default=n)


def chuqurlik_iterativ(d):
    maks = 0
    stek = [(d, 0)]
    while stek:
        joriy, daraja = stek.pop()
        maks = max(maks, daraja)
        if isinstance(joriy, dict):
            stek.extend((v, daraja + 1) for v in joriy.values())
    return maks


print(f"  {'Chuqurlik':>10} {'Rekursiv':<22} {'Iterativ'}")
print("  " + "─" * 50)
for n in [100, 500, 2000, 10_000]:
    d = chuqur_yarat(n)
    try:
        r = f"✅ {chuqurlik_rekursiv(d)}"
    except RecursionError:
        r = "❌ RecursionError"
    i = f"✅ {chuqurlik_iterativ(d)}"
    print(f"  {n:>10} {r:<22} {i}")

print(f"\n  ⚠️ Nega 500 da yiqildi, limit esa 1000?")
print(f"     max(... for v in d.values()) — generator ifodasi. U ham")
print(f"     o'z FREYMIGA ega, shuning uchun har daraja 2 freym oladi:")
print(f"     500 daraja ≈ 1000 freym → RecursionError.")
print(f"\n  ⭐ Chuqurlik noma'lum bo'lsa — ITERATIV")


print("\n=== 6. Xotira ===")


def stek_chuqurligi():
    """Joriy stek chuqurligini qaytaradi."""
    n = 0
    f = sys._getframe()
    while f:
        n += 1
        f = f.f_back
    return n


def olchash(n):
    if n == 0:
        return stek_chuqurligi()
    return olchash(n - 1)


print(f"  Rekursiya chuqurligi va stek:\n")
print(f"    {'Chuqurlik':>10} {'Stek freymlari':>16}")
print("    " + "─" * 30)
for n in [0, 10, 100, 500]:
    print(f"    {n:>10} {olchash(n):>16}")

freym = sys._getframe()
print(f"\n  Bir freym: ~{sys.getsizeof(freym)} bayt")
print(f"  1000 chuqurlik ≈ {sys.getsizeof(freym) * 1000 / 1024:.0f} KB")

print(f"\n  Iterativ (stek bilan):")
print(f"    Ro'yxat elementi: ~8 bayt (ko'rsatkich)")
print(f"    1000 element ≈ 8 KB")
print(f"    ⭐ ~{sys.getsizeof(freym) / 8:.0f}x kam xotira")


print("\n=== 7. Qaror jadvali ===")

print("""
  ┌────────────────────────────┬──────────────────────────────────┐
  │ Vazifa                     │ Tanlov                           │
  ├────────────────────────────┼──────────────────────────────────┤
  │ Chiziqli o'tish            │ Iteratsiya ⭐                     │
  │ Akkumulyatsiya (sum, max)  │ Tayyor funksiya ⭐                │
  │ Daraxt / graf              │ Rekursiya ⭐                      │
  │ JSON / ichma-ich tuzilma   │ Rekursiya ⭐                      │
  │ Bo'l va hukmronlik qil     │ Rekursiya ⭐                      │
  │ Backtracking               │ Rekursiya ⭐                      │
  │ Chuqurlik > 1000           │ Iteratsiya (stek) ⭐              │
  │ Chuqurlik noma'lum         │ Iteratsiya ⭐                     │
  │ Tezlik kritik              │ Iteratsiya                       │
  │ Takroriy hisoblash         │ Rekursiya + @cache ⭐             │
  └────────────────────────────┴──────────────────────────────────┘
""")

Natijaning muhim qismi:

text
=== 1. Chiziqli: faktorial ===
  faktorial(20):

  Usul                             Vaqt    Nisbat
  ────────────────────────────────────────────────
  Rekursiv                      0.516 s      9.6x
  Iterativ                      0.363 s      6.8x
  math.factorial                0.054 s      1.0x

  Chuqurlik chegarasi:
    n=900    rekursiv: ✅                     iterativ: ✅
    n=1500   rekursiv: ❌ RecursionError      iterativ: ✅

=== 5. Chuqur tuzilma ===
   Chuqurlik Rekursiv               Iterativ
  ──────────────────────────────────────────────────
         100 ✅ 101                 ✅ 101
         100 ✅ 101                  ✅ 101
        2000 ❌ RecursionError      ✅ 2001
       10000 ❌ RecursionError       ✅ 10001

=== 6. Xotira ===
  Bir freym: ~264 bayt
  1000 chuqurlik ≈ 258 KB
    1000 element ≈ 8 KB
    ⭐ ~33x kam xotira

Nima ko'rsatdi: 2.4, 2.5-bo'limlar.

Misol 4 — Amaliy: klassik algoritmlar

python
"""Rekursiya tabiiy bo'lgan masalalar."""

import time
from functools import cache

print("=== 1. Bo'l va hukmronlik qil ===")


def binar_qidiruv(r, x, chap=0, ong=None):
    """O(log n) — har qadamda yarmini tashlaydi."""
    ong = len(r) - 1 if ong is None else ong
    if chap > ong:
        return -1
    orta = (chap + ong) // 2
    if r[orta] == x:
        return orta
    if r[orta] < x:
        return binar_qidiruv(r, x, orta + 1, ong)
    return binar_qidiruv(r, x, chap, orta - 1)


def merge_sort(r):
    """O(n log n) — bo'lish va birlashtirish."""
    if len(r) <= 1:
        return r
    orta = len(r) // 2
    chap = merge_sort(r[:orta])
    ong = merge_sort(r[orta:])
    return birlashtir(chap, ong)


def birlashtir(a, b):
    natija = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            natija.append(a[i]); i += 1
        else:
            natija.append(b[j]); j += 1
    natija.extend(a[i:])
    natija.extend(b[j:])
    return natija


def quick_sort(r):
    """O(n log n) o'rtacha."""
    if len(r) <= 1:
        return r
    tayanch = r[len(r) // 2]
    kichik = [x for x in r if x < tayanch]
    teng = [x for x in r if x == tayanch]
    katta = [x for x in r if x > tayanch]
    return quick_sort(kichik) + teng + quick_sort(katta)


import random
random.seed(1)

SARALANGAN = list(range(0, 100, 3))
TASODIFIY = [random.randrange(100) for _ in range(15)]

print(f"  Binar qidiruv (saralangan: {SARALANGAN[:8]}...):\n")
for x in [0, 33, 99, 50]:
    joy = binar_qidiruv(SARALANGAN, x)
    holat = f"indeks {joy}" if joy >= 0 else "topilmadi"
    print(f"    qidir({x:>3}) → {holat}")

print(f"\n  Saralash:")
print(f"    Asl:        {TASODIFIY}")
print(f"    merge_sort: {merge_sort(TASODIFIY)}")
print(f"    quick_sort: {quick_sort(TASODIFIY)}")
print(f"    sorted():   {sorted(TASODIFIY)}")

import timeit
KATTA = [random.randrange(10_000) for _ in range(2000)]
SOZLASH = f"from __main__ import merge_sort, quick_sort\nr = {KATTA!r}"
print(f"\n  Tezlik ({len(KATTA):,} element):")
for nom, kod in [("merge_sort", "merge_sort(r)"),
                 ("quick_sort", "quick_sort(r)"),
                 ("sorted (Timsort)", "sorted(r)")]:
    vaqt = timeit.timeit(kod, setup=SOZLASH, number=20)
    print(f"    {nom:<20} {vaqt * 1000 / 20:>8.2f} ms")

print(f"\n  ⭐ sorted() — C da yozilgan Timsort, har doim tezroq")


print("\n\n=== 2. Backtracking: N-vazir ===")


def n_vazir(n):
    """N ta vazirni shohmot taxtasiga joylashtirish."""
    yechimlar = []

    def xavfsizmi(joylashuv, qator, ustun):
        for q, u in enumerate(joylashuv):
            if u == ustun or abs(q - qator) == abs(u - ustun):
                return False
        return True

    def joylashtir(joylashuv):
        qator = len(joylashuv)
        if qator == n:
            yechimlar.append(list(joylashuv))
            return
        for ustun in range(n):
            if xavfsizmi(joylashuv, qator, ustun):
                joylashuv.append(ustun)
                joylashtir(joylashuv)       # ⭐ rekursiya
                joylashuv.pop()             # ⭐ backtrack

    joylashtir([])
    return yechimlar


for n in [4, 5, 6, 8]:
    boshlandi = time.perf_counter()
    yechimlar = n_vazir(n)
    vaqt = time.perf_counter() - boshlandi
    print(f"  {n}×{n} taxta: {len(yechimlar):>3} yechim  "
          f"({vaqt * 1000:>7.1f} ms)")

print(f"\n  4×4 birinchi yechim:")
yechim = n_vazir(4)[0]
for qator, ustun in enumerate(yechim):
    taxta = "".join("♛ " if u == ustun else "· " for u in range(4))
    print(f"    {taxta}")


print("\n\n=== 3. Permutatsiyalar va kombinatsiyalar ===")


def permutatsiyalar(r):
    """Barcha tartiblanishlar."""
    if len(r) <= 1:
        yield list(r)
        return
    for i in range(len(r)):
        for p in permutatsiyalar(r[:i] + r[i + 1:]):
            yield [r[i]] + p


def kombinatsiyalar(r, k):
    """k elementli barcha to'plamlar."""
    if k == 0:
        yield []
        return
    if len(r) < k:
        return
    for kombinatsiya in kombinatsiyalar(r[1:], k - 1):
        yield [r[0]] + kombinatsiya
    yield from kombinatsiyalar(r[1:], k)


def barcha_qism_toplamlar(r):
    """2ⁿ ta qism to'plam."""
    if not r:
        yield []
        return
    for qism in barcha_qism_toplamlar(r[1:]):
        yield qism
        yield [r[0]] + qism


R = ["a", "b", "c"]

print(f"  Elementlar: {R}\n")
print(f"  Permutatsiyalar ({len(list(permutatsiyalar(R)))}):")
print(f"    {[''.join(p) for p in permutatsiyalar(R)]}")

print(f"\n  2 elementli kombinatsiyalar:")
print(f"    {[''.join(k) for k in kombinatsiyalar(R, 2)]}")

print(f"\n  Barcha qism to'plamlar ({2 ** len(R)}):")
print(f"    {[''.join(q) or '∅' for q in barcha_qism_toplamlar(R)]}")

print(f"\n  ⭐ itertools bilan solishtiring:")
from itertools import permutations, combinations, chain
print(f"    permutations(r)        → {[''.join(p) for p in permutations(R)]}")
print(f"    combinations(r, 2)     → {[''.join(k) for k in combinations(R, 2)]}")
qism_toplamlar = chain.from_iterable(
    combinations(R, k) for k in range(len(R) + 1)
)
print(f"    chain(combinations...) → "
      f"{[''.join(q) or '∅' for q in qism_toplamlar]}")
print(f"    ⭐ itertools — C da yozilgan, tezroq")


print("\n\n=== 4. Dinamik dasturlash ===")


@cache
def tanga_almashtirish(summa, tangalar):
    """Minimal tangalar soni."""
    if summa == 0:
        return 0
    if summa < 0:
        return float("inf")
    return min(
        (1 + tanga_almashtirish(summa - t, tangalar) for t in tangalar),
        default=float("inf"),
    )


@cache
def zinapoya(n):
    """n zinaga chiqish usullari (1 yoki 2 qadam)."""
    if n <= 2:
        return max(n, 1)
    return zinapoya(n - 1) + zinapoya(n - 2)


@cache
def levenshtein(a: str, b: str) -> int:
    """Ikki satr orasidagi tahrirlash masofasi."""
    if not a:
        return len(b)
    if not b:
        return len(a)
    if a[0] == b[0]:
        return levenshtein(a[1:], b[1:])
    return 1 + min(
        levenshtein(a[1:], b),          # o'chirish
        levenshtein(a, b[1:]),          # qo'shish
        levenshtein(a[1:], b[1:]),      # almashtirish
    )


TANGALAR = (1, 5, 10, 25)

print(f"  Tanga almashtirish (tangalar: {TANGALAR}):")
for summa in [30, 63, 99]:
    n = tanga_almashtirish(summa, TANGALAR)
    print(f"    {summa:>3} → {n} ta tanga")

print(f"\n  Zinapoya (1 yoki 2 qadam):")
for n in [3, 5, 10, 50]:
    print(f"    {n:>3} zina → {zinapoya(n):,} usul")

print(f"\n  Levenshtein masofasi:")
JUFTLIKLAR = [
    ("kitten", "sitting"),
    ("salom", "kalom"),
    ("python", "python"),
    ("abc", "xyz"),
]
for a, b in JUFTLIKLAR:
    print(f"    {a!r:<10} ↔ {b!r:<10} = {levenshtein(a, b)}")

print(f"\n  Kesh statistikasi:")
for f in [tanga_almashtirish, zinapoya, levenshtein]:
    print(f"    {f.__name__:<20} {f.cache_info()}")

print(f"""
  ⭐ Dinamik dasturlash = rekursiya + memoizatsiya
     • Masala kichik qism masalalarga bo'linadi
     • Qism masalalar TAKRORLANADI
     • @cache eksponensialni polinomialga aylantiradi
""")


print("\n=== 5. Xanoy minoralari ===")


def xanoy(n, manba="A", maqsad="C", yordamchi="B", qadamlar=None):
    """Klassik rekursiv masala."""
    if qadamlar is None:
        qadamlar = []
    if n == 1:
        qadamlar.append((manba, maqsad))
        return qadamlar
    xanoy(n - 1, manba, yordamchi, maqsad, qadamlar)
    qadamlar.append((manba, maqsad))
    xanoy(n - 1, yordamchi, maqsad, manba, qadamlar)
    return qadamlar


print(f"  {'Disklar':>8} {'Qadamlar':>10} {'Formula (2ⁿ-1)':>16}")
print("  " + "─" * 38)
for n in range(1, 8):
    qadamlar = xanoy(n)
    print(f"  {n:>8} {len(qadamlar):>10} {2 ** n - 1:>16}")

print(f"\n  3 disk uchun qadamlar:")
for i, (a, b) in enumerate(xanoy(3), 1):
    print(f"    {i}. {a} → {b}")

print(f"""
  ⭐ Xanoy — rekursiyaning klassik namunasi:
     n diskni ko'chirish = (n-1) ni ko'chirish
                         + eng kattasini ko'chirish
                         + (n-1) ni qaytarish
""")


print("\n=== 6. Rekursiya tuzoqlari ===")

print(f"  ❌ Kesim bilan — O(n²):\n")


def yigindi_kesim(r):
    return 0 if not r else r[0] + yigindi_kesim(r[1:])


def yigindi_indeks(r, i=0):
    return 0 if i >= len(r) else r[i] + yigindi_indeks(r, i + 1)


R = list(range(500))
SOZLASH = f"from __main__ import yigindi_kesim, yigindi_indeks\nr = {R!r}"

for nom, kod in [("r[1:] bilan (O(n²))", "yigindi_kesim(r)"),
                 ("indeks bilan (O(n))", "yigindi_indeks(r)"),
                 ("sum(r)", "sum(r)")]:
    vaqt = timeit.timeit(kod, setup=SOZLASH, number=1000)
    print(f"    {nom:<24} {vaqt * 1000 / 1000:>8.3f} ms")

print(f"""
  ⚠️ r[1:] har chaqiruvda YANGI ro'yxat yaratadi:
     n + (n-1) + (n-2) + ... = O(n²) xotira va vaqt

  ✅ Indeks bilan — nusxa yo'q
  ⭐ Eng yaxshisi — sum(r)
""")

print(f"  ❌ O'zgaruvchan sukut:\n")


def yig_yomon(r, natija=[]):
    """⚠️ 7.3-dars tuzog'i."""
    for x in r:
        natija.append(x)
    return natija


def yig_yaxshi(r, natija=None):
    natija = [] if natija is None else natija
    for x in r:
        natija.append(x)
    return natija


print(f"    yig_yomon([1,2])  → {yig_yomon([1, 2])}")
print(f"    yig_yomon([3,4])  → {yig_yomon([3, 4])}   ⚠️ oldingi qoldi")
print(f"    yig_yaxshi([1,2]) → {yig_yaxshi([1, 2])}")
print(f"    yig_yaxshi([3,4]) → {yig_yaxshi([3, 4])}   ✅")

Natijaning muhim qismi:

text
=== 2. Backtracking: N-vazir ===
  4×4 taxta:   2 yechim  (    0.1 ms)
  5×5 taxta:  10 yechim  (    0.2 ms)
  6×6 taxta:   4 yechim  (    0.7 ms)
  8×8 taxta:  92 yechim  (   16.2 ms)

  4×4 birinchi yechim:
    · ♛ · ·
    · · · ♛
    ♛ · · ·
    · · ♛ ·

=== 4. Dinamik dasturlash ===
  Levenshtein masofasi:
    'kitten'   ↔ 'sitting'  = 3
    'salom'    ↔ 'kalom'    = 1
    'python'   ↔ 'python'   = 0
    'abc'      ↔ 'xyz'      = 3

=== 6. Rekursiya tuzoqlari ===
    r[1:] bilan (O(n²))         1.357 ms
    indeks bilan (O(n))         0.157 ms
    sum(r)                      0.004 ms

Nima ko'rsatdi: 2.3, 2.7-bo'limlar.

5. To'g'ri va noto'g'ri tushunishlar

Noto'g'ri fikr To'g'risi
"Rekursiya har doim chiroyliroq" Chiziqli masalada sikl aniqroq
"Chuqurlik chegarasi 1000" Amalda ~990 — joriy stek ham hisoblanadi
"setrecursionlimit xavfsiz" Katta qiymat → segfault
"Python quyruqli rekursiyani optimallashtiradi" Ataylab qilmaydi
"@cache har doim ishlatilishi mumkin" Argumentlar hashlanadigan, funksiya toza bo'lsin
"Rekursiya sekin — ishlatmang" Daraxt/graf uchun tabiiy va to'g'ri
"r[1:] bilan rekursiya normal" O(n²) — indeks ishlating
"Rekursiv fib normal" O(2ⁿ) — @cache shart
"Iterativ har doim tezroq" Bir xil algoritm uchun — ha, lekin kod uzunroq

6. Keng tarqalgan xatolar va yechimlari

1. Asos holat yo'q

python
def f(n): return n * f(n-1)         # ❌ RecursionError
def f(n):
    if n <= 1: return 1             # ✅
    return n * f(n-1)

2. Argument kichraymaydi

python
return f(n)                         # ❌
return f(n - 1)                     # ✅

3. Asosga yetib bo'lmaydi

python
if n == 0: return 1                 # ⚠️ manfiy son bilan
if n <= 0: return 1                 # ✅

4. Kesim bilan

python
f(r[1:])                            # ❌ O(n²)
f(r, i + 1)                         # ✅

5. Memoizatsiya yo'q

python
def fib(n): return fib(n-1)+fib(n-2)    # ❌ O(2ⁿ)

@cache                                   # ✅ O(n)
def fib(n): ...

6. @cache + o'zgaruvchan argument

python
@cache
def f(r: list): ...                 # ❌ unhashable

@cache
def _f(t: tuple): ...               # ✅
def f(r): return _f(tuple(r))

7. O'zgaruvchan sukut

python
def f(r, natija=[]): ...            # ❌ 7.3-dars tuzog'i
def f(r, natija=None): ...          # ✅

8. Chuqur tuzilma uchun rekursiya

python
def yur(d): ...                     # ⚠️ 1000 daraja chegara
def yur_iterativ(d):                # ✅ stek bilan
    stek = [d]

7. Integratsiya — bu bilim qayerda kerak bo'ladi

  • 7.1-dars (o'tilgan): funksiya asoslari
  • 7.3-dars (o'tilgan): o'zgaruvchan sukut tuzog'i
  • 6.14-dars (o'tilgan): ichma-ich tuzilmalar, rekursiv aylanish
  • 6.17-dars (o'tilgan): generatorlar, yield from
  • 10-qism: functools.cache, dinamik dasturlash
  • 15-qism: sys.setrecursionlimit, threading.stack_size
  • Algoritmlar: saralash, qidiruv, graf, DP

8. Eng yaxshi amaliyotlar

  1. Asos holat birinchi qatorlarda. Va u yetib boradigan bo'lsin.

  2. Takroriy hisoblash bo'lsa — @cache. O(2ⁿ) → O(n).

  3. Kesim o'rniga indeks. f(r, i+1), f(r[1:]) emas.

  4. Chuqurlik noma'lum bo'lsa — iterativ. Stek yoki navbat bilan.

  5. Chiziqli masalada sikl. Rekursiya daraxt/graf uchun.

  6. setrecursionlimit dan qoching. Segfault xavfi.

  7. Quyruqli rekursiya yozmang. Python uni optimallashtirmaydi.

  8. itertools ni tekshiring. permutations, combinations — tayyor va tezroq.

9. Amaliy topshiriq

Vazifa 1: Natijani bashorat qiling

python
1.  def f(n): return 1 if n <= 1 else n * f(n-1)
    print(f(5))
2.  def g(n): return n * g(n-1)
    g(5)
3.  import sys; print(sys.getrecursionlimit())
4.  def h(n): return 0 if n == 0 else 1 + h(n-1)
    h(2000)
5.  from functools import cache
    @cache
    def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)
    print(fib(50))
6.  @cache
    def k(r: list): return sum(r)
    k([1, 2])
7.  def m(r): return 0 if not r else r[0] + m(r[1:])
    print(m([1,2,3]))
8.  def p(n, akk=1): return akk if n <= 1 else p(n-1, akk*n)
    print(p(5))
9.  def q(n): return q(n)
    q(1)
10. def s(r, i=0): return 0 if i >= len(r) else r[i] + s(r, i+1)
    print(s([1,2,3]))
11. def juft(n): return True if n == 0 else toq(n-1)
    def toq(n): return False if n == 0 else juft(n-1)
    print(juft(10))
12. fib.cache_clear(); print(fib.cache_info().currsize)
Javoblar
  1. 120
  2. RecursionError — asos yo'q
  3. 1000
  4. RecursionError
  5. 12586269025
  6. TypeError: unhashable type: 'list'
  7. 6 — ishlaydi, lekin O(n²)
  8. 120 — quyruqli, lekin optimallashtirilmaydi
  9. RecursionError — kichraymaydi
  10. 6
  11. True
  12. 0

Vazifa 2: Xatolarni tuzating

python
1.  def f(n): return n * f(n-1)
2.  def f(n):
        if n == 0: return 1
        return n * f(n-1)       # f(-1) bilan
3.  def fib(n): return n if n<2 else fib(n-1)+fib(n-2)
4.  def yig(r): return 0 if not r else r[0] + yig(r[1:])
5.  @cache
    def f(r: list): return sum(r)
6.  def f(r, natija=[]): natija.append(r); return natija
7.  sys.setrecursionlimit(1_000_000)
8.  def chuqurlik(d):     # 10000 darajali tuzilma
        return 1 + max(chuqurlik(v) for v in d.values())
Javoblar
python
1.  if n <= 1: return 1  qo'shing
2.  if n <= 0: return 1
3.  @cache qo'shing
4.  def yig(r, i=0): return 0 if i >= len(r) else r[i] + yig(r, i+1)
5.  @cache def _f(t: tuple); def f(r): return _f(tuple(r))
6.  def f(r, natija=None): natija = [] if natija is None else natija
7.  threading.stack_size() bilan alohida oqim, yoki iterativ
8.  Iterativ (stek bilan) yozing

Vazifa 3: Rekursiv vositalar

Yozing (har biri uchun iterativ versiya ham):

  1. chuqurlik(d) — ichma-ich tuzilma chuqurligi
  2. tekisla(r) — ichma-ich ro'yxatni tekislash
  3. barglar(d) — barcha barg qiymatlar
  4. yol_topish(d, kalit) — kalitgacha yo'l
  5. hisobla(d) — barcha son qiymatlar yig'indisi
  6. Aylanma havoladan himoya (id() to'plami)
  7. Chuqurlik chegarasi (max_daraja)

Vazifa 4: Memoizatsiya tadqiqoti

  1. fib ni 4 xil yozing: sodda, @cache, qo'lda, iterativ
  2. Har biri uchun: vaqt, chaqiruvlar soni, xotira
  3. n ga bog'liqlik grafigi
  4. @lru_cache(maxsize) — turli hajmlarda
  5. Kesh samaradorligi (hit rate)
  6. Qachon memoizatsiya foydali emas

Vazifa 5: Klassik algoritmlar

Rekursiv yozing va itertools/standart kutubxona bilan solishtiring:

  1. permutatsiyalar(r), kombinatsiyalar(r, k)
  2. qism_toplamlar(r)
  3. merge_sort, quick_sort
  4. binar_qidiruv
  5. xanoy(n)
  6. Har biri uchun tezlik va murakkablik

Vazifa 6: Dinamik dasturlash

@cache bilan yeching:

  1. Tanga almashtirish (minimal soni va usullar soni)
  2. Ryukzak masalasi (knapsack)
  3. Eng uzun umumiy ketma-ketlik (LCS)
  4. Levenshtein masofasi (+ tahrirlash qadamlari)
  5. Zinapoya (n qadam bilan)
  6. Har biri uchun keshsiz versiya bilan solishtiring

Vazifa 7: O'ylash

Nega Python quyruqli rekursiyani optimallashtirmaydi, garchi bu texnik jihatdan mumkin bo'lsa ham?

Javob

Guido to'rt sabab keltirgan (2009, "Tail Recursion Elimination").

1. Traceback yo'qoladi.

Quyruqli optimallashtirish freym'ni qayta ishlatadi. Ya'ni:

python
def a(): return b()
def b(): return c()
def c(): raise ValueError("xato")

a()

Optimallashtirish bilan traceback:

File "x.py", line 3, in c
    raise ValueError("xato")

Optimallashtirishsiz:

File "x.py", line 5, in <module>
    a()
File "x.py", line 1, in a
    return b()
File "x.py", line 2, in b
    return c()
File "x.py", line 3, in c
    raise ValueError("xato")

Ikkinchisi ancha foydali. Guido:

"Also, tail recursion elimination makes stack traces less useful."

Python — debug qulayligiga katta e'tibor beradigan til.

2. Python funksional til emas.

Quyruqli rekursiya — Scheme, Haskell, Erlang uchun asosiy vosita, chunki u yerda sikl yo'q:

scheme
(define (loop n)
  (if (= n 0) 'done (loop (- n 1))))

Pythonda esa sikl bor va u tabiiyroq:

python
for i in range(n): ...
while shart: ...

Guido:

"I don't think it's a good idea to try to encourage a Python programming style that relies on tail recursion... Python has excellent looping constructs."

3. Yashirin optimallashtirish.

Zen: "Explicit is better than implicit."

Quyruqli optimallashtirish — jimgina xatti-harakat o'zgarishi:

python
def f(n):
    return f(n - 1)         # optimallashtirish BOR → cheksiz sikl
                            # optimallashtirish YO'Q → RecursionError

RecursionError — foydali signal: "algoritmingizda xato bor". Uni yo'qotish xatolarni yashiradi.

4. Barcha amalga oshirish qo'llab-quvvatlashi kerak.

Agar CPython buni qilsa, PyPy, Jython, IronPython, MicroPython ham qilishi kerak. Aks holda kod ba'zi amalga oshirishlarda ishlaydi, ba'zilarida yo'q.

Bu — til spetsifikatsiyasiga jiddiy qo'shimcha.

Texnik nozikliklar:

Pythonda quyruqli chaqiruvni aniqlash oson emas:

python
def f(n):
    return f(n - 1)         # quyruqli?

Ha, lekin:

python
def f(n):
    try:
        return f(n - 1)     # ❌ quyruqli EMAS — finally bo'lishi mumkin
    finally:
        tozalash()
python
def f(n):
    with ochiq_fayl():
        return f(n - 1)     # ❌ __exit__ chaqirilishi kerak
python
class A:
    def f(self, n):
        return self.f(n-1)  # ⚠️ self.f dinamik — boshqa funksiya bo'lishi mumkin

Oxirgi holat ayniqsa muhim: Pythonda self.f ish vaqtida aniqlanadi. Kompilyator "bu o'sha funksiya" deb ayta olmaydi.

Muqobil yechimlar:

1. Dekorator (hiyla):

python
def tail_call(f):
    """⚠️ Ishlaydi, lekin sekin va chalkash."""
    def ichki(*args, **kwargs):
        while True:
            natija = f(*args, **kwargs)
            if not isinstance(natija, TailCall):
                return natija
            args, kwargs = natija.args, natija.kwargs
    return ichki

Bunday kutubxonalar bor (tco, tail-recursive), lekin ular:

  • Sekinroq (qo'shimcha o'rash)
  • Kod chalkashroq
  • Traceback baribir yo'qoladi

2. Trampolin naqshi:

python
def trampolin(f, *args):
    while callable(f):
        f = f(*args) if args else f()
        args = ()
    return f

3. Oddiy sikl:

python
def yigindi(r):
    jami = 0
    for x in r:
        jami += x
    return jami

Bu — eng oddiy, tez va o'qiladigan.

Boshqa tillar:

Til Holat
Scheme Standart TALAB qiladi
Haskell, Erlang Kafolatlangan
Scala @tailrec (kompilyator tekshiradi)
Kotlin tailrec kalit so'zi
JavaScript ES6 da bor, faqat Safari amalga oshirgan
Java, C#
Python

Scala/Kotlin yondashuvi qiziq: ular aniq e'lon talab qiladi:

kotlin
tailrec fun f(n: Int, akk: Int = 1): Int =
    if (n <= 1) akk else f(n - 1, akk * n)

Kompilyator tekshiradi: agar funksiya quyruqli bo'lmasa — xato beradi. Bu — "aniq yashirinlikdan yaxshi" tamoyiliga mos.

Pythonda shunga o'xshash narsa taklif qilingan, lekin qabul qilinmagan.

Xulosa: bu — falsafiy qaror. Python debug qulayligi va oddiylikni tanladi. Amaliy natija: Pythonda quyruqli rekursiya yozmang — sikl yozing. Bu tezroq, o'qilishi yaxshiroq va chuqurlik chegarasi yo'q.

Nimani mustahkamlaydi: 2.2, 2.4, 2.6-bo'limlar.

Xulosa

Bu darsda rekursiyani o'rgandik.

Eng muhim uch fikr:

  1. Ikki qism majburiy: asos va kichrayuvchi qadam. Asos holat bo'lmasa yoki unga yetib bo'lmasa — RecursionError. Chuqurlik chegarasi ~1000 (amalda ~990) va uni oshirish segfault xavfini keltiradi.

  2. Takroriy hisoblash bo'lsa — @cache. fib(30) keshsiz 2.7 million chaqiruv va yarim soniya, @cache bilan 31 chaqiruv va mikrosoniyalar. O(2ⁿ) → O(n).

  3. Rekursiya — daraxt va graf uchun, sikl — chiziqli uchun. JSON aylanishi, "bo'l va hukmronlik qil", backtracking — rekursiya tabiiy. Chiziqli akkumulyatsiya, katta yoki noma'lum chuqurlik — iteratsiya. Va r[1:] o'rniga indeks ishlating: kesim rekursiyani O(n²) qiladi.

Keyingi darsda — 7-qismning yakuni: docstring va tur ko'rsatkichlari. Funksiyani hujjatlash, mypy bilan tekshirish va zamonaviy Python uslubi.

Ulashish:Telegram'da

Izohlar (0)

Izoh yozish uchun kiring.

  • Hozircha izoh yo'q. Birinchi bo'ling!
7.13-dars: Rekursiya — IlmHamroh