7. Rekursiya

Fikr

Rekursiya — masalani o‘ziga o‘xshash kichikrog‘iga keltirish.
Ikki qismdan iborat:

1. Baza — eng kichik holat, javobi to‘g‘ridan-to‘g‘ri ma’lum;
2. Qadam — kattaroq holatni kichikrog‘i orqali ifodalash.

def fakt(n):
    if n <= 1:        # baza
        return 1
    return n * fakt(n - 1)      # qadam

Bazasiz rekursiya — cheksiz chaqiruv va RecursionError.

Chuqurlik chegarasi

Python sukut bo‘yicha ~1000 chuqurlikda to‘xtaydi. Musobaqada kerak
bo‘lsa:

import sys
sys.setrecursionlimit(300000)

Lekin chuqurlik 10⁵ dan oshsa, siklga o‘tgan ma’qul — rekursiya
xotirani ham ko‘p yeydi.

Rekursiyaning tuzog‘i

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

Bu eksponensial: fib(40) uchun ~10⁹ chaqiruv. Sabab — bir xil
qiymat qayta-qayta hisoblanadi. Yechim: natijani eslab qolish
(memoizatsiya) yoki sikl.

from functools import lru_cache

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

Bitta qator qo‘shildi — murakkablik O(2ⁿ) dan O(n) ga tushdi. Bu
dinamik dasturlashga birinchi qadam.

Qayerda tabiiy

Daraxt va grafni aylanish, bo‘lib tashlash (merge sort), barcha
variantlarni ko‘rib chiqish (backtracking) — bularda rekursiya
sikldan ancha o‘qilishli.