Rekurencja cpp

Question

Jak napisać rekurencyjnie kod, który będzie zwracał sumę liczb podzielnych przez 2?

Answer 1

int sumaRekurencji(int liczba)
{
	int suma=0;
	if(liczba>0)
	{
		if(liczba % 2 == 0)
		{
			suma += liczba + sumaRekurencji(liczba-1);
		}
		else
		{
			suma += sumaRekurencji(liczba-1);
		}
	}
	return suma;
}

 

Comments

Dzięki wielkie!

Answer 2

Co oznacza rekurencyjnie?

Comments

Funkcja wywłouje samą siebie, aż do osiągnięcia upragnionego efektu. Zastępuje rozwiązania iteracyjne. Zazwyczaj takie rozwiązanie jest krótsze w zapisie ale mniej wydajne.

---

No i niekiedy rekurencja jest niezastąpiona. Na przykład usuwanie drzewa BST.

Answer 3

Rekurencja oznacza odwołanie się funckji do samej siebie.

W kodzie nie możemy zapomnieć o warunku, który zakończy odwoływanie się funkcji do samej siebie (w przykładzie jets to if(liczba>0) ) ponieważ jeżeli o tym zapomnimy to funkcji będzie się cały czas zapętlać aż do momentu kiedy przekroczymy zakres naszej zmiennej (np. dla long double jest to zakres od -1,1 × 10^4932 do 1,1 × 10^4932 - polecam poczytać o reprezentacji liczb zmiennoprzeciwnkowych)

Przykład rekurencji dla programu, który zlicza sumę liczb z danego przedziału:

double suma(int poczatek, int koniec){

    double wynik = 0;

    if(poczatek <= koniec)
    {
        wynik = poczatek + suma(poczatek+1, koniec);
    }
    
    return wynik;
}
int main()
{
    cout << suma(1,3);
}

Aby lepiej wyobrazić sobie o co chodzi, możemy skompilować kod tylko w warunku if zmieńmy suma(poczatek+1, koniec) na suma(poczatek, koniec). Wtedy program się zapętli i cały czas będzie wchodził do if, nigdy nie dojdzie do warunku kiedy poczatek > koniec ponieważ zmienna poczatek nie zostaje zwiększana.

Wywołanie rekurencyjne powyższego kodu dla suma(1,3) działa następująco:

wynik = (1 + suma(2,3) )

wynik = (1 + (2 + suma(3,3)) )

wynik = (1 + (2 + (3) ) )

tutaj już warunek nie zostaje spełniony bo poczatek jest większy niz koniec, więc lecimy do return wynik i zwracamy:

wynik = 6