Rekurencja – program w pewnych warunkach całkowicie się zatrzymuje

0

Witam,
mam problem z rekurencją, a dokładniej jeśli do 8500 wywołań znajdzie się rozwiązanie to jest dobrze ale jeżeli nie to przerywa wywołania, całkowicie się zatrzymuje program. Z czym może być związany problem zatrzymania się wywołań? A chciałbym żeby wywoływane maksymalnie 99999 razy

long long int reku(int liczba,int h, int i, int j, int k, int l)
{
	
	printf("%i,%i,%i,%i,%i\n", h, i, j, k, l);
	if (liczba == h*l*k*j*i)
	{
		if (h != 1)
		{
			printf("%i", h);
		}
		if (i != 1)
		{
			printf("%i", i);
		}
		if (j != 1)
		{
			printf("%i", j);
		}
		if (k != 1)
		{
			printf("%i", k);
		}
		if (l != 1)
		{
			printf("%i", l);
		}
		return 0;
	}
	else if (l == 9)
	{

		reku(liczba,h, i, j, k + 1, 1);
	}
	else if (k == 9)
	{

		reku(liczba,h, i, j + 1, 1, l);
	}
	else if (j == 9)
	{

		reku(liczba,h, i + 1, 1, k, l);
	}
	else if (i == 9)
	{

		reku(liczba,h+1, 1, j, k, l);
	}
	
	else
	{
	
		reku(liczba,h, i, j, k, l + 1);
	}
	return 0;
	
}

int main(void)
{
	int liczba = 0;

	printf("Podaj liczbe: ");
	if (scanf("%i", &liczba) == 0)
	{
		printf("Incorrect input");
		return 1;
	}
	else
	{
		if (liczba < 0 || liczba>10000)
		{
			printf("Incorrect input data");
			return 2;
		}
	}
	
        reku(liczba, 1, 1, 1, 1, 1);
	getchar();
	getchar();
	return 0;
}
1

Program się zatrzymuje czy wywala? Bo jeśli to drugie to pewnie masz do czynienia z sytuacją nazywaną stack overflow. Każde wywołanie rekurencyjne powoduje odłożenie pewnych danych (jak argumenty, zmienne lokalne, pewne rejestry) na stos. A ten jest skończony więc po pewnym czasie przekroczysz ten limit.

Jeśli chcesz ominąć ten problem to zamień wywołania rekurencyjne algorytmem opartym o pętlę z użyciem stosu alokowanym na stercie.

0

A można czyścić overflow? bo niestety nie mogę używać pętli

1

Można też zwiększyć rozmiar stosu dla programu (poszukaj w opcjach kompilatora) ale.. to nie jest rozwiązanie! Rozwiązaniem jest zmiana algorytmu jak podał @rrowniak

1

Nestety, nie Możesz "wyczyścić" overflow cokolwiek Miałeś na myśli. Jak Przepełniasz stos, to pomoże tylko zmiana na pętlę.

0

Okey, dzięki pomyślę nad możliwościami

0

Ja bym zaczął od zrozumienia czym jest rekurencja ogonowa. Bo ten kod można by spokojnie napisać rekurencją, ale zamiast prinftów z d**y funkcja musiałaby zwracać wynik. Optymalizacja rekurencji ogonowej widziałaby wtedy że w praktyce wcale nie trzeba trzymać kolejnych ramek stosu dla kolejnych zagłębień rekurencji, bo realnie interesuje cię tylko "ostatnia".

0

Poza argumentami funkcji i adresem powrotnym na stosie nic nie ląduje w tym kodzie, a to są niewielkie rzeczy.
Czyli jeśli się kończy "stack overflow" to musisz mieć błąd w kodzie (brakuje warunku kończącego rekurencję lub istniejący warunek zły), albo zbyt naiwny algorytm, bo by osiągnąć "stack overflow" w tym kodzie liczba zagłębień misi być bardzo duża (teraz widzę, że jest bardzo duża +8000), szczególnie, że kompilatory obecnie potrafią generować kod, który dynamicznie powiększać rozmiar stosu w razie potrzeby.

Jako, że funkcja się nazywa reku i jej nie opisałeś co ma robić, to nie mam ochoty próbować zrozumieć: co to miało robić, a co dopiero jaki jest tam błąd.
Na 100% można inaczej napisać tą rekurencję, ale problem jest nieznany.

Ergo to jest problem XY.

1 użytkowników online, w tym zalogowanych: 0, gości: 1