Informatyka 3 ALO (środa)

Marta Żebrak
Temat: Rekurencja (lekcja 1/3)
Czy widziałeś kiedyś Matrioszkę – zestaw rosyjskich laleczek? Na początku widzisz tylko jedną figurkę, zwykle pomalowane drewno, które wygląda tak:

Możesz zdjąć górna połowę pierwszej figurki i co zobaczysz w środku? Kolejną, nieco mniejszą rosyjską lalkę!

Możesz wyjąć tę lalkę i rozdzielić górna połowę od dolnej. Wtedy zobaczysz kolejną jeszcze mniejszą Matrioszkę:

I jeszcze raz:

I możesz tak kontynuować i rozdzielać kolejne figurki. Ostatecznie znajdziesz maleńką rosyjską laleczkę, zbudowaną z jednego kawałka drewna, w związku z tym, ostatnia już się nie otwiera:

Rozpoczęliśmy od jednej dużej rosyjskiej lalki, a potem znajdowaliśmy coraz to mniejsze laleczki, dopóki nie zobaczyliśmy tak małej, że nie mogła ona już w środku pomieścić następnej.
Co ma wspólnego Matrioszka z algorytmami? Tak jak rosyjska lalka ma w sobie mniejszą lalkę, a ta posiada jeszcze mniejszą i tak dalej aż trafimy na laleczkę, która jest zbyt mała, aby pomieścić następną, tak my zobaczymy jak zaprojektować algorytm, który rozwiąże problem, rozwiązując najpierw mniejszy przypadek tego samego problemu, dopóki ten problem nie jest tak mały, aby rozwiązać go bezpośrednio. Taką technikę nazywamy rekurencją.

Stosowanie rekurencji jest charakterystyczne dla algorytmów projektowanych metodą dziel i zwyciężaj.

Typowym problemem, dla którego można zastosować rekurencję, jest obliczanie silni. Przypomnijmy, że silnia z n jest zdefiniowana jako n!=1×2×…×n. Funkcja ta może być równoważnie zapisana jako:

n!=(n−1)!×n, dla n>0,
n!=1, dla n=0.

W powyższym przykładzie górny wiersz jest ogólnym równaniem rekurencji, zaś dolny wiersz jest wartością brzegową. W języku C++ powyższa funkcja byłaby zapisana w poniższy sposób.

int silnia(int n)
{
    if (n > 0)
    {
        return n * silnia(n-1);
    }
    else
    {
        return 1;
    }
};

Przekształcenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, która nie zawiera odwołania do samej siebie) jest określane jako rozwiązanie rekurencji.

Przykład 1

Prześledźmy program wyznaczający sumę n kolejnych liczb naturalnych.

#include <iostream>
using namespace std;

long long suma(int n)
{
	if(n<1) 
		return 0;
	
	return n+suma(n-1);
}

int main()
{
	int n;
	
	cout<<"Podaj liczbę: ";
	cin>>n;
	
	cout<<"Suma "<<n<<" kolejnych liczb naturalnych wynosi "
<<suma(n)<<endl;

	return 0;
}

Załóżmy, że na wejściu podaliśmy liczbę 5 (program ma wyznaczyć sumę 1+ 2+ 3 + 4 + 5).

wynik = suma(5);

Funkcja suma(n), wywołała się z argumentem równym 5. Najpierw sprawdzamy, czy n< 1 (5 < 1). Warunek jest fałszywy, przechodzimy więc do następnej linijki return 5 + suma(5 – 1) . Funkcja suma wywołana została przez samą siebie z argumentem równym 4, a więc mamy:

wynik = suma(5) = 5 + suma(4),

daną czynność powtarzamy do momentu, gdy argument osiągnie wartość 0,

wtedy funkcja zwróci 0 (0<1, prawda).

wynik = suma(5) = 5 + suma(4) = 5 + 4 + suma(3) = 5 + 4 + 3 + suma(2) = 5 + 4 + 3 + 2 + suma(1) =

5 + 4 + 3 + 2 + 1 + suma(0) = 5 + 4 + 3 + 2 + 1 + 0 = 15.

Na dziś to tyle z podstaw, mam nadzieje, że zrozumieliście.