Yazan :Şadi Evren ŞEKER
Bilgisayar bilimlerinde, özellikle özyineli (recursive) problemlerde, problemin bir kısmının tekrar edilmesi durumudur. Örneğin, klasik bir problem olan fibonacci sayıları örneğinde, örtüşen altproblem bulunmaktadır.
Fibonacci serisinin 4. terimini hesaplamak isteyelim ve bunun için aşağıdaki fonksiyonu yazmış olalım:
Matematiksel olarak : fib(0) = 1, fib(1) = 1 ve fib(n) = fib(n-1)+fib(n-2)
Programlama dillerinde:
fib(int n){
if(n==0||n==1)
return 1;
return fib(n-1)+fib(n-2);
}
Yukarıdaki bu fonksiyonun çalışması sırasında çağırdığı alt fonksiyonları bir ağaç şeklinde çizecek olursak:
Yukarıdaki ağaçta, görüldüğü üzere, bazı terimler birden fazla kere hesaplanmaktadır. Örneğin fib(2) fonksiyonu, hem fib(4) hesaplanırken, hem de fib(3) hesaplanırken hesaplanmaktadır. Bu anlamda, problemin bir alt grubunun (subproblem) örtüştüğünden (overlap) bahsedebiliriz. Genelde bu tip örtüşmelerde, hız kazandırmak ve problemin sadece bir kere çözülmesini saplamak için dinamik programlama (dynamic programming) yöntemi kullanılır.