Özyineleme (Recursion)

Karanlık bir sinema salonunda oturduğunu ve kaçıncı sırada olduğunu merak ettiğini düşün. Arkana dönüp sıraları tek tek saymak yerine önündeki kişiye “Sen kaçıncı sıradasın?” diye soruyorsun. O da aynı soruyu kendi önündekine soruyor ve soru en öndeki kişiye kadar iniyor. En öndeki kişinin önünde kimse yok, o yüzden hiç düşünmeden “Birinci sıradayım” diyor. Sonra cevap geriye doğru yayılıyor: herkes duyduğu sayıya bir ekleyip arkasındakine iletiyor ve sonunda sen de kendi sıranı öğreniyorsun.

İşte özyineleme (recursion) tam olarak budur: bir problemi aynı problemin daha küçük bir kopyasına indirgemek ve en küçük kopyanın cevabını doğrudan bilmek. Kulağa bir hile gibi gelse de ağaç gezinme, merge sort ve quick sort, geri izleme ve dinamik programlama gibi ileride göreceğin pek çok algoritma bu fikrin üzerine kurulu. Özyinelemeli düşünmeyi öğrendiğinde, döngülerle yazması saatler sürecek bazı problemlerin birkaç satıra indiğini göreceksin.

Bu derste özyinelemeli bir fonksiyonun iki temel parçasını, çağrıların bellekte çağrı yığını (call stack) üzerinde nasıl ilerlediğini ve bir özyinelemenin maliyetini özyineleme ağacından nasıl okuyacağını öğreneceksin. Üstel süren bir algoritmayı memoization ile nasıl doğrusal hâle getireceğini göreceğiz. Son olarak Go'ya özgü bir konuya bakacağız: goroutine stack'lerinin nasıl büyüdüğü ve özyineleme çok derinleştiğinde ne olduğu.

Temel durum ve özyinelemeli durum

Doğru yazılmış her özyinelemeli fonksiyon iki parçadan oluşur:

• Temel durum (base case): Cevabı başka bir çağrı yapmadan, doğrudan bilinen en küçük girdi. Sinema örneğindeki en öndeki kişi.
• Özyinelemeli durum (recursive case): Problemi daha küçük bir alt probleme indirgeyip fonksiyonun kendisini çağıran ve gelen cevaptan asıl sonucu kuran kısım. Önündekine sorup cevaba bir ekleyen herkes.

Klasik ilk örnek faktöriyeldir. n! (n faktöriyel), 1'den n'e kadar olan tam sayıların çarpımıdır: 5! = 5 × 4 × 3 × 2 × 1 = 120. Dikkat edersen 5! = 5 × 4! olarak da yazılabilir. Yani faktöriyel kendi cinsinden tanımlanabilir:

• 0! = 1 (temel durum)
• n ≥ 1 için n! = n × (n − 1)! (özyinelemeli durum)

package main

import "fmt"

// factorial, n! değerini özyinelemeyle hesaplar.
func factorial(n int) int {
	if n == 0 { // temel durum
		return 1
	}
	return n * factorial(n-1) // özyinelemeli durum
}

func main() {
	for n := range 6 {
		fmt.Printf("%d! = %d\n", n, factorial(n))
	}
	fmt.Println("20! =", factorial(20))
}

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
20! = 2432902008176640000

Matematiksel tanım koda neredeyse birebir dönüştü. Bir özyinelemenin doğru çalışması için iki koşulun sağlanması gerekir:

1. Temel duruma mutlaka ulaşılmalı. Aksi hâlde fonksiyon kendini sonsuza kadar çağırır.
2. Her özyinelemeli çağrı girdiyi temel duruma doğru küçültmeli. factorial(n-1) her adımda n'yi bir azaltır ve n sıfıra ulaşınca zincir durur.

Bu iki koşul, matematikteki tümevarımın (induction) programlamadaki karşılığıdır: temel durum doğruysa ve “n − 1 için doğruysa n için de doğru” adımı geçerliyse, fonksiyon her geçerli girdi için doğrudur.

Çağrı yığını nasıl çalışır

Bir fonksiyon çağrıldığında Go çalışma zamanı, o çağrı için goroutine'in stack'inde bir çerçeve (stack frame) ayırır. Çerçevede fonksiyonun parametreleri, yerel değişkenleri ve iş bitince nereye dönüleceği bilgisi bulunur. Fonksiyon döndüğünde çerçevesi kaldırılır. En son çağrılan fonksiyon ilk döndüğü için bu yapı bir yığındır (LIFO) ve bu yüzden çağrı yığını (call stack) adını alır. Yığın veri yapısının kendisini Yığın (Stack) dersinde ayrıntılı olarak bulabilirsin.

Özyinelemede kritik nokta şu: factorial kendini çağırdığında mevcut çağrı bitmez, askıda bekler. factorial(4), 4 * factorial(3) ifadesini hesaplayabilmek için önce factorial(3)'ün dönmesini beklemek zorundadır. Üstelik her çağrının kendi n değişkeni vardır; factorial(3)'ün n'si ile factorial(4)'ün n'si bellekte farklı çerçevelerde durur ve birbirini etkilemez.

factorial(4) çağrıldığında, temel duruma ulaşıldığı anda yığın şöyle görünür:

factorial(0) çalışırken çağrı yığını:

        ┌───────────────────────┐
  üst → │ factorial(0)   n = 0  │  temel durum: 1 döndürür
        ├───────────────────────┤
        │ factorial(1)   n = 1  │  bekliyor: 1 * factorial(0)
        ├───────────────────────┤
        │ factorial(2)   n = 2  │  bekliyor: 2 * factorial(1)
        ├───────────────────────┤
        │ factorial(3)   n = 3  │  bekliyor: 3 * factorial(2)
        ├───────────────────────┤
        │ factorial(4)   n = 4  │  bekliyor: 4 * factorial(3)
        ├───────────────────────┤
        │ main                  │  bekliyor: factorial(4)
        └───────────────────────┘

Çıkış evresi (çerçeveler üstten başlayarak kaldırılır):

  factorial(0) = 1
  factorial(1) = 1 * 1 = 1
  factorial(2) = 2 * 1 = 2
  factorial(3) = 3 * 2 = 6
  factorial(4) = 4 * 6 = 24   → main'e döner

Bu süreç iki evreden oluşur:

1. İniş (winding): Çağrılar temel duruma ulaşana kadar yığına yeni çerçeveler eklenir. Bu evrede henüz hiçbir çarpma yapılmamıştır; her çerçeve bir cevap bekler.
2. Çıkış (unwinding): Temel durum bir değer döndürür. Çerçeveler sırayla yığından çıkarken bekleyen çarpmalar yapılır ve sonuç yukarı doğru taşınır.

Bunu kendi gözünle görmek için fonksiyona bir depth (derinlik) parametresi ekleyelim ve her çağrının başında ve sonunda derinlik kadar girintili bir satır yazdıralım:

package main

import (
	"fmt"
	"strings"
)

func factorial(n, depth int) int {
	indent := strings.Repeat("  ", depth)
	fmt.Printf("%s→ factorial(%d) çağrıldı\n", indent, n)
	if n == 0 {
		fmt.Printf("%s← factorial(0) = 1 (temel durum)\n", indent)
		return 1
	}
	result := n * factorial(n-1, depth+1)
	fmt.Printf("%s← factorial(%d) = %d\n", indent, n, result)
	return result
}

func main() {
	fmt.Println("sonuç:", factorial(4, 0))
}

→ factorial(4) çağrıldı
  → factorial(3) çağrıldı
    → factorial(2) çağrıldı
      → factorial(1) çağrıldı
        → factorial(0) çağrıldı
        ← factorial(0) = 1 (temel durum)
      ← factorial(1) = 1
    ← factorial(2) = 2
  ← factorial(3) = 6
← factorial(4) = 24
sonuç: 24

Çıktıdaki girinti, o anda yığında kaç factorial çerçevesi olduğunu gösteriyor. → satırları iniş evresine, ← satırları çıkış evresine ait. Özyinelemeli çağrıdan sonra gelen kodun (burada result'ı yazdıran satır) çıkış evresinde ve ters sırada çalıştığına dikkat et: önce en içteki çağrı, en son en dıştaki çağrı yazdırıyor. Özyinelemeli bir fonksiyonda hata ayıklarken bu tarz bir iz (trace) çıktısı eklemek, neyin ne zaman olduğunu anlamanın en hızlı yoludur.

Klasik özyineleme örnekleri

Özyinelemeli düşünmenin püf noktası şu soruyu sormaktır: “Problemin biraz daha küçük hâlinin cevabını bilseydim, asıl cevabı nasıl kurardım?” Bu soruyu farklı problemlerde uygulayarak kas hafızası kazanalım.

Dilimin toplamı

Bir dilimin toplamı, ilk elemanla geri kalan elemanların toplamının toplamıdır. Boş dilimin toplamı sıfırdır; bu da temel durum.

package main

import "fmt"

// sum, ilk elemanı geri kalanların toplamına ekler.
func sum(nums []int) int {
	if len(nums) == 0 { // temel durum: boş dilimin toplamı 0
		return 0
	}
	return nums[0] + sum(nums[1:])
}

// sumFrom aynı işi indeksle yapar: nums[i:] parçasının toplamını döndürür.
func sumFrom(nums []int, i int) int {
	if i == len(nums) {
		return 0
	}
	return nums[i] + sumFrom(nums, i+1)
}

func main() {
	nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
	fmt.Println(sum(nums))
	fmt.Println(sumFrom(nums, 0))
	fmt.Println(sum(nil))
}

31
31
0

nums[1:] ifadesi elemanları kopyalamaz; aynı alttaki diziyi gösteren yeni bir dilim başlığı oluşturur (Diziler ve Dilimler). Bu yüzden her çağrı sabit miktarda iş yapar ve toplam süre O(n) olur. Ancak son çağrı çalışırken yığında n + 1 çerçeve bulunduğundan ek alan da O(n)'dir. Aynı işi yapan bir for döngüsü ise O(1) ek alanla çalışır; bu farka ilerleyen bölümlerde döneceğiz. sumFrom dilimi hiç dilimlemeden bir indeks taşır. İkili arama ve merge sort gibi birçok özyinelemeli algoritmada bu indeksli stil tercih edilir.

String'i ters çevirme

Go'da bir string, UTF-8 ile kodlanmış byte'lardan oluşur ve ç, ğ, ı, ü gibi Türkçe harfler birden fazla byte kaplar (String, Byte ve Rune). Bu yüzden bir string'i byte byte ters çevirmek çok byte'lı karakterleri bozar. Doğru yol, önce []rune'a dönüştürmek ve rune'ları ters çevirmektir.

Özyinelemeli fikir şu: en dıştaki iki elemanın yerini değiştir, sonra aradaki parçayı aynı yöntemle ters çevir. Parçada sıfır ya da bir eleman kaldığında iş bitmiştir.

package main

import "fmt"

// reverseRunes, r[lo] ile r[hi]'yi değiştirir ve aradaki parçayı özyinelemeyle çevirir.
func reverseRunes(r []rune, lo, hi int) {
	if lo >= hi { // temel durum: 0 veya 1 elemanlı parça zaten ters
		return
	}
	r[lo], r[hi] = r[hi], r[lo]
	reverseRunes(r, lo+1, hi-1)
}

func reverse(s string) string {
	r := []rune(s)
	reverseRunes(r, 0, len(r)-1)
	return string(r)
}

// reverseBytes aynı işi byte'lar üzerinde yapar: Türkçe metinde hatalı!
func reverseBytes(b []byte, lo, hi int) {
	if lo >= hi {
		return
	}
	b[lo], b[hi] = b[hi], b[lo]
	reverseBytes(b, lo+1, hi-1)
}

func main() {
	s := "Günaydın çiçek"
	fmt.Println(reverse(s))

	b := []byte(s)
	reverseBytes(b, 0, len(b)-1)
	fmt.Printf("%q\n", string(b))
}

keçiç nıdyanüG
"ke\xa7\xc3i\xa7\xc3 n\xb1\xc4dyan\xbc\xc3G"

Rune tabanlı sürüm doğru sonucu verdi. Byte tabanlı sürüm ise ü ve ç gibi harfleri oluşturan byte'ların sırasını da ters çevirdiği için geçersiz UTF-8 dizileri üretti; %q bunları \xa7 gibi kaçış dizileriyle gösteriyor. Rune sürümünde her çağrı iki eleman işler ve derinlik yaklaşık n/2'dir, yani hem zaman hem yığın alanı O(n)'dir.

İnternette sık gördüğün şu kısa sürüm ise gizli bir maliyet taşır:

// Kısa ama pahalı: her adımda yeni bir string oluşur.
func reverseSlow(r []rune) string {
	if len(r) <= 1 {
		return string(r)
	}
	return reverseSlow(r[1:]) + string(r[0])
}

Her + işlemi yeni bir string ayırır ve içeriği baştan kopyalar. Uzunlukları 1, 2, 3, ..., n olan string'ler oluştuğu için toplam iş 1 + 2 + ... + n = O(n²) olur. Özyinelemenin maliyetini hesaplarken yalnızca çağrı sayısını değil, her çağrının içinde yapılan işi de hesaba katmayı unutma.

Üs alma: naif ve hızlı

xⁿ değerini hesaplamanın en doğrudan özyinelemeli tanımı şudur: x⁰ = 1 ve xⁿ = x · xⁿ⁻¹. Bu tanım n + 1 çağrı yapar. Oysa çok daha akıllıca bir gözlem var: n çiftse xⁿ = (xᵏ)², n tekse xⁿ = (xᵏ)² · x; burada k = n/2 (tam sayı bölmesi). Örneğin 2¹³'ü bulmak için 2⁶'yı bilmek yeterli, 2⁶ için 2³'ü, 2³ için 2¹'i. Üs her adımda yarıya indiği için yalnızca yaklaşık log₂ n çağrı yapılır.

2¹³ hesaplanırken çağrılar şöyle ilerler. Tabloyu yukarıdan aşağı okuduğunda iniş, aşağıdan yukarı okuduğunda çıkış evresini görürsün:

İki yaklaşımı çağrı sayısını sayarak karşılaştıralım:

package main

import "fmt"

var calls int

// powerNaive: x^n = x * x^(n-1)
func powerNaive(x, n int) int {
	calls++
	if n == 0 {
		return 1
	}
	return x * powerNaive(x, n-1)
}

// powerFast: x^n = (x^(n/2))^2, n tekse bir kez daha x ile çarp.
func powerFast(x, n int) int {
	calls++
	if n == 0 {
		return 1
	}
	half := powerFast(x, n/2) // alt problemi yalnızca BİR kez çöz
	if n%2 == 0 {
		return half * half
	}
	return half * half * x
}

func main() {
	for _, n := range []int{10, 30, 62} {
		calls = 0
		a := powerNaive(2, n)
		naiveCalls := calls

		calls = 0
		b := powerFast(2, n)
		fastCalls := calls

		fmt.Printf("2^%d = %d (eşit: %t)  naif: %d çağrı, hızlı: %d çağrı\n",
			n, a, a == b, naiveCalls, fastCalls)
	}
}

2^10 = 1024 (eşit: true)  naif: 11 çağrı, hızlı: 5 çağrı
2^30 = 1073741824 (eşit: true)  naif: 31 çağrı, hızlı: 6 çağrı
2^62 = 4611686018427387904 (eşit: true)  naif: 63 çağrı, hızlı: 7 çağrı

Naif sürüm n + 1 çağrı yaparken hızlı sürüm yalnızca ⌊log₂ n⌋ + 2 çağrı yaptı. n = 62'de durduk, çünkü 2⁶³ artık 64 bitlik işaretli int'e sığmaz. Kayan noktalı sayılarla ya da mod aritmetiğiyle aynı fikir çok büyük üsler için de çalışır; kriptografideki modüler üs alma bu yöntemin bir uygulamasıdır.

Hanoi kuleleri

Üç çubuk (A, B, C) ve A çubuğunda büyükten küçüğe dizilmiş n disk var. Amaç tüm diskleri C çubuğuna taşımak. Kurallar basit: tek seferde yalnızca bir disk taşınır, yalnızca bir çubuğun en üstündeki disk alınabilir ve büyük bir disk hiçbir zaman küçük bir diskin üzerine konamaz.

Bu bulmacayı döngülerle çözmeye çalışmak kafa karıştırıcıdır; özyinelemeli düşünmek ise çözümü üç adıma indirir. En büyük diski C'ye taşıyabilmek için üstündeki n − 1 diskin o anda B'de duruyor olması gerekir. O hâlde:

1. Üstteki n − 1 diski A'dan B'ye taşı (C'yi yardımcı olarak kullan).

2. En büyük diski A'dan C'ye taşı.

3. n − 1 diski B'den C'ye taşı (A'yı yardımcı olarak kullan).

4. ve 3. adımlar, aynı problemin bir disk eksik hâlidir. Bu adımların içeride nasıl yapılacağını düşünmene gerek yok; özyinelemeli çağrının kendi işini doğru yapacağına güvenmen yeterli. Bu güven sıçraması (leap of faith) özyinelemeli düşünmenin özüdür: temel durum doğruysa ve her adım problemi doğru biçimde küçültüyorsa, tümevarım sayesinde çözümün tamamı doğrudur.

package main

import "fmt"

// hanoi, n diski from çubuğundan to çubuğuna via çubuğunu kullanarak taşır.
func hanoi(n int, from, to, via string, moves *int) {
	if n == 0 { // temel durum: taşınacak disk yok
		return
	}
	hanoi(n-1, from, via, to, moves) // üstteki n-1 diski yoldan çek
	*moves++
	fmt.Printf("%d. hamle: disk %d, %s → %s\n", *moves, n, from, to)
	hanoi(n-1, via, to, from, moves) // n-1 diski en büyüğün üstüne taşı
}

func main() {
	moves := 0
	hanoi(3, "A", "C", "B", &moves)
	fmt.Println("toplam hamle:", moves)
}

1. hamle: disk 1, A → C
2. hamle: disk 2, A → B
3. hamle: disk 1, C → B
4. hamle: disk 3, A → C
5. hamle: disk 1, B → A
6. hamle: disk 2, B → C
7. hamle: disk 1, A → C
toplam hamle: 7

Hamle sayısına T(n) diyelim. Adımlardan doğrudan şu bağıntı çıkar: T(0) = 0 ve T(n) = 2·T(n − 1) + 1. Açarsak T(1) = 1, T(2) = 3, T(3) = 7, T(4) = 15 buluruz; yani T(n) = 2ⁿ − 1. Tümevarımla doğrulaması da kolay: 2·(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. Bu, bulmacanın çözülebileceği en az hamle sayısıdır ve üstel olarak büyür:

64 disk için saniyede bir hamle yapsan işin bitmesi yaklaşık 585 milyar yıl sürer. Hanoi kulelerinde bu üstel maliyetten kaçış yoktur, çünkü çıktının kendisi (hamle listesi) üstel uzunluktadır.

Fibonacci ve özyineleme ağacı

Fibonacci dizisinde her sayı kendinden önceki iki sayının toplamıdır: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Tanım doğrudan özyinelemelidir: fib(0) = 0, fib(1) = 1 ve n ≥ 2 için fib(n) = fib(n − 1) + fib(n − 2). Bu kez iki temel durum ve çağrı başına iki özyinelemeli çağrı var. Bu küçük fark maliyeti tamamen değiştiriyor. Çağrıları sayalım:

package main

import "fmt"

var calls int

func fib(n int) int {
	calls++
	if n < 2 { // temel durumlar: fib(0) = 0, fib(1) = 1
		return n
	}
	return fib(n-1) + fib(n-2)
}

func main() {
	for _, n := range []int{5, 10, 20, 30, 35} {
		calls = 0
		v := fib(n)
		fmt.Printf("fib(%d) = %d, çağrı sayısı: %d\n", n, v, calls)
	}
}

fib(5) = 5, çağrı sayısı: 15
fib(10) = 55, çağrı sayısı: 177
fib(20) = 6765, çağrı sayısı: 21891
fib(30) = 832040, çağrı sayısı: 2692537
fib(35) = 9227465, çağrı sayısı: 29860703

n beş arttığında çağrı sayısı kabaca 11 katına çıkıyor. fib(35) için yaklaşık 30 milyon çağrı yapıldı; oysa aynı sonucu kâğıt kalemle 34 toplama işlemiyle bulabilirsin. Boşa harcanan işin nerede olduğunu görmek için özyineleme ağacına bakalım.

Özyineleme ağacı

Özyineleme ağacında her düğüm bir fonksiyon çağrısıdır ve bir düğümün çocukları o çağrının yaptığı özyinelemeli çağrılardır. Kök ilk çağrıdır, yapraklar temel durumlardır. fib(5)'in ağacı şöyle:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)
│       ├── fib(1)
│       └── fib(0)
└── fib(3)             ← fib(3) ikinci kez, tüm alt ağacıyla birlikte
    ├── fib(2)
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

Ağaçta 15 düğüm var ama yalnızca 6 farklı alt problem (fib(0)'dan fib(5)'e kadar) çözülüyor: fib(3) iki kez, fib(2) üç kez, fib(1) beş kez hesaplanıyor. n büyüdükçe bu tekrarlar üstel olarak artar. Aynı alt problemin defalarca çözülmesine örtüşen alt problemler (overlapping subproblems) denir ve dinamik programlamanın çıkış noktası tam olarak budur.

Ağacın hangi sırayla oluştuğuna da dikkat et: Go önce fib(n-1) çağrısını tamamen bitirir, ancak ondan sonra fib(n-2)'ye geçer. Yani ağaç derinlik öncelikli olarak, soldan sağa gezilir ve herhangi bir anda yığında yalnızca kökten o anki düğüme giden yol bulunur.

Aşağıdaki görselleştirmede fib(5)'in çağrı ağacını adım adım izleyebilirsin. Çağrıların hangi sırayla açılıp kapandığını takip et ve aynı alt problemin ağacın farklı dallarında kaç kez belirdiğini say.

Ağaçtan karmaşıklık çıkarmak

Özyinelemeli bir fonksiyonun maliyetini bulmak için ağaca üç soru sor:

1. Bir düğümde ne kadar iş yapılıyor? Alt çağrılar hariç, fonksiyonun kendi gövdesindeki iş. fib'de bir karşılaştırma ve bir toplama var: O(1).
2. Ağaçta kaç düğüm var? Toplam zaman yaklaşık olarak düğüm sayısı × düğüm başına iştir.
3. Ağaç ne kadar derin? Yığında aynı anda yalnızca kökten o anki düğüme giden yol durduğu için ek alan, derinlik × çerçeve boyutudur.

fib için: her düğümün en fazla iki çocuğu var ve en uzun yol (hep n-1 dalına giden yol) yaklaşık n uzunluğunda. k. seviyede en fazla 2ᵏ düğüm olabileceğinden toplam düğüm sayısı 2ⁿ'yi geçmez; zaman karmaşıklığı O(2ⁿ) olur. Aslında n-2 dalları daha çabuk bittiği için ağaç dengesizdir ve gerçek büyüme hızı φⁿ'dir (φ = (1 + √5)/2 ≈ 1,618, altın oran). Yani O(2ⁿ) doğru bir üst sınırdır, daha sıkı sınır O(φⁿ)'dir. Kesin çağrı sayısı 2·fib(n + 1) − 1'dir; yukarıdaki çıktıyı bu formülle doğrulayabilirsin (fib(6) = 8 olduğundan fib(5) için 15 çağrı).

Alan ise yalnızca O(n)'dir, çünkü ağacın tamamı hiçbir zaman aynı anda bellekte bulunmaz. fib(4) dalı tamamen bitip çerçeveleri yığından kalktıktan sonra fib(3) dalı başlar.

Bu derste gördüğümüz fonksiyonların ağaçlarını yan yana koyalım:

Tablodan genel bir sezgi çıkıyor: tek alt çağrı yapıp girdiyi sabit miktarda küçülten fonksiyonlar bir zincir oluşturur ve doğrusal çalışır. Tek alt çağrı yapıp girdiyi yarıya bölenler logaritmiktir. Çağrı başına iki alt çağrı yapıp girdiyi yalnızca sabit miktarda küçültenler ise üstel ağaçlar üretir. Çağrı başına iki alt çağrı yapıp girdiyi yarıya bölen fonksiyonlarda (merge sort gibi) ağacın log₂ n seviyesi olur; her seviyede toplam O(n) iş yapılıyorsa sonuç O(n log n) çıkar. Bunu Verimli Sıralama Algoritmaları dersinde merge sort üzerinde göreceksin. Big-O gösteriminin kendisini tazelemek istersen Karmaşıklık Analizi dersine göz atabilirsin.

Memoization'a giriş

Naif Fibonacci'nin sorunu her adımın zor olması değil, aynı şeyi defalarca hesaplamasıydı. Çözüm şaşırtıcı derecede basit: bir alt problemin sonucunu ilk hesapladığında bir yere not et, sonraki seferlerde hesaplamak yerine oradan oku. Bu tekniğe memoization denir. Kelime Latince “memorandum”dan, yani “not edilecek şey”den gelir; “memorization” (ezberleme) ile karıştırma.

Memoization uygulayabilmek için iki şart var. Birincisi fonksiyon saf olmalı: aynı girdiye her zaman aynı çıktıyı vermeli ve dışarıdaki bir durumu değiştirmemeli. İkincisi girdiler bir anahtar olarak saklanabilmeli. Fibonacci her iki şartı da sağlıyor. Aşağıda aynı fikri önce bir map, sonra bir dilim ile uyguluyoruz:

package main

import "fmt"

var calls int

// fibMap, hesaplanan sonuçları bir map'te saklar.
func fibMap(n int, memo map[int]int) int {
	calls++
	if n < 2 {
		return n
	}
	if v, ok := memo[n]; ok { // daha önce hesaplandı mı?
		return v
	}
	v := fibMap(n-1, memo) + fibMap(n-2, memo)
	memo[n] = v // sonucu not et
	return v
}

// fibSlice, map yerine önceden ayrılmış bir dilim kullanır.
// -1 değeri "henüz hesaplanmadı" anlamına gelir.
func fibSlice(n int, memo []int) int {
	calls++
	if n < 2 {
		return n
	}
	if memo[n] != -1 {
		return memo[n]
	}
	memo[n] = fibSlice(n-1, memo) + fibSlice(n-2, memo)
	return memo[n]
}

func main() {
	calls = 0
	v := fibMap(35, map[int]int{})
	fmt.Printf("map ile:   fib(35) = %d, çağrı sayısı: %d\n", v, calls)

	memo := make([]int, 91)
	for i := range memo {
		memo[i] = -1
	}
	calls = 0
	v = fibSlice(90, memo)
	fmt.Printf("dilim ile: fib(90) = %d, çağrı sayısı: %d\n", v, calls)
}

map ile:   fib(35) = 9227465, çağrı sayısı: 69
dilim ile: fib(90) = 2880067194370816120, çağrı sayısı: 179

fib(35) için çağrı sayısı yaklaşık 30 milyondan 69'a düştü; fib(90) ise 179 çağrıda hesaplandı (naif sürüm bunu hayatın boyunca bitiremezdi). Neden tam olarak 2n − 1 çağrı? fib(n) önce fib(n − 1)'i çağırır ve bu zincir fib(1)'e kadar iner. Dönüşte her seviye fib(n − 2)'yi çağırdığında cevabı notlarda hazır bulur. Ağaç, sol kenardaki bir zincire ve her düğümden sarkan tek bir yaprağa dönüşür:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)    ← notlardan okundu
└── fib(3)        ← notlardan okundu

Her alt problem en fazla bir kez hesaplanır ve her hesaplama O(1) iş yapar; n + 1 farklı alt problem olduğundan zaman O(n) olur. Alan için hem not tablosu hem de n derinliğindeki yığın O(n) yer tutar.

Map mi, dilim mi? Anahtarlar 0'dan n'e kadar yoğun tam sayılarsa dilim daha hızlıdır: hash hesabı yapılmaz ve bellek bitişiktir. Anahtarlar seyrekse ya da bileşikse (örneğin iki boyutlu bir problemde struct{ i, j int }) map daha esnektir. Dilimde “henüz hesaplanmadı” bilgisini ayırt etmek için geçerli bir sonuç olamayacak bir değer (burada -1) kullandık; map'te bu işi virgül-ok (comma ok) deyimi üstleniyor. Bir de taşmaya dikkat: fib(92), 64 bitlik int'e sığan son Fibonacci sayısıdır.

Memoization, dinamik programlamanın yukarıdan aşağı (top-down) biçimidir. Aynı problemi aşağıdan yukarı bir tabloyla çözmek (tabulation), durumları tanımlamak ve alanı O(1)'e indirmek gibi konular Dinamik Programlama I: Temeller dersinde seni bekliyor.

Özyineleme ile iterasyonun karşılaştırılması

Her özyinelemeli algoritma iteratif olarak da yazılabilir; en kötü ihtimalle çağrı yığınının yaptığı işi kendi yığın veri yapınla elle yaparsın. Tersine her döngü de özyinelemeyle yazılabilir. Asıl soru hangisinin daha uygun olduğu:

Kısacası problem doğal olarak özyinelemeli bir yapıya sahipse ve derinlik makul düzeydeyse özyineleme kodu çok daha açık hâle getirir. Dengeli bir ağaçta derinlik O(log n) olduğu için bu neredeyse her zaman güvenlidir: bir milyar düğümlü dengeli bir ağacın bile yüksekliği yaklaşık 30'dur. Dilimi toplamak ya da faktöriyel hesaplamak gibi basit doğrusal işlerde ise döngü hem daha hızlı hem daha az bellek kullanır. Ağaçlarda iki yaklaşımın somut karşılaştırmasını Ağaçlar ve İkili Ağaçlar dersinde görebilirsin.

Kuyruk özyinelemesi

Özyinelemeli çağrı fonksiyonun son işlemiyse, yani çağrının sonucu hiçbir ek işlem yapılmadan doğrudan döndürülüyorsa buna kuyruk özyinelemesi (tail recursion) denir. factorial içindeki n * factorial(n-1) kuyruk özyinelemesi değildir, çünkü çağrı döndükten sonra hâlâ bir çarpma yapılması gerekir. Sonucu biriktiren bir parametre (accumulator) ekleyerek fonksiyonu kuyruk özyinelemeli hâle getirebiliriz:

package main

import "fmt"

// factTail kuyruk özyinelemelidir: çağrı son işlemdir, sonuç acc'de birikir.
func factTail(n, acc int) int {
	if n <= 1 {
		return acc
	}
	return factTail(n-1, acc*n)
}

// factLoop aynı fonksiyonun döngü hâlidir:
// parametreler değişkene, özyinelemeli çağrı döngünün bir turuna dönüşür.
func factLoop(n int) int {
	acc := 1
	for n > 1 {
		acc *= n
		n--
	}
	return acc
}

// fibLoop yalnızca son iki değeri tutar: O(n) zaman, O(1) alan.
func fibLoop(n int) int {
	a, b := 0, 1
	for range n {
		a, b = b, a+b
	}
	return a
}

func main() {
	fmt.Println(factTail(10, 1), factLoop(10))
	fmt.Println(fibLoop(10), fibLoop(90))
}

3628800 3628800
55 2880067194370816120

Kuyruk özyinelemeli bir fonksiyon mekanik olarak döngüye çevrilebilir: parametreler değişkene dönüşür, özyinelemeli çağrı “parametreleri güncelle ve başa dön” anlamına gelir, temel durum da döngünün bitiş koşulu olur. factTail ile factLoop arasındaki ilişki tam olarak budur. Scheme gibi bazı diller bu dönüşümü dil düzeyinde garanti eder; buna kuyruk çağrısı optimizasyonu (tail call optimization, TCO) denir ve kuyruk özyinelemesi bu sayede sabit yığın alanıyla çalışır.

Go'da stack büyümesi ve derin özyineleme

Go'da her goroutine küçük bir stack ile (birkaç kilobayt) başlar. Bir fonksiyon çağrısı için yer kalmadığında çalışma zamanı iki kat büyüklükte yeni bir stack ayırır, eski stack'in içeriğini oraya kopyalar ve stack'i gösteren işaretçileri günceller. Çöp toplayıcı, ihtiyacından çok büyük kalmış stack'leri daha sonra küçültebilir. Bu dinamik yapı sayesinde binlerce goroutine az bellekle çalışabilir (Goroutine'ler) ve özyineleme derinliği birkaç bin ile sınırlı kalmaz; yüz binlerce, hatta milyonlarca seviyelik özyinelemeler çoğu zaman sorunsuz çalışır.

Ama bu büyüme sınırsız değildir. 64 bit sistemlerde bir goroutine'in stack'i varsayılan olarak en fazla 1 GB, 32 bit sistemlerde 250 MB olabilir. Sınır aşıldığında program normal bir panic ile değil, kurtarılamayan bir fatal error ile sonlanır. Önceki bölümdeki kuyruk özyinelemeli yapıyı kullanarak bunu deneyelim:

package main

import "fmt"

// sumTo, 1'den n'e kadar olan sayıları kuyruk özyinelemesiyle toplar.
func sumTo(n, acc int) int {
	if n == 0 {
		return acc
	}
	return sumTo(n-1, acc+n)
}

func main() {
	fmt.Println(sumTo(1_000_000, 0))   // bir milyon derinlik: sorun yok
	fmt.Println(sumTo(100_000_000, 0)) // yüz milyon derinlik: stack taşar
}

500000500000
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0x... stack=[0x..., 0x...]
fatal error: stack overflow

runtime stack:
runtime.throw(...)
...

goroutine 1 [running]:
main.sumTo(...)
...
exit status 2

Bir milyon seviye sorunsuz çalıştı; yüz milyon seviye ise 1 GB sınırını aştı. Bu arada sumTo kuyruk özyinelemeli olmasına rağmen çöktü: Go'nun kuyruk çağrılarını optimize etmediğinin somut kanıtı. Bir stack'e kaç çerçeve sığacağı fonksiyonun çerçeve boyutuna bağlıdır; çok sayıda parametresi ya da büyük yerel değişkenleri olan bir fonksiyon çok daha erken taşar.

Özyinelemeyle olasılıkları gezmek

Özyinelemenin en güçlü kullanım alanlarından biri, bir dizi seçim yaparak tüm olasılıkları dolaşmaktır. Örneğin "abc" harflerinin tüm dizilişlerini (permütasyonlarını) üretelim. Fikir şu: ilk konuma koyacağın harfi seç, sonra kalan harflerin tüm permütasyonlarını özyinelemeyle üret. Yerleştirilecek harf kalmadığında bir permütasyon tamamlanmıştır.

package main

import "fmt"

// permute, rest içindeki her harfi sırayla prefix'e ekleyip kalanlarla devam eder.
func permute(prefix, rest string) {
	if rest == "" { // temel durum: yerleştirilecek harf kalmadı
		fmt.Println(prefix)
		return
	}
	for i := range len(rest) {
		permute(prefix+string(rest[i]), rest[:i]+rest[i+1:])
	}
}

func main() {
	permute("", "abc")
}

abc
acb
bac
bca
cab
cba

Bu örnek, basit tutmak için string'i byte byte işliyor ve bu yüzden yalnızca ASCII harflerle doğru çalışır; Türkçe harfler için []rune kullanmalısın. Ağacın ilk seviyesinde n seçenek, ikincisinde n − 1 seçenek vardır ve toplamda n! yaprak oluşur. Seçim yapıp keşfetme ve gerektiğinde seçimi geri alma şablonu geri izleme (backtracking) olarak bilinir; alt kümeler, kombinasyonlar ve N-Vezir problemiyle birlikte Geri İzleme dersinde ayrıntılı işleniyor.

Sık yapılan hatalar

• Temel durumu unutmak ya da ona ulaşamamak. factorial(-1) gibi beklenmedik bir girdi temel durumu atlarsa özyineleme hiç durmaz ve program stack taşmasıyla çöker. Temel durumu n <= 1 gibi kapsayıcı yaz ya da girdiyi en başta doğrula.
• Girdiyi küçültmemek. Gövdede yanlışlıkla f(n) ya da f(n+1) çağırmak sonsuz özyinelemeye yol açar. Her çağrının temel duruma bir adım yaklaştığını kendine açıkça gerekçelendir.
• Aynı alt çağrıyı iki kez yapmak. power(x, n/2) * power(x, n/2) gibi ifadeler O(log n)'lik bir algoritmayı O(n)'e çevirir. Sonucu bir değişkende tut.
• Örtüşen alt problemleri fark etmemek. Naif Fibonacci n = 50 için 40 milyardan fazla çağrı yapar. Ağaçta aynı argümanlarla tekrar eden çağrılar görüyorsan memoization kullan.
• Çağrı başına gizli maliyeti gözden kaçırmak. Her çağrıda string birleştirmek ya da dilimi kopyalamak, O(n) çağrılık bir özyinelemeyi O(n²)'ye çıkarabilir. Mümkünse indeks taşı ve yerinde çalış.
• Go'nun kuyruk özyinelemesini optimize ettiğini sanmak. Go kuyruk çağrısı optimizasyonu yapmaz; derin kuyruk özyinelemeleri de stack'i doldurur. Böyle fonksiyonları döngüye çevir.
• Tam sayı taşmasını unutmak. 21! ve 2⁶³ int sınırını aşar ve Go taşmada hata vermez, değer sessizce başa sarar. Büyük değerler için math/big kullan ya da girdiyi sınırla.

Alıştırmalar

package main

import "fmt"

// digitSum, n'in rakamlarının toplamını döndürür.
func digitSum(n int) int {
	if n < 0 {
		return digitSum(-n)
	}
	if n < 10 { // temel durum: tek basamak
		return n
	}
	return n%10 + digitSum(n/10)
}

func main() {
	for _, n := range []int{0, 7, 1234, 98765, -505} {
		fmt.Printf("digitSum(%d) = %d\n", n, digitSum(n))
	}
}

digitSum(0) = 0
digitSum(7) = 7
digitSum(1234) = 10
digitSum(98765) = 35
digitSum(-505) = 10

package main

import (
	"fmt"
	"unicode"
)

// check, r[lo..hi] aralığının palindrom olup olmadığını döndürür.
func check(r []rune, lo, hi int) bool {
	if lo >= hi { // temel durum: 0 ya da 1 harf kaldı
		return true
	}
	if r[lo] != r[hi] {
		return false
	}
	return check(r, lo+1, hi-1)
}

func isPalindrome(s string) bool {
	var letters []rune
	for _, c := range s {
		if unicode.IsLetter(c) {
			letters = append(letters, unicode.TurkishCase.ToLower(c))
		}
	}
	return check(letters, 0, len(letters)-1)
}

func main() {
	for _, s := range []string{
		"Ey Edip Adana'da pide ye",
		"Anastas mum satsana",
		"Ütü",
		"Kütüphane",
		"",
	} {
		fmt.Printf("%q → %t\n", s, isPalindrome(s))
	}
}

"Ey Edip Adana'da pide ye" → true
"Anastas mum satsana" → true
"Ütü" → true
"Kütüphane" → false
"" → true

package main

import (
	"fmt"
	"math"
)

// myPow, x^n değerini O(log |n|) çağrıda hesaplar; n negatif olabilir.
func myPow(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	half := myPow(x, n/2) // n/2 sıfıra doğru yuvarlanır: -5/2 = -2
	if n%2 == 0 {
		return half * half
	}
	if n > 0 {
		return half * half * x // 5 = 2*2 + 1
	}
	return half * half / x // -5 = 2*(-2) - 1
}

func main() {
	fmt.Println(myPow(2, 10))
	fmt.Println(myPow(2, -3))
	fmt.Println(myPow(1.5, 3))
	fmt.Println(myPow(-1, math.MinInt))
	fmt.Println(myPow(2, math.MinInt))
}

1024
0.125
3.375
1
0

package main

import "fmt"

type parser struct {
	src string
	pos int
}

// peek, boşlukları atlayıp sıradaki karakteri döndürür; girdi bittiyse 0.
func (p *parser) peek() byte {
	for p.pos < len(p.src) && p.src[p.pos] == ' ' {
		p.pos++
	}
	if p.pos == len(p.src) {
		return 0
	}
	return p.src[p.pos]
}

// expr = term (('+' | '-') term)*
func (p *parser) expr() int {
	result := p.term()
	for {
		switch p.peek() {
		case '+':
			p.pos++
			result += p.term()
		case '-':
			p.pos++
			result -= p.term()
		default:
			return result
		}
	}
}

// term = factor (('*' | '/') factor)*
func (p *parser) term() int {
	result := p.factor()
	for {
		switch p.peek() {
		case '*':
			p.pos++
			result *= p.factor()
		case '/':
			p.pos++
			result /= p.factor()
		default:
			return result
		}
	}
}

// factor = sayı | '-' factor | '(' expr ')'
func (p *parser) factor() int {
	switch p.peek() {
	case '-':
		p.pos++
		return -p.factor()
	case '(':
		p.pos++
		v := p.expr() // parantezin içi yine tam bir ifade
		p.peek()
		p.pos++ // ')' karakterini tüket
		return v
	}
	n := 0
	for p.pos < len(p.src) && p.src[p.pos] >= '0' && p.src[p.pos] <= '9' {
		n = n*10 + int(p.src[p.pos]-'0')
		p.pos++
	}
	return n
}

func eval(s string) int {
	p := &parser{src: s}
	return p.expr()
}

func main() {
	for _, s := range []string{
		"3 + 4 * (2 - 1)",
		"2 * (3 + 4) * 5 - 10 / 2",
		"-(2 + 3) * 4",
		"((((7))))",
		"100 / 7 / 2",
	} {
		fmt.Printf("%s = %d\n", s, eval(s))
	}
}

3 + 4 * (2 - 1) = 7
2 * (3 + 4) * 5 - 10 / 2 = 65
-(2 + 3) * 4 = -20
((((7)))) = 7
100 / 7 / 2 = 7

Kısa sınav

Özet

• Özyinelemeli bir fonksiyon, doğrudan cevaplanan bir temel durum ve problemi küçültüp kendini çağıran bir özyinelemeli durumdan oluşur; temel duruma ulaşılamazsa özyineleme durmaz.
• Her çağrı çağrı yığınında bir çerçeve açar. İniş evresinde çerçeveler birikir, çıkış evresinde bekleyen işlemler ters sırayla tamamlanır.
• Özyineleme ağacı maliyeti okumanın en kolay yoludur: zaman ≈ düğüm sayısı × düğüm başına iş, ek alan ≈ ağacın derinliği.
• Girdiyi yarıya bölen tek bir çağrı (hızlı üs alma) O(log n) sürer; çağrı başına iki alt çağrı yapıp girdiyi sabit miktarda küçültenler (naif Fibonacci, Hanoi) üstel zaman alır.
• Memoization, örtüşen alt problemleri yalnızca bir kez çözerek Fibonacci'yi üstel zamandan O(n)'e indirir. Yoğun tam sayı anahtarları için dilim, diğer durumlar için map kullan.
• Özyineleme ağaçlar, böl ve fethet ve geri izleme için doğal bir araçtır; basit doğrusal işlerde döngü daha hızlıdır ve O(1) ek alan kullanır.
• Go kuyruk çağrısı optimizasyonu yapmaz. Goroutine stack'leri dinamik olarak büyür ama 64 bit sistemlerde varsayılan 1 GB sınırı vardır; aşıldığında program kurtarılamayan fatal error: stack overflow ile çöker.