Yineleme
Yineleme, bir sürecin tekrarıdır. Okula giden bir öğrenci mezun olana kadar her gün okula gitme sürecini tekrarlar. Ayda en az bir veya iki kez markete gidip ürün alıyoruz. Bu süreci her ay tekrarlıyoruz. Matematikte, bir Fibonacci dizisi görev tekrarının özelliklerini de takip eder. İlk iki sayının 0 ve 1 olduğu, diğer tüm sayıların önceki iki sayının toplamı olduğu Fibonacci dizisini düşünelim.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Yineleme Adımları
Fibonacci formülü şu şekilde yazılabilir:
F (n) = F (n - 1) + F (n - 2)
fibonacci (0) = 0
fibonacci (1) = 1
Fibonacci (2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
fibonacci (3) = fibonacci (2) + fibonacci (1) = 1 + 1 = 2
fibonacci (4) = fibonacci (3) + fibonacci (2) = 2 + 1 = 3
fibonacci (5) = fibonacci (4) + fibonacci (3) = 3 + 2 = 5
fibonacci (6) = fibonacci (5) + fibonacci (4) = 5 + 3 = 8
Aşağıda verilen algoritma n'inci Fibonacci sayısını döndürür.
Özyineleme
Yeni bir Fibonacci sayısı (n. Sayı) aldığımızda, bir sonraki nth Fibonacci olarak (n + 1) th Fibonacci bulduğumuzda, n inci sayı aslında (n - 1) inci sayıdır. Yukarıda bahsedilen yineleme adımlarını gördüğümüz gibi: eğer n = 2 ise o zaman
Fibonacci (2) = Fibonacci (2-1) + Fibonacci (2-2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
Şimdi, fibonacci (3), yani n = 3 oluşturmak istiyoruz.
Fibonacci (3) = Fibonacci (3-1) + Fibonacci (3-2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Bu, n'nin akım (n - 1) inci değerini ve (n - 2) fibonacci değerini her artırdığında, aynı zamanda arttığı anlamına gelir. Ancak her n için (n - 1) th ve (n - 2) th fibonacci'yi takip etmek yorucu. Yineleme görevini kendi başına tekrar etmeye çağıran bir yöntem yazmaya ne dersiniz?
Kendini çağıran bir yöntem özyinelemeli yöntem olarak adlandırılır. Özyinelemeli bir yöntem, programın kendisini aramayı bıraktığı bir temel duruma sahip olmalıdır. Fibonacci serisi için temel durumumuz fibonacci (0) = 0 ve fibonacci (1) = 1'dir. Aksi takdirde, Fibonacci yöntemi kendisini iki kez - fibonacci (n - 1) ve fibonacci (n - 2) olarak adlandırır. Daha sonra fibonacci (n) elde etmek için onları ekler. Nth Fibonacci'yi bulmak için yinelemeli bir yöntem şu şekilde yazılabilir:
Dikkatli bakarsak, özyineleme stack özelliğini izler. Bir problemin çözümünü elde etmek için daha küçük alt problemleri çözer. N> 1 için son satırı yürütür. Dolayısıyla, n = 6 ise, fonksiyon fibonacci (6 - 1) ve fibonacci (6 - 2) 'yi çağırır ve ekler. fibonacci (6 - 1) veya fibonacci (5), fibonacci (5 - 1) ve fibonacci (5 - 2) 'yi çağırır ve ekler. Bu özyineleme, 6 temel durum değeri olan fibonacci (0) = 0 veya fibonacci (1) = 1 olana kadar devam eder. Temel duruma ulaştığında, iki temel değer ekler ve fibonacci'nin değerini alana kadar yükselir ( 6). Aşağıda özyinelemenin ağaç temsili bulunmaktadır.
özyineleme Ağacı
Gördüğümüz gibi, bir özyineleme ne kadar güçlü olabilir. Yukarıdaki ağacı yalnızca tek bir kod satırı oluşturur (temel durumlar dahil yukarıdaki kodun son satırı). Özyineleme bir yığını korur ve temel duruma ulaşana kadar daha derine iner. Dinamik Programlama (DP): Özyinelemenin anlaşılması ve kodlanması kolaydır, ancak zaman ve bellek açısından pahalı olabilir. Aşağıdaki özyineleme ağacına bir göz atın. Fib (4) ile başlayan sol alt ağaç ve fib (4) ile başlayan sağ alt ağaç tamamen aynıdır. Aynı sonucu 3 üretirler ancak aynı görevi iki kez yaparlar. Eğer n büyük bir sayı ise (örnek: 500000) o zaman özyineleme, aynı alt görevi birden çok kez çağıracağı için programı çok yavaşlatabilir.
özyineleme Ağaç daire içine alınmış
Bu sorunu önlemek için dinamik programlama kullanılabilir. Dinamik programlamada, aynı tipteki gelecekteki görevi çözmek için önceden çözülmüş alt görevi kullanabiliriz. Bu, orijinal problemi çözme görevini azaltmanın bir yoludur. Daha önce çözülmüş alt görev çözümlerini sakladığımız bir dizi fib [] alalım. Fib [0] = 0 ve fib [1] = 1 olduğunu zaten biliyoruz. Bu iki değeri saklayalım. Şimdi, fib [2] 'nin değeri nedir? Fib [0] = 0 ve fib [1] = 1 halihazırda depolanmış olduğundan, sadece fib [2] = fib [1] + fib [0] dememiz gerekiyor ve hepsi bu. Aynı şekilde fib [3], fib [4], fib [5], ……, fib [n] oluşturabiliriz. Önceden çözülmüş alt görevler, orijinal görev çözülene kadar bir sonraki alt görevi almak için çağrılır ve böylece gereksiz hesaplama azalır.
