Recursion nedir?

Question

Recursion nedir?

Accepted Answer

**Recursion**, bir fonksiyonun aynı problemin daha küçük bir versiyonunu çözmek için kendisini çağırmasıdır. Her recursion, onu durduran bir **base case** ve temele doğru ilerleyen bir **recursive case** gerektirir.

## Fikir

Bir problemi daha küçük özdeş alt problemlere bölün. Her çağrı **call stack** üzerine bir frame iter; dönüşler onları çıkarır.

## Örnek

```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
```

## İzleme

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

## Karmaşıklık

Burada **O(n)** zaman ve **O(n)** stack alanı (her çağrı başına bir frame).

## Tuzaklar

- **Base case eksik** -> sonsuz recursion -> stack overflow.
- Derin recursion stack'i tüketebilir; bazı diller tail-call optimizasyonuna sahip değildir.
- Çakışan alt problemleri yeniden hesaplamak üstel zamana patlay verebilir (memoization ile düzeltiniz).

## Neden önemli

Recursion, kendine benzer problemleri — ağaçlar, grafikler, böl ve fethet — döngülerden çok daha temiz bir şekilde ifade eder.

Bu merge sort, backtracking ve dinamik programlama'nın arkasındaki zihinsel modeldir.

Call stack'i anlamak ayrıca hata ayıklama ve bellek hakkında akıl yürütmede sizi daha iyi hale getirir.