Recursion ve Dinamik Programlama

Bir klasörün içindeki tüm dosyaları saymak istersek her alt klasörde aynı işlemi tekrarlarız. Problemin kendi küçük biçimini içermesi recursion için doğal bir işarettir.

Recursion’ın iki şartı

Recursive fonksiyon kendisini çağırır. Sonsuza gitmemesi için bir base case ve her çağrıda probleme yaklaştıran ilerleme gerekir.

function factorial(n: number): number {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

n <= 1 base case’tir. factorial(n - 1) problemi küçültür. Her çağrı call stack’e frame ekler; çok büyük n stack overflow oluşturabilir. Aynı çözüm döngüyle sabit stack alanında yazılabilir.

Tekrarlanan alt problem

Naif Fibonacci fonksiyonu aynı değerleri defalarca hesaplar ve giriş her arttığında iş miktarı katlanarak büyür. Memoization, büyük problemden başlayıp ihtiyaç duyulan küçük sonuçları cache’leyen top-down (yukarıdan aşağı) yaklaşımdır. Tabulation, en küçük sonuçlardan başlayıp büyük sonuca doğru tabloyu dolduran bottom-up (aşağıdan yukarı) yaklaşımdır.

function fibonacci(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;
  const value = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  memo.set(n, value);
  return value;
}

memo.has sonucun daha önce hesaplanıp hesaplanmadığını kontrol eder. memo.get hazır sonucu döndürür. memo.set yeni sonucu saklar. Böylece zaman karmaşıklığı yaklaşık O(2ⁿ) yerine O(n), ek alan O(n) olur.

Ne zaman dinamik programlama?

Problem örtüşen alt problemlere ve optimal alt yapıya sahipse uygundur. Her recursion dinamik programlama gerektirmez. Bağımsız dalları olan ağaç gezisinde memo gereksiz olabilir; en kısa yol probleminde özel graph algoritmaları daha açıktır.

Alıştırma

Bir merdiveni her adımda bir veya iki basamak çıkarak kaç farklı şekilde tamamlayabileceğinizi önce recursion, sonra memoization ile çözün. Her n değerinin kaç kez hesaplandığını sayın.