რა არის რეკურსია?

Question

რა არის რეკურსია?

Accepted Answer

**რეკურსია** არის, როდესაც ფუნქცია თავს იძახებს იმავე პრობლემის უფრო მცირე ვერსიის ამოსახსნელად. ყველა რეკურსიას სჭირდება **ბაზის შემთხვევა**, რომელიც მას დაостанавლებს და **რეკურსიული შემთხვევა**, რომელიც ბაზის მიმართულებით მოძრაობს.

## იდეა

პრობლემა დაყავით უფრო მცირე იდენტურ ქვეპრობლემებად. თითოეული ზარი ჩამოაღებს ფრეიმს **call stack**-ზე; დაბრუნებები მათ წაართმევს.

## მაგალითი

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## ტრეისი

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## სირთვე

აქ **O(n)** დრო და **O(n)** stack სივრცე (ერთი ფრეიმი თითოეული ზარისთვის).

## პიტნის პუნქტები

- **ბაზის შემთხვევის ნაკლი** -> უსასრულო რეკურსია -> stack overflow.
- ღრმა რეკურსია შეიძლება დაამცირო stack-ი; ზოგიერთ ენას აკლია tail-call optimization.
- გადაფარებული ქვეპრობლემების ხელახლა გამოთვლა შეიძლება გახდეს ექსპონენციალური დრო (შეასწორეთ memoization-ით).

## რატომ მნიშვნელოვანია

რეკურსია ნაირად გამოხატავს თვითმსგავსი პრობლემებს — ხეები, გრაფიკები, divide and conquer — ბევრად უფრო 청청 გზით, ვიდრე ციკლები.

ის არის მენტალური მოდელი merge sort-ის, backtracking-ის და dynamic programming-ის უკან.

Call stack-ის გაგება ასევე შენ უკეთესს ხდის debugging-ში და მეხსიერების შესახებ მსჯელობაში.