Pomoce:

Instalacja Code Blocks i tworzenie projektu aplikacji konsoli.
Wprowadzenie do języka C++, strumienie i zmienne
Komputer podejmuje decyzje
Pętle warunkowe
Pętla iteracyjna
algorytm Euklidesa

Rekurencja

Słowo rekurencja (również rekursja) wywodzi się z języka łacińskiego - recurrere = biec z powrotem. W algorytmice mówimy, że dany algorytm jest rekurencyjny, jeśli do rozwiązania pewnego problemu wykorzystuje on sam siebie. W programowaniu dana funkcja jest rekurencyjna, jeśli wywołuje samą siebie. Kolejne wywołania takiej funkcji nazywamy rekurencyjnym ciągiem wywołań. Ciąg ten nie może być nieskończony - każde wywołanie funkcji powoduje umieszczenie w pamięci komputera adresu powrotu, czyli miejsca w programie, do którego wraca procesor, gdy zakończy wykonywać kod funkcji. Ponieważ pamięć jest skończona, to nie można w niej umieścić nieskończenie wiele adresów powrotnych. Dlatego w rekurencji bardzo ważne jest określenie warunku, który kończy rekurencję - np. funkcja przestaje już dalej wywoływać samą siebie.

 

Rekurencyjna silnia

Silnia n! (ang. factorial of n) jest iloczynem kolejnych liczb naturalnych mniejszych lub równych n. Możemy ją zapisać w sposób rekurencyjny:

 

 

Wykorzystując ten wzór policzmy np. 5!:

 

 

Zwróć uwagę, iż w obliczeniach cofamy się od n = 5 do n = 0. Gdy osiągniemy 0, to rekurencja ustaje.

 

// Rekurencyjne wyznaczanie silni
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

unsigned silnia(unsigned n)
{
    if(n == 0) return 1;
    else       return n * silnia(n - 1);
}

int main()
{
    unsigned n;

    cin >> n;

    cout << n << "! = " << silnia(n) << endl << endl;
  
    return 0;
}

 

Silnia rośnie bardzo szybko. Już 13! przekroczy dopuszczalny zakres dla liczb typu unsigned (0...4mld). Zwróć uwagę, iż funkcja rekurencyjna jest bardzo prosta - to jest właśnie zaleta rekurencji.

 

Rekurencyjny Największy Wspólny Dzielnik

Algorytm Euklidesa możemy również zapisać w sposób rekurencyjny:

 

 

Może się to wydawać na pierwszy rzut oka dziwne, lecz tak właśnie działa algorytm Euklidesa z dzieleniem, który omawialiśmy wcześniej. Traktuje on liczbę b jako resztę z dzielenia a przez b. Jeśli reszta z dzielenia jest równa 0, to kończy zwracając a. Jeśli nie, to a zastępuje przez b, czyli obecną resztą z dzielenia, a b zastępuje nową resztą z dzielenia i znów wykonuje sam siebie aż do pożądanego skutku.

 

(a)   (b)   →   (b)   (a mod b)

 

// Rekurencyjne obliczanie NWD
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

unsigned NWD(unsigned a, unsigned b)
{
    if(b == 0) return a;
    else       return NWD(b, a % b) ;
}

int main()
{
    unsigned a, b;

    cin >> a >> b;

    cout << "NWD(" << a << "," << b << ") = " << NWD(a, b) << endl << endl;
  
    return 0;
}

 

Zwróć uwagę, iż ponownie funkcja NWD uprościła się dzięki rekurencji.

 

Liczby Fibonacciego

Liczby Fibonacciego powstają również rekurencyjnie:

 

 

Oto kilka początkowych liczb Fibonacciego:

 

 

Za wyjątkiem dwóch pierwszych, każda kolejna liczba Fibonacciego powstaje jako suma dwóch poprzednich liczb. Jeśli dla tych liczb zastosujemy metodę rekurencyjną, to, owszem, funkcja tworząca będzie prosta, lecz liczba wywołań rekurencyjnych może prześcignąć nasze wyobrażenia. Spróbujmy rozwinąć rekurencyjnie fib6 (na czerwono zaznaczono liczby Fibonacciego, które się dalej rozkładają rekurencyjnie):

 

fib6 = fib4 + fib5
fib6 = fib2 + fib3 + fib3 + fib4
fib6 = fib0 + fib1 + fib1 + fib2 + fib1 + fib2 + fib2 + fib3
fib6 = fib0 + fib1 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib2
fib6 = fib0 + fib1 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1

 

A teraz rozwinięcie rekurencyjne dla fib7:

 

fib7 = fib5 + fib6
fib7 = fib3 + fib4 + fib4 + fib5
fib7 = fib1 + fib2 + fib2 + fib3 + fib2 + fib3 + fib3 + fib4
fib7 = fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib2 + fib0 + fib1 + fib1 + fib2 + fib1 + fib2 + fib2 + fib3
fib7 = fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib2
fib7 = fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1
 

Jak widzimy, liczba wywołań lawinowo rośnie wraz ze wzrostem n. Taki przyrost nazywamy przyrostem wykładniczym. Niestety, ta cecha powoduje, iż obliczenie metodą rekurencyjną liczb Fibonacciego może być operacją bardzo czasochłonną dla dużych n.

 

// Rekurencyjne obliczanie liczb Fibonacciego
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

unsigned long long fib(int n)
{
    if(n <= 1) return n;
    else       return fib(n - 2) + fib(n - 1);
}

int main()
{
    int n;

    cin >> n;

    cout << "fib(" << n << ") = " << fib(n) << endl << endl;
  
    return 0;
}

 

Sprawdź działanie tego programu dla n = 40. Liczy parę sekund. Dla n = 50 możesz już stracić cierpliwość (czas ponad 7 minut - Celeron 2,8 GHz). A o wyliczeniu 90-tej liczby Fibonacciego zapomnij - człowiek tak długo nie żyje!

Widzimy zatem, iż rekurencja może czasami prowadzić do algorytmów, których czas wykonania jest tak długi, że praktycznie algorytm nigdy się nie kończy. Tymczasem liczby Fibonacciego można wyliczać znacznie efektywniej, wykorzystując zasady tzw. programowania dynamicznego (ang. dynamic programming).

W programowaniu dynamicznym algorytm wykorzystuje wyniki otrzymane w poprzednich krokach - obliczamy nową liczbę na podstawie dwóch poprzednich, a następnie zapamiętujemy dwie ostatnie liczby. Całość pracuje w pętli aż do wyznaczenia liczby Fibonacciego o pożądanym numerze.

 

// Dynamiczne obliczanie liczb Fibonacciego
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

unsigned long long fib(int n)
{
    if(n <= 1) return n;
    else
    {
        unsigned long long f0, f1, f;

        f0 = 0;
        f1 = 1;

        for(int i = 2; i <= n; i++)
        {
            f = f0 + f1;
            f0 = f1;
            f1 = f;
        }

        return f;
    }
}

int main()
{
    int n;

    cin >> n;

    cout << "fib(" << n << ") = " << fib(n) << endl << endl;
  
    return 0;
}

 

Teraz program prawie natychmiast liczy wartość liczby fib90 = 2880067194370816120. Wersja rekurencyjna potrzebowałaby do tego wieków...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.