C++ Recursive Fonksiyon Çağırırken Önceki Fonksiyonu Call Stack'den Kaldırma

C++
1

Aşağıdaki recursive fonksiyonda n argümanına 0’dan küçük bir değer verilene kadar fonksiyona kendini tekrar çağırıyor, ardından çağırma işlemleri bittikten sonra en üstteki stack’teki fonksiyon aldığı n değerini tekrar geri döndürdüğünde bir sonraki satıra geçilerek ekrana n sayısı yazılıyor, ve call stack’ten en son çağrılan fonksiyon silinerek bir alttaki fonksiyona devam ediliyor. Buraya kadar hiçbir sıkıntı yok.

#include <iostream>

void recursive(int n)
{
	if (n < 0)
		return n;

	recursive(n - 1);

	std::cout << n << std::endl;
}

int main()
{
	recursive(5);
	std::cin.get();
}

Ama eğer std::cout'u fonksiyonu çağırmadan önce yaparsam:

#include <iostream>

void recursive(int n)
{
	if (n < 0)
		return n;

	std::cout << n << std::endl;

	recursive(n - 1);
}

int main()
{
	recursive(5);
	std::cin.get();
}

Önce ekrana yazma işlemi yapılıyor, ardından bulunduğumuz stack memory’den silinmeden call stack’e yeni bir fonksiyon ekleniyor, yeni fonksiyon çalışırken de önceden çalıştırdığımız fonksiyondaki değişkenler gereksiz olarak memory’yi işgal ediyor. Eğer fonksiyonumuz şöyle olsaydı:

#include <iostream>

void recursive(int n)
{
	if (n < 0)
		return n;

	int cok_buyuk_veri_yapisi[5000];
	double cok_daha_buyuk_veri_yapisi[100000];

	// bu değişkenlerle işlemler

	recursive(n - 1);
}

int main()
{
	recursive(5);
	std::cin.get();
}

recursive(5)'de yapacak birşey kalmamasına rağmen burdaki değişkenlerin kapladığı alanların serbest bırakılması için recursive(4)'ün bitmesi beklenecekti. Onun bitmesi için de recursive(3)'ün ve bu böyle devam edecekti. Ben de diyorum ki call stack’e yeni bir fonksiyon eklerken önceki fonksiyonu (ya da önceki stack mi demelim ama her neyse) silinmesi için nasıl bir yol izlemeliyim. (En azından Flutter’da) mobil uygulama geliştirirken kullanılan Navigator.push() ve Navigator.popAndPush() gibi (tabi bu durum için böyle bir fonksiyon aramıyorum ama en azından bu sorunu çözebilecek bir yol).

Aklıma üsttekileri ayrı bir scope içine alma fikri geldi:

#include <iostream>

void recursive(int n)
{
	{
		if (n < 0)
			return n;

		int cok_buyuk_veri_yapisi[5000];
		double cok_daha_buyuk_veri_yapisi[100000];

		// bu değişkenlerle işlemler
	}

	recursive(n - 1);
}

int main()
{
	recursive(5);
	std::cin.get();
}

Ama bu durum sadece fonksiyonun en sonda çağırıldığı durumları çözüyor. Ben eğer recursive(5)'in gövdesinin ortalarında recursive(4)'ü cağırıp recursive(5)'i terminate etmek istersem nasıl bir yol izlemeliyim?

(Bazı terimleri birbiriyle karıştırmış olabilirim uyarırsanız düzeltirim)

2

Bu istediğinizin adı tail recursion optimization ve belli parametreler ile çoğu derleyici bunu yapıyor. Burada bahsedilmiş:

Eğer f fonksiyonu herhangi bir g fonksiyonunu çağırdıktan sonra hala yapması gereken işlemler varsa f’e ait call stack’ı silemeyiz, fonksiyon oradaki değişkenleri kullanıyor olabilir. Onun dışında örneğimdeki g fonksiyonun ortada veya başka bir yerde çağırılmasının çok önemli olacağını sanmıyorum, g çağırıldıktan hemen sonra f’in return etmesi de derleyicinin optimizasyon yapması için yeterli olabilir. Üretilen çıktıyı incelemek lazım.

Verdiğim linkte de bahsedilmiş, çağırılması gereken destructor’lar yüzünden derleyici tail recursion optimization yap(a)mayabilir.

1 Beğeni
3

Ben de orada return etmekten bahsetmeye çalışıyordum ama sanırım açık açık yazmayı unutmuşum.

4

Oncelikle, orneklerdeki fonksiyonlar int dondurmeleri gerekmesine ragmen dondurmuyorlar. Su haliyle UB’ye yol aciyorlar ve haliyle her seyin olmasi mumkun.

Eger ikinci ornekteki son statement’i return recursive(n - 1) olarak degistirirsen bu bir tail call oluyor ve bahettigimiz tail call optimization’a tabi olabiliyor. En son n - 1 degerinin hesaplanip push’lanmasiyla beraber fonksiyonda okunacak hic bir degisken, yapilacak hic bir is kalmiyor ve call stack ucurulabiliyor.

Yani anladigim kadariyla verdigin ornekler ters.

Bu arada std::cout::operator<< gibi ara cagrilar bu denkleme girmiyor cunku calisma bir sonraki statement’a gectigi anda call stack’i ucurulmus oluyor.

1 Beğeni
5

Evet orasını gözden kaçırmışım düzelttim şimdi.

Tam olarak anlayamadım. Hangi örnekteki std::cout?

6

Iki ornekteki dort cagri da: