Bir prosedür veya işlev, içindeki başka bir prosedüre çağrı içerebilir. Dahil olmak üzere, alt program kendisini arayabilir. Bu durumda, bilgisayar umursamıyor. O, her zaman olduğu gibi, yukarıdan aşağıya tanıştığı komutları tutarlı bir şekilde yürütür.
Matematiği hatırlarsanız, o zaman orada matematiksel tümevarım ilkesini karşılayabilirsiniz. Şöyledir: bazı ifadeler her doğal n için doğrudur, eğer
1) n = 1 için geçerlidir;
2) herhangi bir keyfi doğal için ifadenin geçerliliğinden n = k bunun n = k+1 için doğru olduğu sonucu çıkar.
Programlamada bu tekniğe özyineleme denir.
Tekrarlama, verilen basit temel durumlara dayalı olarak, bir nesne kümesini kümenin kendisi açısından tanımlamanın bir yoludur.
Yinelemeli kendini doğrudan veya diğer prosedürler ve işlevler aracılığıyla çağıran bir prosedürdür (işlev).
Özyinelemeli prosedür örneği:
void Rec(int a)
{
eğer (a>0) { Rec(a-1);
Console.WriteLine(a);
}
Şematik olarak, yineleme işi bir akış şeması olarak gösterilebilir.
Rec() prosedür parametre ile yürütülür 3 Ardından, 3 parametreli prosedür içinde, 2 parametreli prosedür çağrılır ve 0 parametreli prosedür çağrılana kadar devam eder. Daha sonra kontrol 1 parametresi ile prosedüre geri aktarılır, o da 1 sayısını yazdırarak işini bitirir ve bu böyle devam eder. parametre 3 ile prosedürden önce.
Çağrılan tüm prosedürler, işlerini tamamlayana kadar hafızada saklanır. Eşzamanlı prosedürlerin sayısı yineleme derinliği olarak adlandırılır.
|
Yinelemenin, bir alt programda yer alan komutların tekrar tekrar yürütülmesi olduğunu öğrendik. Ve bu da döngünün çalışmasına benzer. Döngü yapısının hiç bulunmadığı programlama dilleri vardır, örneğin Prolog.
for döngüsünün çalışmasını simüle etmeye çalışalım.
for döngüsü bir adım sayacı değişkeni içerir. Yinelemeli bir alt programda, böyle bir değişken parametre olarak iletilebilir.
İki parametreli // prosedür LoopImitation()
// ilk parametre – adım sayacı, ikinci parametre – toplam adım sayısı
statik geçersiz LoopImitation(int i, int n)
{
Console.WriteLine("Merhaba N" + i); // i herhangi bir değeri için tekrarlanacak ifade
if (i < n) // döngü sayacı n değerine eşit olana kadar,
{
LoopImitation(i+1, n); // yeni bir çağrı i+1 parametresiyle örnek prosedür (sonraki i değerine git)
}
}
|
Yineleme ve yineleme
Yinelemeyi anlamak için yinelemeyi anlamanız gerekir...
Programlamada yineleme döngüsel bir veri işleme sürecinin bir adımı.
Genellikle geçerli adımdaki (yineleme) yinelemeli algoritmalar, önceki adımlarda hesaplanan aynı işlemin veya eylemin sonucunu kullanır. Bu tür hesaplamalara bir örnek, yineleme ilişkilerinin hesaplanmasıdır.
Özyinelemeli değerin basit bir örneği faktöriyeldir: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
Her adımda (yineleme) değerin hesaplanması şu şekildedir: \(N=N \cdot i\) . \(N\) değerini hesaplarken, önceden depolanmış değeri \(N\) alırız >.
Bir sayının faktöriyeli yinelenen formül kullanılarak da açıklanabilir:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{durumlar} \end{denklem*}\)
Bu açıklamanın özyinelemeli bir işlevden başka bir şey olmadığını fark edebilirsiniz.
Burada ilk satır ( \(n <= 1\)) temel durumdur (yineleme sonlandırma koşulu) ve ikinci satır bir sonraki adıma geçiştir. < br />
| Yinelemeli faktöriyel fonksiyon |
Yinelemeli algoritma |
statik int Faktöriyel(int n){
eğer (n > 1)
dönüş n * Faktöriyel(n - 1);
aksi takdirde 1 döndürür;
}
|
int x = 1;
için (int i = 2; i <= n; i++)
x = x * ben;
Console.WriteLine("%d", x);
|
İşlev çağrılarının bazı ek yük içerdiği anlaşılmalıdır, bu nedenle özyinelemeli olmayan bir faktöriyel hesaplaması biraz daha hızlı olacaktır.
Sonuç: Basit bir yinelemeli algoritmaya sahip, yinelemesiz bir program yazabileceğiniz yerde, yinelemesiz yazmanız gerekir. Ancak yine de, hesaplama sürecinin yalnızca özyineleme ile uygulandığı geniş bir problem sınıfı vardır.
Öte yandan, özyinelemeli algoritmalar genellikle daha anlaşılırdır.
Bir sayının bir sayı sisteminden diğerine yinelemeli çevirisi
Yordamlarda bazı durumlarda, dönüş kelimesini argüman olmadan kullanabilirsiniz - yani, aslında prosedür yine de hiçbir şey döndürmez. Bu, yineleme yaparken, ; return , tekrarlanan parametre değerlerinin baz durumlarında düşüşü sonlandırmak için kullanılır. Örneğin, bir sayıyı ondalıktan ikiliye dönüştüren bir prosedür şöyle görünebilir:
statik void printTwo(int n)
{
eğer (n == 0) döndürürse;
printTwo(n / 2);
if (n % 2 == 0) Console.Write(0);
başka Console.Write(1);
}
|
Görev
"Tumba-Yumba" kabilesinin dilinin alfabesinde; dört harf: "K", "L", "M" ve "N". Bu alfabenin harflerinden oluşturulabilen n harflerinden oluşan tüm kelimeleri göstermeniz gerekmektedir.
Sorun, daha küçük bir soruna indirgenebilen normal bir kaba kuvvet sorunudur.
Sözcüğün yerine harfleri sırayla koyacağız.
Bir kelimenin ilk konumu alfabenin 4 harfinden (K. L, M, N) biri olabilir.
Önce K harfini koyalım. Ardından, ilk harf K olan tüm değişkenleri elde etmek için, kalan n - 1 konumlarında tüm olası harf kombinasyonlarını numaralandırmanız gerekir. (resme bakın).
 Böylece problem n - 1 uzunluğundaki dört problemi çözmeye indirgenmiştir.
n karakteri tekrarlayarak yinele
w[0]='K'; // son L-1 karakterlerini tekrarla
w[0]='L'; // son L-1 karakterlerini tekrarla
w[0]='M'; // son L-1 karakterlerini tekrarla
w[0]='N'; // son L-1 karakterlerini tekrarla
w - çalışan kelimeyi saklayan bir karakter dizisi.
Böylece özyineleme elde ettik.Problemin çözümünü özyinelemeli bir prosedür şeklinde düzenleyebiliriz.
Özyinelemenin ne zaman sona ereceğini belirlemek için kalır? Tüm karakterler ayarlandığında, yani ayarlanan karakter sayısı n olur. Bu durumda, ortaya çıkan kelimeyi ekranda görüntülemeniz ve prosedürden çıkmanız gerekir.
C# programı şöyle görünecek.
// w - değiştirilebilir parametre (dize sonucu)
// TumbaWords prosedürü alfabeyi bir karakter dizisi olarak iletir,
// kelime kelime ve önceden ayarlanmış karakter sayısı (başlangıçta – 0)
statik boşluk TumbaWords( string A, ref string w, int N )
{
if (N == w.Length) // w.Length - dizideki karakter sayısı
{
// tüm karakterler zaten kelimeye ayarlanmışsa,
// o zaman bir dizi çıktısı almak ve prosedürü sonlandırmak gerekir
Console.WriteLine(w);
geri dönmek;
}
for ( int i = 0; i
NOT w değişken bir parametredir (sonuç dizesi)!
|
|