Yineleme
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. Ayrıca, 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, orada matematiksel tümevarım ilkesi ile tanışabilirsiniz. Aşağıdaki gibidir:
bazı ifadeler her doğal n için doğrudur, eğer
1. n = 1 ve için geçerlidir
2. Herhangi bir keyfi doğal n = k için ifadenin geçerliliğinden bunun, n = k + 1 için doğru olduğu sonucu çıkar.
Programlamada bu tekniğe yineleme denir.
Özyineleme verilenlere dayalı olarak, kümenin kendisi açısından bir nesne kümesini tanımlamanın bir yoludur. basit temel durumlar.
Tekrarlı kendini doğrudan veya diğer prosedürler ve işlevler aracılığıyla çağıran bir prosedürdür (işlev).
Örnek
def Rec(a):
eğer (a>0): Rec(a-1)
baskı(a)
Şematik olarak, özyineleme işi bir akış şeması ile temsil edilebilir
Rec() prosedürü parametre 3 ile yürütülür.Ardından, parametre 3 ile prosedür içinde, parametre 2 ile prosedür çağrılır ve bu, parametre 0 ile prosedür çağrılıncaya kadar devam eder.0 parametresi ile prosedür çağrıldığında, özyinelemeli çağrı artık gerçekleşmeyecek ve 0 parametreli prosedür 0 sayısını yazdıracak ve çıkacaktır. 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.
|
Döngü değişimi olarak yineleme
Özyinelemenin, bir alt programda içerilen talimatların tekrar tekrar yürütülmesi olduğunu gördük. Ve bu da döngünün çalışmasına benzer. Döngü yapısının tamamen 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. Özyinelemeli bir alt programda, böyle bir değişken parametre olarak iletilebilir.
# Prosedür LoopImitation() iki parametreli
# İlk parametre – adım sayacı, ikinci parametre – toplam adım sayısı
def LoopImitation(i, n):
print("Hello N", i) # i'nin herhangi bir değeri için tekrarlanacak ifade
eğer ben n: # Döngü sayacı n değerine eşit olana kadar,
LoopImitation(i + 1, n) # prosedürün yeni bir örneğini çağırın,
# i+1 parametresiyle (bir 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.
| Yinelemeli faktöriyel işlevi |
Yinelemeli algoritma |
|
def Faktöryel(n):
eğer n > 1:
dönüş n * Faktöriyel(n - 1)
başka:
dönüş 1
|
x=1
(1, n + 1) aralığındaki i için:
x = x * ben;
|
İş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.
Görev
Kabile dilinin alfabesinde «Tumba-Yumba» dört harf: "K", "L", "M" ve "N". Bu alfabenin harflerinden oluşturulabilecek n harften oluşan tüm kelimelerin ekranda gösterilmesi 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 biri olabilir ( K, L, M, N).
İlk önce ' K' harfini ilk sıraya koyun. Ardından, ilk harfi ' K' olan tüm varyantları elde etmek için, kalan n-1 konumlar ve .etc. (resmi görmek)
Böylece, özyinelemeli bir çözüm bulduk: bir döngüde, tüm olası ilk harfleri gözden geçirin (alfabenin her harfini ilk sıraya koyarak) ve her durum için tüm olası "kuyrukları" oluşturun; uzunluk n-1.
Karakterlerin yinelemeli tekrarı
Geriye kalan kısım boş olduğunda (n = 0), yani tekrarlamayı durdurmanız ve bitmiş kelimeyi çıktı almanız gerekir. tüm harfler zaten seçili.
Özyinelemeli prosedür şuna benzer:
def TumbaWords(kelime, alfabe, n):
eğer n < 1:
baskı(kelime)
geri dönmek
alfabede c için:
TumbaWords(kelime+c, alfabe, n - 1)
|
|