Idea rozwiązania rekurencyjnego

Mechanizm rekurencji polega na wykorzystaniu funkcji, która wywołuje samą siebie aż do momentu, gdy przeznaczone jej do rozwiązania zadanie zostanie wykonane. Funkcja taka może być typu void, ale może również zwracać obliczoną wartość.

Zobaczmy, jak wygląda funkcja rekurencyjna, której zadaniem jest wypisanie wszystkich liczb naturalnych dodatnich mniejszych lub równych od podanego parametru.

Specyfikacja problemu:

Dane:

• n – liczba naturalna dodatnia

Wynik:

Program wypisuje malejący ciąg liczb naturalnych dodatnich mniejszych lub równych n.

#include <iostream>
using namespace std;

void wypiszNaturalne(int n) {
	if (n < 1) {
		return;
	}
    
	cout << n << endl;
	wypiszNaturalne(n - 1);
}

Ponieważ zadaniem funkcji jest wypisanie liczb na standardowe wyjście, nie ma potrzeby, aby zwracała ona jakąkolwiek wartość. Zdefiniowaliśmy zatem funkcję typu void. Parametr funkcjiparametr funkcjiParametr funkcji n przechowuje wartość największej liczby naturalnej, którą program musi wypisać.

Jako pierwsza w funkcji pojawia się instrukcja warunkowainstrukcja warunkowainstrukcja warunkowa, która zatrzyma działanie funkcji, bez wywołania kolejnej instancji, jeżeli parametr n osiągnie wartość mniejszą niż jeden. Warunków powodujących zakończenie działania funkcji rekurencyjnej może być więcej niż jeden.

Zaraz pod instrukcją warunkową wypisujemy wartość parametru n, a następnie wywołujemy funkcję rekurencyjną z argumentemargument funkcjiargumentem zmniejszonym o 1.

Prześledźmy działanie funkcji, gdy wywołamy ją z argumentem n równym 3.

if (3 < 1) {
	return;
}
    
cout << 3 << endl;
wypiszNaturalne(3 - 1);

Czy 3 jest mniejsze niż 1? Nie. Dlatego pomijamy instrukcje warunkową i wypisujemy wartość 3, a następnie wywołujemy tę samą funkcję z argumentem zmniejszonym o 1, czyli n = 2.

if (2 < 1) {
	return;
}
    
cout << 2 << endl;
wypiszNaturalne(2 - 1);

Liczba 2 nie jest mniejsza od 1, więc polecenie zapisane w instrukcji warunkowej nadal nie zostaje wykonane. Wpisujemy więc liczbę 2 i wywołujemy funkcję z argumentem równym 1.

if (1 < 1) {
	return;
}
    
cout << 1 << endl;
wypiszNaturalne(0);

Czy 1 jest mniejsze niż 1? Ponownie nie, więc wypisujemy wartość 1 i wywołujemy funkcję po raz kolejny, tym razem z argumentem równym 0.

if (0 < 1) {
	return;
}

Ponieważ liczba 0 jest mniejsza niż 1, wyrażenie logiczne w instrukcji warunkowej przybierze wartość true. W rezultacie zostanie wykonane polecenie return, które zakończy działanie funkcji. Wynikiem działania programu będą liczby 3, 2, 1.

Jak widać, każde wywołanie funkcji zatrzymuje pracę funkcji bieżącej. Czeka ona, aż funkcja przez nią wywołana zakończy działanie (i zwróci wartość, jeśli miałaby ją zwracać). Przy wywoływaniu kolejnych funkcji rekurencyjnych dzieje się tak samo.

Jeżeli wywołana funkcja rekurencyjna spełni warunek zakończenia pracy i – gdy tego oczekiwano – zwróci wartość zamiast wywoływać siebie samą, funkcja, która ją wywołała, może podjąć działanie. Zwraca ona wartość poprzedniczce, która również podejmuje działanie, zwraca wartość funkcji ją wywołującej i tak dalej. Proces ten trwa do momentu, gdy pracę wznowi pierwsza, wywołana przez program funkcja. Zwraca ona ostateczny wynik realizacji algorytmu rekurencyjnego.

Aby opisany mechanizm działał poprawnie, potrzebny jest co najmniej jeden warunek, po spełnieniu którego funkcja nie zostanie wywołana po raz kolejny, lecz zakończy się (oraz ewentualnie zwróci wartość). Jeżeli taki warunek się nie pojawi, funkcja będzie wywoływać się w nieskończoność, co spowoduje zawieszenie programu lub błąd przepełnienia stosu.

Przy każdym kolejnym wywołaniu funkcji jej parametr lub jeden z parametrów muszą zmienić wartość. Nie może też dojść do sytuacji, w której wartość parametru lub parametrów powtórzą się między wywołaniami. Jeżeli tak się stanie, program może nigdy nie zakończyć działania.

Ciąg Fibonacciego

Ciąg Fibonacciegociąg FibonacciegoCiąg Fibonacciego to ciąg liczb naturalnych, w którym pierwsze dwa elementy (o indeksie zero i jeden) to 0 oraz 1, a każdy kolejny element jest sumą dwóch poprzednich. Elementem ciągu o indeksie dwa jest zatem 0 + 1 = 1, o indeksie trzy zaś  1 + 1 = 2 i tak dalej.

Definicja ciągu Fibonacciego ma następującą postać:

$F_n=\{\begin{array}{ll}0& \text{dla }n=0\\ 1& \text{dla }n=1\\ F_{n-1}+F_{n-2}& \text{dla }n>1\end{array}$

Rekurencja

Iteracja

Napiszemy program w języku C++, który w sposób iteracyjny znajdzie i wypisze element ciągu Fibonacciego o indeksie n. Implementację algorytmu zaczniemy od stworzenia funkcji iteracyjnej.

long long iter_fibonacci(int n) {
  
}

Ta funkcja również będzie zwracać wartość. Jej typ to long long, ponieważ wartości kolejnych wyrazów ciągu Fibonacciego rosną wykładniczo.

Zapisujemy warunki, po których spełnieniu zostanie zatrzymane działanie funkcji i zwróci ona wartość. Wiemy, że pierwszy wyraz ciągu Fibonacciego – zatem wyraz o indeksie 0 – ma wartość 0. Natomiast drugi wyraz – czyli wyraz o indeksie 1 – wynosi 1. Zapiszemy odpowiednie instrukcje warunkowe.

long long iter_fibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}
}

Musimy brać również pod uwagę przypadek, gdy wartość parametru n jest większa niż 1. W takiej sytuacji każdy kolejny element jest sumą dwóch poprzednich. Dla dalszego działania funkcji potrzebujemy zmiennych pomocniczych. Inicjalizujemy trzy zmienne pomocnicze: a, b (oznaczające wartości dwóch początkowych wyrazów ciągu) oraz i (indeks kolejnego elementu ciągu Fibonacciego). Przypisujemy im odpowiednio wartości 0, 1 i 2.

long long iter_fibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}

	long long a = 0;
	long long b = 1;
	int i = 2;
}

Zapisujemy pętlę while, która będzie wykonywać się tak długo, dopóki wartość zmiennej i jest mniejsza od wartości zmiennej n lub jej równa.

long long iter_fibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}

	long long a = 0;
	long long b = 1;
	int i = 2;
    
	while (i <= n) {
        
    }        
}

W każdym obiegu pętli while najpierw obliczamy i‑ty wyraz ciągu, czyli sumę dwóch poprzednich wyrazów ciągu. Wynik przypisujemy do zmiennej suma. Następnie aktualizujemy wartości zmiennych a i b. Zmiennej a przypisujemy wartość zmiennej b, a zmiennej b wartość zmiennej suma. Na końcu zwiększamy wartość zmiennej i o 1.

long long iter_fibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}

	long long a = 0;
	long long b = 1;
	int i = 2;
    
	while (i <= n) {
		long long suma = a + b;
		a = b;
		b = suma;
		i = i + 1;
	}    
    
	return b;
}

Po zakończeniu pętli wartość zmiennej b jest zwracana jako wynik działania funkcji.

Oto cały kod programu:

#include <iostream>
using namespace std;

long long iter_fibonacci(int n) {
    
    if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}

	long long a = 0;
	long long b = 1;
	int i = 2;

	while (i <= n) {
		long long suma = a + b;
		a = b;
		b = suma;
		i = i + 1;
	}

	return b;
}

int main() {
	cout << iter_fibonacci(3) << endl;
	return 0;
}

Słownik