Rekursiya va "bo'l va hukmronlik qil"

def faktorial(n):
    if n <= 1:                    # bazaviy holat
        return 1
    return n * faktorial(n - 1)   # rekursiv holat


print(faktorial(5))

def faktorial_izohli(n, chuqurlik=0):
    chekinish = "  " * chuqurlik
    print(f"{chekinish}-> faktorial({n}) chaqirildi")

    if n <= 1:
        print(f"{chekinish}<- bazaviy holat, 1 qaytdi")
        return 1

    natija = n * faktorial_izohli(n - 1, chuqurlik + 1)
    print(f"{chekinish}<- {n} x ... = {natija} qaytdi")
    return natija


faktorial_izohli(4)

def yigindi(royxat):
    """Ro'yxat yig'indisi."""
    if not royxat:
        return 0
    return royxat[0] + yigindi(royxat[1:])


def teskari(matn):
    """Matnni teskari o'girish."""
    if len(matn) <= 1:
        return matn
    return teskari(matn[1:]) + matn[0]


def palindrommi(matn):
    """Palindrom tekshiruvi."""
    if len(matn) <= 1:
        return True
    if matn[0] != matn[-1]:
        return False
    return palindrommi(matn[1:-1])


def darajaga(asos, koeffitsient):
    """Tez darajaga ko'tarish. O(log n)."""
    if koeffitsient == 0:
        return 1
    if koeffitsient % 2 == 0:
        yarim = darajaga(asos, koeffitsient // 2)
        return yarim * yarim              # ikki marta emas, bir marta hisoblaymiz
    return asos * darajaga(asos, koeffitsient - 1)


print(yigindi([1, 2, 3, 4, 5]))
print(teskari("dasturlash"))
print(palindrommi("shosh"))
print(darajaga(2, 10))

def fibonachchi_sekin(n):
    """Sodda rekursiv Fibonachchi. O(2^n) - juda sekin!"""
    if n < 2:
        return n
    return fibonachchi_sekin(n - 1) + fibonachchi_sekin(n - 2)

import time

for n in [20, 25, 30, 32]:
    boshlanish = time.perf_counter()
    natija = fibonachchi_sekin(n)
    davomiylik = time.perf_counter() - boshlanish
    print(f"fib({n}) = {natija:>8,}   {davomiylik:>7.3f} soniya")

def fibonachchi_kesh(n, kesh=None):
    """Memoizatsiya bilan. O(n)."""
    if kesh is None:
        kesh = {}
    if n in kesh:
        return kesh[n]
    if n < 2:
        return n

    kesh[n] = fibonachchi_kesh(n - 1, kesh) + fibonachchi_kesh(n - 2, kesh)
    return kesh[n]


# Yoki tayyor dekorator bilan
from functools import lru_cache


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


import time

boshlanish = time.perf_counter()
natija = fibonachchi_tez(100)
print(f"fib(100) = {natija:,}")
print(f"Vaqt: {time.perf_counter() - boshlanish:.6f} soniya")
print(fibonachchi_tez.cache_info())

def fibonachchi_sikl(n):
    """Iterativ variant. O(n) vaqt, O(1) xotira."""
    if n < 2:
        return n

    oldingi, joriy = 0, 1
    for _ in range(2, n + 1):
        oldingi, joriy = joriy, oldingi + joriy
    return joriy


print(fibonachchi_sikl(100))

def eng_katta_va_kichik(massiv, chap=0, ong=None):
    """Bir o'tishda eng katta va eng kichikni topadi."""
    if ong is None:
        ong = len(massiv) - 1

    if chap == ong:                              # bitta element
        return massiv[chap], massiv[chap]

    if ong - chap == 1:                          # ikkita element
        if massiv[chap] < massiv[ong]:
            return massiv[chap], massiv[ong]
        return massiv[ong], massiv[chap]

    orta = (chap + ong) // 2
    chap_kichik, chap_katta = eng_katta_va_kichik(massiv, chap, orta)
    ong_kichik, ong_katta = eng_katta_va_kichik(massiv, orta + 1, ong)

    return min(chap_kichik, ong_kichik), max(chap_katta, ong_katta)


sonlar = [23, 5, 78, 12, 99, 3, 45, 67]
kichik, katta = eng_katta_va_kichik(sonlar)
print(f"Eng kichik: {kichik}, eng katta: {katta}")

def xanoy(disklar, manba="A", manzil="C", yordamchi="B", qadamlar=None):
    """Xanoy minoralari masalasi. 2^n - 1 ta qadam talab qiladi."""
    if qadamlar is None:
        qadamlar = []

    if disklar == 1:
        qadamlar.append(f"{disklar}-diskni {manba} dan {manzil} ga")
        return qadamlar

    # 1. Yuqoridagi n-1 ta diskni yordamchi ustunga
    xanoy(disklar - 1, manba, yordamchi, manzil, qadamlar)
    # 2. Eng kattasini manzilga
    qadamlar.append(f"{disklar}-diskni {manba} dan {manzil} ga")
    # 3. n-1 ta diskni yordamchidan manzilga
    xanoy(disklar - 1, yordamchi, manzil, manba, qadamlar)

    return qadamlar


qadamlar = xanoy(3)
for raqam, qadam in enumerate(qadamlar, start=1):
    print(f"{raqam}. {qadam}")
print(f"\nJami: {len(qadamlar)} ta qadam (2^3 - 1 = 7)")

from pathlib import Path


def papka_hajmi(yol, chuqurlik=0, korsatilsin=True):
    """Papka hajmini rekursiv hisoblaydi."""
    yol = Path(yol)

    if yol.is_file():
        return yol.stat().st_size

    jami = 0
    try:
        for element in sorted(yol.iterdir()):
            hajm = papka_hajmi(element, chuqurlik + 1, korsatilsin)
            jami += hajm

            if korsatilsin and chuqurlik < 2:
                chekinish = "  " * chuqurlik
                belgi = "[D]" if element.is_dir() else "   "
                print(f"{chekinish}{belgi} {element.name:<28}{hajm / 1024:>10,.1f} KB")
    except PermissionError:
        pass

    return jami


jami = papka_hajmi("app")
print(f"\nJami hajm: {jami / 1024:,.1f} KB")