Menü

C ++ 'da Özyineleme

recursion c

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

C ++ 'da Özyineleme Hakkında Her Şeyi Klasik Örneklerle Keşfedin.

Önceki eğitimimizde, C ++ 'daki işlevler hakkında daha fazla şey öğrendik.

Kodu alt birimlere ayırmak ve kodu daha basit ve okunabilir kılmak için işlevleri kullanmanın yanı sıra, işlevler, gerçek zamanlı problem çözme, matematiksel ve istatistiksel hesaplama dahil olmak üzere çeşitli diğer uygulamalarda kullanışlıdır.

C ++ 'da daha karmaşık uygulamalar geliştirdikçe, birçok gereksinimle karşılaşırız, bu nedenle kullanmak için birkaç özel C ++ kavramını koymamız gerekir. Özyineleme böyle bir kavramdır.

=> Tam C ++ Öğreticiler listesi için Burayı Ziyaret Edin.

C ++

Bu öğreticide, özyineleme, nerede ve neden kullanıldığına ve özyinelemeyi uygulayan bazı klasik C ++ örnekleriyle ilgili daha fazla bilgi edineceğiz.

Ne öğreneceksin:

Özyineleme Nedir?

Özyineleme, bir fonksiyonun kendisini çağırdığı bir süreçtir. Özyinelemeyi uygulayan veya kendisini çağıran işleve Özyinelemeli işlev denir. Özyinelemede, özyinelemeli işlev kendini tekrar tekrar çağırır ve bir son koşul karşılanana kadar devam eder.

Aşağıdaki resim Özyinelemenin nasıl çalıştığını göstermektedir:

Özyineleme Çalışması

Yukarıdaki diyagramda gördüğümüz gibi, ana işlev bir işlevi, funct () çağırır. Funct () işlevi de kendini tanımının içine çağırır. Özyineleme bu şekilde çalışır. Kendini çağıran işlevin bu süreci, biz onu sonlandıracak bir sonlandırma koşulu sağlayana kadar devam edecektir.

Genellikle, yinelemeyi uygularken, özyinelemeyi tetikleyecek bir koşul ve normal yürütmeyi yürütmek için başka bir koşul sağlayacak şekilde kod dalı sağlıyoruz.

Özyineleme Temel Koşulu

Özyineleme gerçekleştirildiğinde, temel duruma veya sonlandırma durumuna çözüm sağlanır ve daha küçük sorunların çözümlerine dayanarak daha büyük sorunların çözümleri oluşturulur.

Klasik bir Özyineleme örneğini, Factorial gösterimini ele alalım..

Matematiksel olarak bir n sayısının faktöriyelinin:

n! = nxn-1x… .x0!
verilen 0! = 1;

varsayılan ağ geçidi mevcut değildir Windows 10

Yani n = 3 için faktöriyel 3 olacak! = 3 × 2!

3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6

Yani programlı olarak bu hesaplamayı şu şekilde ifade edebiliriz:

int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }

Bu nedenle, yukarıda gösterildiği gibi, yukarıdaki faktöriyel hesaplamasını özyinelemeli bir fonksiyon çağrısı olarak ifade ettik. Görüyoruz ki n sayısı 1'den küçük veya eşitse, özyinelemeli çağrı yerine 1 döndürüyoruz. Bu, faktöriyel için özyinelemeyi durdurmaya izin veren temel koşul / durum olarak adlandırılır.

Bu nedenle, temel koşul özyinelemeli bir işlevin kendisini kaç kez çağıracağına temel olarak karar verir. Bu, daha büyük bir sayının faktöriyelini, temel sınıfa ulaşılıncaya kadar daha küçük sayılarla ifade ederek çok iyi hesaplayabileceğimiz anlamına gelir.

Aşağıda bir sayının faktöriyelini hesaplamak için mükemmel bir örnek verilmiştir:

#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout<

Çıktı:

Faktöriyeli hesaplanacak sayıyı girin: 10
10! = 3628800

Yukarıdaki örnekte özyineleme uyguluyoruz. Faktöriyel bulunacak sayıyı standart girdiden alıp faktöriyel işleve geçiriyoruz.

Faktöriyel işlevde, temel koşulu (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.

Özyinelemeli Çağrı İçin Bellek Tahsisi

Bir fonksiyon çağrısı yapıldığında, çağıran fonksiyonun durumunun yığında saklandığını ve bir fonksiyon çağrısı tamamlandığında, programın çalışmaya devam edebilmesi için bu durumun geri yüklendiğini biliyoruz.

Özyinelemeli bir işlev çağrısı yapıldığında, çağrılan işlevin durumu veya belleği, çağıran işlevin durumunun üzerine tahsis edilir ve her özyinelemeli işlev çağrısı için yerel değişkenlerin farklı bir kopyası yapılır.

Temel koşula ulaşıldığında, işlev çağıran işleve geri döner ve bellek ayrılır ve işlem devam eder.

Özyinelemede Yığın Taşması

Özyineleme sınırsız bir süre devam ettiğinde, yığın taşmasına neden olabilir.

Özyineleme ne zaman böyle devam edebilir? Bir durum, temel koşulu belirtmediğimiz zamandır. Diğer bir durum, bir program yürütülürken temel koşula ulaşılmamasıdır.

Örneğin,yukarıdaki faktöriyel programı değiştiriyoruz ve temel koşulunu değiştiriyoruz.

int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }

Yukarıdaki kodda, temel koşulu (n == 1000) olarak değiştirdik. Şimdi, n = 10 sayısını verirsek, temel koşulun asla ulaşamayacağı sonucuna varabiliriz. Bu şekilde bir noktada, yığın üzerindeki bellek tükenecek ve böylece yığın taşmasına neden olacaktır.

Bu nedenle, yinelemeli programları tasarlarken, sağladığımız temel koşula dikkat etmemiz gerekir.

Doğrudan ve Dolaylı Özyineleme

Şimdiye kadar özyinelemede, işlevin kendisini çağırdığını gördük. Bu doğrudan özyinelemedir.

Dolaylı özyineleme gibi başka bir özyineleme türü daha vardır. Bunda, bir işlev başka bir işlevi çağırır ve sonra bu işlev çağıran işlevi çağırır. F1 ve f2 iki işlevse. Sonra f1 f2'yi, f2'yi de f1'i çağırır. Bu dolaylı bir özyinedir.

L doğrudan özyinelemeyi göstermek için faktöriyel programımızı revize et.

#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout<

Çıktı:

Faktöriyeli hesaplanacak sayıyı girin: 5
5! = 120

sahte e-posta nasıl oluşturulur

Yukarıdaki örnekte, dolaylı özyineleme gösterdik. Ana işlev factorial_a'yı çağırır. Factorial_a, factorial_b'yi çağırır. Buna karşılık factorial_b, factorial_a'yı çağırır. Programın çıktısının etkilenmediğini görüyoruz.

Kuyruklu ve Kuyruklu Olmayan Özyineleme

Kuyruklu özyinelemeli işlev, işlevde son çağrının yürütüldüğü özyinelemeli bir işlevdir.

Örneğin, aşağıdaki işlevi düşünün.

void display(int n){ if(n<=1) return; cout<<” ”<

Yukarıdaki örnekte, görüntü, son işlev çağrısı olacak şekilde kuyruklu özyinelemeli bir işlevdir.

Kuyruklu işlevler, derleyici tarafından optimize edilebildikleri için kuyruklu olmayan özyinelemeli işlevlerden daha iyi kabul edilir. Bunun nedeni, kuyruklu özyinelemeli çağrı fonksiyondaki son ifade olduğundan, bu çağrıdan sonra çalıştırılacak kod olmamasıdır.

Sonuç olarak, işlev için geçerli yığın çerçevesinin kaydedilmesi gerekli değildir.

Yinelemeli Programlamaya Göre Özyinelemenin Artıları / Eksileri

Özyinelemeli programlar, kompakt ve temiz kod sağlar. Yinelemeli bir program, program yazmanın basit bir yoludur. Faktöriyel, Fibonacci dizisi, Hanoi kuleleri, ağaç geçişleri vb. Gibi çözüm için özyineleme gerektiren bazı doğal sorunlar vardır.

Başka bir deyişle, özyineleme ile verimli bir şekilde çözülürler. Yığınlar veya diğer veri yapıları kullanılarak yinelemeli programlama ile de çözülebilirler, ancak uygulanması daha karmaşık hale gelme şansı vardır.

Yinelemeli ve yinelemeli programlamanın problem çözme güçleri aynıdır. Bununla birlikte, özyinelemeli programlar, temel durum eşleşene kadar tüm işlev çağrılarının yığında depolanması gerektiğinden daha fazla bellek alanı kaplar.

Özyinelemeli işlevler, çok fazla işlev çağrısı ve dönüş değeri nedeniyle bir zaman ek yüküne de sahiptir.

Özyineleme Örnekleri

Daha sonra, yinelemeli programlama örneklerinden bazılarını uygulayacağız.

Fibonacci Serisi

Fibonacci serisi şu şekilde verilen dizidir:

0 1 1 2 3 5 8 13 ……

Yukarıda gösterildiği gibi, Fibonacci serisinin ilk iki sayısı 0 ve 1'dir. Sıradaki bir sonraki sayı, önceki iki sayının toplamıdır.

Bu seriyi Recursion kullanarak uygulayalım.

#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '<

Çıktı:

Fibonacci serisi için eleman sayısını girin: 10
10 sayı için Fibonacci Serisi: 0 1 1 2 3 5 8 13 21 34

Bu örnekte, Fibonacci dizisini oluşturmak için özyinelemeli bir çağrı kullandık. Sabit olan ilk iki sayının doğrudan yazdırıldığını ve sıradaki sonraki sayılar için özyinelemeli bir fonksiyon kullandığımızı görüyoruz.

Palindrom

Bir palindrom numarası, ters yönde okunduğunda soldan sağa doğru okunanla aynı olan bir sayıdır.

Örneğin, soldan sağa ve sağdan sola okurken 121 sayısı aynı şeyi, yani 121'i okur. Dolayısıyla 121 bir palindromdur.

Sağdan sola, yani ters sırada okurken 291 sayısı 192 gibi okunur. Dolayısıyla 291 bir palindrom değildir.

#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '<

Çıktı:

Palindromu kontrol etmek için numarayı girin: 6556
6556 numara bir palindromdur

Aynısı için ekran görüntüsü aşağıda verilmiştir.

Özyineleme - Palindrome

Yukarıdaki programda, giriş numarasını standart girişten okuyoruz. Daha sonra bu sayıyı bir sayının basamaklarını ters çevirmek için özyinelemeli bir işleve aktarırız. Ters rakamlar ve giriş numarası aynıysa, numara bir palindromdur.

Sonuç

Bununla özyinelemeyi bitirdik. Bu eğitimde, ayrıntılı olarak çeşitli örneklerle birlikte yinelemeli programlama, özyinelemeli işlevi, avantajlarını / dezavantajlarını inceledik.

Bu örneklerin yanı sıra, yineleme, çapraz geçişler (sıralı / ön sipariş / konumlayıcı), Hanoi kuleleri, BFS geçişi vb. Gibi bazı standart problemlerin çözümünde de kullanılır.

=> Sıfırdan C ++ Öğrenmek İçin Burayı Ziyaret Edin.

Önerilen Kaynaklar

^