20.3 -- Rekurencja

A funkcja rekurencyjna w C++ to funkcja, która wywołuje samą siebie. Oto przykład źle napisanej funkcji rekurencyjnej:

#include <iostream>

void countDown(int count)
{
    std::cout << "push " << count << '\n';
    countDown(count-1); // countDown() calls itself recursively
}

int main()
{
    countDown(5);

    return 0;
}

Gdy wywoływana jest funkcja countDown(5), wypisywane jest „push 5” i wywoływana jest funkcja countDown(4). countDown(4) wypisuje „push 4” i wywołuje funkcję countDown(3). countDown(3) wypisuje „push 3” i wywołuje funkcję countDown(2). Sekwencja wywołania funkcji countDown(n) countDown(n-1) jest powtarzana w nieskończoność, tworząc w efekcie rekurencyjny odpowiednik nieskończonej pętli.

W lekcji 20.2 — Stos i sterta, nauczyłeś się, że każde wywołanie funkcji powoduje umieszczenie danych na stosie wywołań. Ponieważ funkcja countDown() nigdy nie zwraca (po prostu ponownie wywołuje funkcję countDown()), informacja ta nigdy nie jest usuwana ze stosu! W rezultacie w pewnym momencie w komputerze zabraknie pamięci stosu, nastąpi przepełnienie stosu, a program ulegnie awarii lub zakończy działanie. Na maszynie autora program ten odliczał do -11732 przed zakończeniem!

Warunki zakończenia rekurencyjnego

Rekurencyjne wywołania funkcji działają zazwyczaj tak samo jak normalne wywołania funkcji. Jednakże powyższy program ilustruje najważniejszą różnicę w stosunku do funkcji rekurencyjnych: musisz uwzględnić warunek zakończenia rekurencyjnego, w przeciwnym razie będą one działać „na zawsze” (właściwie do momentu wyczerpania się pamięci stosu wywołań). A Zakończenie rekurencyjne to warunek, którego spełnienie powoduje, że funkcja rekurencyjna przestanie się wywoływać.

Zakończenie rekurencyjne zazwyczaj wiąże się z użyciem instrukcji if. Oto nasza funkcja przeprojektowana z warunkiem zakończenia (i dodatkowymi wynikami):

#include <iostream>

void countDown(int count)
{
    std::cout << "push " << count << '\n';

    if (count > 1) // termination condition
        countDown(count-1);

    std::cout << "pop " << count << '\n';
}

int main()
{
    countDown(5);
    return 0;
}

Teraz, gdy uruchomimy nasz program, funkcja countDown() rozpocznie się od wygenerowania następującego komunikatu:

push 5
push 4
push 3
push 2
push 1

Gdybyś spojrzał na stos wywołań w tym momencie, zobaczyłbyś co następuje:

countDown(1)
countDown(2)
countDown(3)
countDown(4)
countDown(5)
main()

Ze względu na warunek zakończenia, countDown(1) nie wywołuje funkcji countDown(0) - zamiast tego instrukcja „if” nie wykonaj, więc wypisuje „pop 1”, a następnie kończy. W tym momencie funkcja countDown(1) jest usuwana ze stosu, a sterowanie powraca do funkcji countDown(2). countDown(2) wznawia wykonywanie od momentu wywołania countDown(1), więc wypisuje „pop 2”, a następnie kończy. Wywołania funkcji rekurencyjnych są następnie usuwane ze stosu, aż wszystkie wystąpienia funkcji countDown zostaną usunięte.

W ten sposób łączna liczba wyników tego programu:

push 5
push 4
push 3
push 2
push 1
pop 1
pop 2
pop 3
pop 4
pop 5

Warto zauważyć, że dane wyjściowe typu „push” są wykonywane w kolejności do przodu, ponieważ występują przed wywołaniem funkcji rekurencyjnej. Wyniki „pop” występują w odwrotnej kolejności, ponieważ występują po wywołaniu funkcji rekurencyjnej, gdy funkcje są zdejmowane ze stosu (co dzieje się w odwrotnej kolejności, w jakiej zostały umieszczone).

Bardziej przydatny przykład

Teraz, gdy omówiliśmy podstawową mechanikę wywołań funkcji rekurencyjnych, przyjrzyjmy się innej funkcji rekurencyjnej, która jest nieco bardziej typowe:

// return the sum of all the integers between 1 (inclusive) and sumto (inclusive)
// returns 0 for negative numbers
int sumTo(int sumto)
{
    if (sumto <= 0)
        return 0; // base case (termination condition) when user passed in an unexpected argument (0 or negative)
    if (sumto == 1)
        return 1; // normal base case (termination condition)

    return sumTo(sumto - 1) + sumto; // recursive function call
}

Programy rekurencyjne są często trudne do zrozumienia po prostu na nie patrząc. Często pouczające jest sprawdzenie, co się stanie, gdy wywołamy funkcję rekurencyjną z określoną wartością. Zobaczmy więc, co się stanie, gdy wywołamy tę funkcję z parametrem sumto = 5.

sumTo(5) called, 5 <= 1 is false, so we return sumTo(4) + 5.
sumTo(4) called, 4 <= 1 is false, so we return sumTo(3) + 4.
sumTo(3) called, 3 <= 1 is false, so we return sumTo(2) + 3.
sumTo(2) called, 2 <= 1 is false, so we return sumTo(1) + 2.
sumTo(1) called, 1 <= 1 is true, so we return 1.  This is the termination condition.

Teraz odwijamy stos wywołań (usuwając każdą funkcję ze stosu wywołań po powrocie):

sumTo(1) returns 1.
sumTo(2) returns sumTo(1) + 2, which is 1 + 2 = 3.
sumTo(3) returns sumTo(2) + 3, which is 3 + 3 = 6.
sumTo(4) returns sumTo(3) + 4, which is 6 + 4 = 10.
sumTo(5) returns sumTo(4) + 5, which is 10 + 5 = 15.

W tym momencie łatwiej zauważyć, że dodajemy liczby od 1 do przekazanej wartości (włącznie).

Ponieważ funkcje rekurencyjne mogą być trudne do zrozumienia, patrząc na nie, szczególnie ważne są dobre komentarze.

Zauważ, że w powyższym kodzie powtarzamy z wartością sumto - 1 zamiast --sumto. Robimy to, ponieważ operator-- ma efekt uboczny, a użycie zmiennej, która ma efekt uboczny zastosowany więcej niż raz w danym wyrażeniu, spowoduje niezdefiniowane zachowanie. Użycie sumto - 1 pozwala uniknąć skutków ubocznych, dzięki czemu sumto można bezpiecznie używać więcej niż raz w wyrażeniu.

Algorytmy rekurencyjne

Funkcje rekurencyjne zazwyczaj rozwiązują problem, najpierw znajdując rozwiązanie podzbioru problemu (rekurencyjnie), a następnie modyfikując to podrozwiązanie w celu uzyskania rozwiązania. W powyższym algorytmie sumTo(wartość) najpierw rozwiązuje sumTo(wartość-1), a następnie dodaje wartość zmiennej wartość, aby znaleźć rozwiązanie dla sumTo(wartość).

W wielu algorytmach rekurencyjnych niektóre dane wejściowe dają trywialne wyniki. Na przykład sumTo(1) daje trywialny wynik 1 (możesz to obliczyć w głowie) i nie korzysta z dalszej rekurencji. Dane wejściowe, dla których algorytm w trywialny sposób generuje wynik, nazywane są przypadkiem podstawowym. Przypadki podstawowe pełnią rolę warunków zakończenia algorytmu. Przypadki podstawowe można często zidentyfikować, biorąc pod uwagę dane wyjściowe dla wartości wejściowych 0, 1, „”, ” lub wartości null.

Liczby Fibonacciego

Jednym z najbardziej znanych matematycznych algorytmów rekurencyjnych jest ciąg Fibonacciego. Ciągi Fibonacciego pojawiają się w wielu miejscach w przyrodzie, takich jak rozgałęzienia drzew, spirala muszli, zawiązki ananasa, rozwijający się liść paproci, i układ szyszki.

Oto obraz spirali Fibonacciego:

Każda z liczb Fibonacciego to długość boku kwadratu, w którym dana liczba się pojawia.

Liczby Fibonacciego są definiowane matematycznie jako:

W rezultacie napisanie (niezbyt wydajnej) funkcji rekurencyjnej do obliczenia n-tej liczby Fibonacciego jest raczej proste:

#include <iostream>

int fibonacci(int count)
{
    if (count == 0)
        return 0; // base case (termination condition)
    if (count == 1)
        return 1; // base case (termination condition)
    return fibonacci(count-1) + fibonacci(count-2);
}

// And a main program to display the first 13 Fibonacci numbers
int main()
{
    for (int count { 0 }; count < 13; ++count)
        std::cout << fibonacci(count) << ' ';

    return 0;
}

Uruchomienie programu daje następujące wyniki wynik:

0 1 1 2 3 5 8 13 21 34 55 89 144

Jak zauważysz, są to dokładnie liczby pojawiające się na diagramie spirali Fibonacciego.

Algorytmy zapamiętywania

Powyższy rekurencyjny algorytm Fibonacciego nie jest zbyt wydajny, po części dlatego, że każde wywołanie przypadku innego niż podstawowy skutkuje dwoma kolejnymi wywołaniami Fibonacciego. Daje to wykładniczą liczbę wywołań funkcji (w rzeczywistości powyższy przykład wywołań fibonacci() 1205 razy!). Istnieją techniki, które można zastosować w celu zmniejszenia liczby niezbędnych wywołań. Jedna technika, zwana zapamiętywaniem, buforuje wyniki kosztownych wywołań funkcji, dzięki czemu wynik może zostać zwrócony, gdy ponownie wystąpią te same dane wejściowe.

Oto zapamiętana wersja rekurencyjnego algorytmu Fibonacciego:

#include <iostream>
#include <vector>

// h/t to potterman28wxcv for a variant of this code
// count is now a std::size_t to make indexing the std::vector easier
int fibonacci(std::size_t count)
{
	// We'll use a static std::vector to cache calculated results
	static std::vector results{ 0, 1 };

	// If we've already seen this count, then use the cache'd result
	if (count < std::size(results))
		return results[count];

	// Otherwise calculate the new result and add it
	results.push_back(fibonacci(count - 1) + fibonacci(count - 2));
	return results[count];   
}

// And a main program to display the first 13 Fibonacci numbers
int main()
{
	for (int count { 0 }; count < 13; ++count)
		std::cout << fibonacci(static_cast<std::size_t>(count)) << ' ';

	return 0;
}

To zapamiętane wersja wykonuje 35 wywołań funkcji, czyli znacznie lepiej niż 1205 w oryginalnym algorytmie.

Rekurencyjne a iteracyjne

Jedno często zadawane pytanie dotyczące funkcji rekurencyjnych brzmi: „Po co używać funkcji rekurencyjnej, skoro można wykonać wiele tych samych zadań iteracyjnie (używając pętlę for lub while pętla)?” Okazuje się, że zawsze można rozwiązać problem rekurencyjny iteracyjnie — jednak w przypadku nietrywialnych problemów wersja rekurencyjna jest często znacznie łatwiejsza do napisania (i odczytania). Na przykład, chociaż możliwe jest napisanie funkcji Fibonacciego w sposób iteracyjny, jest to nieco trudniejsze! (Spróbuj!)

Funkcje iteracyjne (te, które korzystają z pętli for lub while) są prawie zawsze bardziej wydajne niż ich rekurencyjne odpowiedniki wypychanie i otwieranie ramek stosu wiąże się z pewnym obciążeniem. Funkcje iteracyjne pozwalają uniknąć tego narzutu.

Nie oznacza to, że funkcje iteracyjne są zawsze lepszym wyborem. Czasami rekurencyjna implementacja funkcji jest o wiele czystsza i łatwiejsza do naśladowania, że poniesienie dodatkowego narzutu jest więcej niż tego warte ze względu na korzyści w zakresie łatwości konserwacji, szczególnie jeśli algorytm nie musi powtarzać się zbyt wiele razy, aby znaleźć rozwiązanie.

Ogólnie rzecz biorąc, rekurencja jest dobrym wyborem, gdy spełniona jest większość z poniższych:

• Kod rekurencyjny jest znacznie prostszy w implementacji.
• Rekursja głębokość może być ograniczona (np. nie ma możliwości podania danych wejściowych, które spowodują rekursję w dół o 100 000 poziomów).
• Wersja iteracyjna algorytmu wymaga zarządzania stosem danych.
• To nie jest sekcja kodu o krytycznym znaczeniu dla wydajności.

Jeśli jednak algorytm rekurencyjny jest prostszy w implementacji, sensowne może być rozpoczęcie od rekurencji, a następnie optymalizacja do algorytmu iteracyjnego później.

Czas quizu

1. Silnia liczby całkowitej N (zapisanej jako N!) jest definiowana jako iloczyn (mnożenie) wszystkich liczb od 1 do N (0! = 1). Napisz funkcję rekurencyjną o nazwie silnia, która zwraca silnię danych wejściowych. Przetestuj to na pierwszych 7 silniach.

Wskazówka: Pamiętaj, że (x * y) = (y * x), więc iloczyn wszystkich liczb od 1 do N jest taki sam, jak iloczyn wszystkich liczb od N do 1.

Pokaż rozwiązanie

#include <iostream>

int factorial(int n)
{
	if (n <= 0)
		return 1;

	return factorial(n - 1) * n;
}

int main()
{
	for (int count { 0 }; count < 7; ++count)
		std::cout << factorial(count) << '\n';
}

2. Napisz funkcję rekurencyjną, która jako dane wejściowe przyjmuje liczbę całkowitą i zwraca sumę każdej pojedynczej cyfry tej liczby całkowitej (np. 357 = 3 + 5 + 7 = 15). Wydrukuj odpowiedź dla wejścia 93427 (czyli 25). Załóżmy, że wartości wejściowe są dodatnie.

Pokaż rozwiązanie

#include <iostream>

int sumDigits(int x)
{
	if (x < 10)
		return x;

	return sumDigits(x / 10) + x % 10;
}

int main()
{
	std::cout << sumDigits(93427);
}

3a) To jest nieco trudniejsze. Napisz program, który poprosi użytkownika o wprowadzenie dodatniej liczby całkowitej, a następnie użyje funkcji rekurencyjnej w celu wydrukowania binarnej reprezentacji tej liczby. Użyj metody 1 z lekcji O.4 -- Konwersja liczb całkowitych pomiędzy reprezentacją binarną i dziesiętną.

Wskazówka: Używając metody 1, chcemy wydrukować bity w odwrotnej kolejności. Oznacza to, że instrukcja print powinna być po wywołaniem rekurencyjnym.

Pokaż rozwiązanie

#include <iostream>

// h/t to reader Gapo for this solution
void printBinary(int x)
{
        // Termination case
	if (x == 0)
		return;
	
	// Recurse to the next bit
	printBinary(x / 2);

	// Print out the remainders (in reverse order)
	std::cout << x % 2;
}

int main()
{
	int x;
	std::cout << "Enter a positive integer: ";
	std::cin >> x;

	printBinary(x);
}

3b) Dodatkowy kredyt: zaktualizuj swój kod z 3a, aby obsłużyć przypadek, w którym użytkownik może wprowadzić 0 lub liczbę ujemną.

Oto przykładowe wyjście (zakładając 32-bitowe liczby całkowite):

Enter an integer: -15
11111111111111111111111111110001

Wskazówka: Twoja funkcja printBinary() w rzeczywistości nie musi obsługiwać liczby ujemne. Jeśli przekażesz jej wartość dodatnią z tą samą reprezentacją binarną co liczba ujemna, otrzymasz poprawny wynik.

Pokaż wskazówkę

Pokaż wskazówkę

Pokaż rozwiązanie

// h/t to reader Donlod for this solution
#include <iostream>

void printBinary(unsigned int n)
{
	if (n > 1) // we only recurse if n > 1, so this is our termination case for n == 0
	{
		printBinary(n / 2);
	}

	std::cout << n % 2;
}

int main()
{
	int x{};
	std::cout << "Enter an integer: ";
	std::cin >> x;

	printBinary(static_cast<unsigned int>(x));
}