Özyineleme (Recursion)
Son güncelleme
Özyineleme, bir fonksiyonun aynı problemin daha küçük bir sürümü için kendini çağırmasıdır; bu, doğrudan yanıtlanabilecek kadar küçük bir duruma ulaşana dek sürer. Doğrudan yanıtlanabilen bu durum temel durumdur ve her özyinelemeli fonksiyonun bir tanesine ihtiyacı vardır: fib(n), fib(1) veya fib(0) değerine ulaşana kadar fib(n - 1) ve fib(n - 2) olarak bölünmeye devam eder; bu ikisi ise doğrudan kendi değerlerini döndürür. Yukarıdaki görselleştirme tam olarak bunu çalıştırır: Oynat'a basın ve çağrıların bir ağaç halinde dallanmasını, yapraklarda temel durumlara ulaşmasını, ardından değerlerini her seviyede birleştirerek yukarı döndürmesini izleyin.
Animasyonun gösterdiği ikinci şey çağrı yığınıdır: başlamış ama henüz geri dönmemiş her çağrı. Yığın, çağrılar derinleştikçe büyür, özyineleme derinliğinde zirve yapar ve sonuçlar geri geldikçe çözülür. Derin özyinelemenin yığın taşmasına yol açabilmesinin, yinelemeli bir döngünün ise yığını hiç büyütmemesinin nedeni budur. Aynı çağrı biçimi derinlik öncelikli arama, merge sort ve bir ikili ağaç üzerindeki işlemlerin çoğunun temelini oluşturur.
Zaman ve alan karmaşıklığı
Yukarıda gösterilen naif özyinelemeli Fibonacci ve iki standart iyileştirmesi için:
| Yaklaşım | Zaman | Alan | Notlar |
|---|---|---|---|
| Naif özyineleme | O(2^n) | O(n) | Çağrı ağacı her seviyede ikiye katlanır; alan, tüm ağaç değil en derin yığın kadardır. |
| Memoization ile | O(n) | O(n) | Her fib(k) bir kez hesaplanıp önbelleğe alınır; tekrar eden alt ağaçlar tek bir aramaya iner. |
| Yinelemeli döngü | O(n) | O(1) | İki döner değişken yığının yerini tamamen alır. |
| Genel olarak her özyineleme | çağrı sayısı × çağrı başına iş | O(max depth) | Yığın, başlamış ama henüz geri dönmemiş her çağrı için bir çerçeve tutar. |
Adım adım
| Adım | Ne olur |
|---|---|
| 1 | İlk çağrı fib(n) çağrı yığınına eklenir. |
| 2 | Bu çağrının fib(n - 1) sonucuna ihtiyacı vardır, bu yüzden o çağrı da yığına eklenir; üst çağrı bekler. |
| 3 | Çağrılar, biri n <= 1 durumunu sorana kadar iç içe geçmeyi sürdürür: temel durum daha derin bir çağrı olmadan hemen yanıt verir. |
| 4 | Temel durumun değeri üst çağrıya döner; üst çağrı artık ikinci çağrısını, fib(n - 2), başlatabilir. |
| 5 | Her iki alt çağrı da döndüğünde üst çağrı bunları toplar ve kendisi de döner; çerçevesi yığından çıkar. |
| 6 | Bu dönüş ağaç boyunca yukarı doğru tekrarlanır; sonunda ilk çağrının çerçevesi nihai yanıtla yığından çıkar ve yığın boşalır. |
Çözümlü örnek
Animasyonun oynattığı tam çağrı sırasıyla fib(4) hesaplanıyor:
| Çağrı | O andaki yığın | Döndürdüğü |
|---|---|---|
fib(4) | fib(4) | alt çağrıları bekler |
fib(3) | fib(4) > fib(3) | alt çağrıları bekler |
fib(2) | fib(4) > fib(3) > fib(2) | alt çağrıları bekler |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1 (temel durum) |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0 (temel durum) |
fib(2) birleştirir | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1 (temel durum) |
fib(3) birleştirir | fib(4) > fib(3) | 1 + 1 = 2 |
fib(2) tekrar | fib(4) > fib(2) | 1, sıfırdan yeniden hesaplanır |
fib(4) birleştirir | fib(4) | 2 + 1 = 3 |
Özyineleme ne zaman kullanılmalı
| Şu durumlarda kullanın | Şu durumlarda kaçının |
|---|---|
| Problem kendine benzer yapıdaysa: ağaçlar, iç içe yapılar, böl ve fethet | Basit bir döngü aynı şeyi yığın çerçevesi olmadan ifade ediyorsa |
Derinlik sınırlı ve makulse, örneğin merge sort içindeki O(log n) gibi | Derinlik çok büyük girdilerde girdi boyutuna ulaşabiliyor ve yığın taşması riski doğuyorsa |
| Geri izleme, nereden devam edeceğini hatırlamak için yığına ihtiyaç duyuyorsa | Aynı alt problemler tekrar ediyor ve bunları önbelleğe almıyorsanız |
| Özyinelemeli sürüm okumak ve doğrulamak için belirgin biçimde daha kolaysa | Çağrı ek yükünün ölçülebilir biçimde önem taşıdığı sıcak bir döngüdeyseniz |
Recursion kodu
Python, JavaScript, Java, C++, C dillerinde temiz ve çalıştırılabilir bir Recursion uygulaması. Bir dil seçin, kodu kopyalayın veya Coddy Playground'da hazır yüklenmiş olarak açın.
Python ile Recursion kodu
Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)JavaScript ile Recursion kodu
JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Java ile Recursion kodu
Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}C++ ile Recursion kodu
C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}C ile Recursion kodu
C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}Özyineleme SSS
Özyinelemede temel durum nedir?
Başka bir özyinelemeli çağrı olmadan yanıtlanabilecek kadar küçük olan girdidir.
fib(n) için bu n <= 1 koşuludur ve doğrudan n değerini döndürür. Ulaşılabilir bir temel durum yoksa çağrılar hiç bitmez, yığın büyümeye devam eder ve program yığın taşmasıyla çöker.Çağrı yığını nedir ve neden önemlidir?
Çalışma zamanı, başlamış ama henüz geri dönmemiş her çağrı için argümanlarını ve yerel değişkenlerini tutan bir çerçeve saklar. Özyineleme derinliği yığın yüksekliğine eşittir; bu yüzden
n seviye derine inen bir özyineleme, her çağrı neredeyse hiç iş yapmasa bile O(n) bellek kullanır. Animasyonun altındaki rozet sırası tam olarak bu yığının büyümesini ve çözülmesini gösterir.Özyinelemeli Fibonacci neden üstel zaman alır?
Çünkü aynı alt problemler tekrar tekrar hesaplanır: yukarıdaki çözümlü örnekte
fib(2), fib(4) içinde iki kez değerlendirilir ve bu tekrar her seviyede kabaca ikiye katlanarak O(2^n) çağrıya yol açar. Her sonucu ilk hesaplandığında önbelleğe almak, yani memoization, ağacı O(n) düzeyine indirir.Özyineleme yinelemeden daha mı iyidir?
Hiçbiri her durumda daha iyi değildir. Her özyineleme, açık bir yığın kullanan bir döngü olarak; her döngü de bir özyineleme olarak yeniden yazılabilir. Ağaç dolaşımı ve derinlik öncelikli arama gibi kendine benzer problemlerde özyineleme okunabilirlik açısından öne geçer; doğrusal geçişlerde ise yineleme bellek ve çağrı ek yükü açısından kazanır.
Özyinelemeli bir fonksiyonda yığın taşmasına ne yol açar?
Ya temel durum eksiktir veya hiç ulaşılamaz, bu yüzden çağrılar hiç bitmez; ya da özyineleme doğrudur ama derinliği çalışma zamanının yığın sınırı için fazla büyüktür, örneğin milyonlarca elemanlı bir girdide eleman başına bir çağrı yapmak gibi. Çözümler şunlardır: temel duruma ulaşılmasını garantilemek, derinliği sınırlamak veya yinelemeye dönüştürmek.
Hangi algoritmalar doğası gereği özyinelemelidir?
Böl ve fethet mantığındaki merge sort ve quicksort gibi sıralamalar, bir ikili ağaç ve graflar üzerindeki dolaşımlar, ikili arama, N vezir gibi geri izleme bulmacaları ve JSON ya da bir dosya sistemi gibi iç içe yapılar üzerinde tanımlanan her şey.
İlgili kaynaklar
Daha fazla görselleştirme
