recursion

Rekursiya — funksiya o‘zini kichikroq kirish bilan chaqiradi. Har rekursiyada ikki qism bo‘ladi: to‘xtash sharti (baza) va kichraytirish qadami.

def factorial(n):
    if n == 0:              # baza
        return 1
    return n * factorial(n - 1)

def digits_sum(n):
    return n if n < 10 else n % 10 + digits_sum(n // 10)

Qanday o‘ylash kerak

«Kichikroq masala yechilgan deb faraz qilaman. Undan kattasini qanday yasayman?» — shu savolga javob rekursiv qadam bo‘ladi.

Diqqat

• Python’da chuqurlik chegarasi ~1000: chuqur rekursiyada sys.setrecursionlimit(10**6) yoki siklga o‘tkazing.
• Bir xil argument qayta-qayta hisoblansa — eslab qoling (functools.lru_cache), bu allaqachon DP.

from functools import lru_cache

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