Funkcję wywołujemy poprzez jej nazwę, umieszczając w nawiasach wartości dla kolejnych parametrów.

// Funkcje
//------------------------

#include <iostream>

using namespace std;

// Funkcja zwraca NWD dwóch liczb a i b
//-------------------------------------

int nwd(unsigned a, unsigned b)
{
  while(b != a)
  {
      if(a > b) a = a - b;
      else      b = b - a;
  }
  return a;
}

int main()
{
  cout << nwd(36,24) << endl
       << nwd(36,64) << endl;

  return 0;
}

Funkcje mogą otrzymywać informację za pomocą parametrów, które wewnątrz funkcji wyglądają jak zmienne. Parametry są przekazywane na dwa sposoby:

• przez wartość
• przez referencję

Przekazywanie przez wartość oznacza, że funkcja otrzymuje w swoim parametrze wartość wyrażenia, które zostanie umieszczone w wywołaniu funkcji przez wywołujący ją program. Przykładem jest poprzednio napisana funkcja nwd. W parametrach a i b otrzymuje ona wartości dwóch liczb, dla których wyznacza największy wspólny dzielnik. Przeanalizujmy poniższy program:

// Funkcje
//------------------------

#include <iostream>

using namespace std;

void cosik(int a)
{
  cout << "Funkcja: " << a << endl;
}

int main()
{
  int x = 15;

  cout << "Program: " << x << endl;
  cosik(x);
  cosik(x+15);
  cosik(x+255);
  cout << "Program: " << x << endl;
  return 0;
}

W funkcji głównej tworzymy zmienną x i nadajemy jej wartość 15. Program wyświetla zawartość tej zmiennej x, po czym wywołuje funkcję cosik, przekazując jej w parametrze a wartość x. Funkcja wyświetla to, co otrzymała w swoim parametrze i kończy działanie. Następuje drugie wywołanie cosik, ale teraz w parametrze a otrzyma ona zawartość x powiększoną o 15, czyli 30. Zauważ, iż wyrażenie x+15 jest obliczane zanim zostanie wywołana funkcja. W kolejnym wywołaniu funkcja cosik otrzyma w swoim parametrze wartość x powiększoną o 255, czyli 270. Na koniec program wyświetla jeszcze raz zawartość zmiennej x. Na wyjściu otrzymamy zatem:

Zmieńmy nieco program:

// Funkcje
//------------------------

#include <iostream>

using namespace std;

void cosik(int a)
{
  a = a * a;
  cout << "Funkcja: " << a << endl;
}

int main()
{
  int x = 15;

  cout << "Program: " << x << endl;
  cosik(x);
  cout << "Program: " << x << endl;
  return 0;
}

Teraz funkcja cosik wyznacza kwadrat otrzymanego parametru i wyświetla wartość tego kwadratu. W funkcji głównej tworzymy zmienną x i nadajemy jej wartość 15. Następnie wyświetlamy wartość x, wywołujemy funkcję cosik z wartością x jako parametrem i na koniec ponownie wyświetlamy zawartość x. Jako wynik działania otrzymamy:

Parametr a zmienił się w funkcji cosik na kwadrat, lecz nie wpłynęło to na zmianę zawartości zmiennej x, która dalej pozostała równa 15 po powrocie z funkcji cosik. Wynika z tego, że przy przekazywaniu parametru przez wartość funkcja może zrobić z otrzymanym parametrem cokolwiek, ale będzie to miało znaczenie tylko wewnątrz tej funkcji.

Dane do funkcji możemy również przekazywać przez referencję. W tym przypadku funkcja nie otrzymuje wartości danej, lecz samą daną, np. zmienną. Jeśli ją zmieni, to zmiana ta pozostanie w zmiennej również po zakończeniu działania funkcji.

// Funkcje
//------------------------

#include <iostream>

using namespace std;

void cosik(int & a)  // Parametr przekazywany przez referencję
{
  a *= a;
  cout << "Funkcja: " << a << endl;
}

int main()
{
  int x = 15;

  cout << "Program: " << x << endl;
  cosik(x);
  cout << "Program: " << x << endl;
  return 0;
}

W programie dodaliśmy tylko jeden znak '&' przed nazwę parametru funkcji cosik. Znak ten jest w C++ operatorem referencji. Referencja oznacza, że parametr a nie jest wartością jakiegoś wyrażenia, lecz obiektem, który został udostępniony funkcji jako parametr. Funkcja cosik wyznacza kwadrat tego, co zawiera przekazany obiekt, czyli x. Obliczony kwadrat jest wstawiany z powrotem do otrzymanego obiektu, który wewnątrz funkcji cosik nosi nazwę a. Dlatego po powrocie z wywołania zmienna x zawiera kwadrat swojej początkowej wartości.

Referencja jest przydatna przy wielu okazjach. Na przykład, jest ona jednym ze sposobów zwracania przez funkcję więcej niż jednej wartości.

// Funkcje
// (C)2014 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

void cosik(int a, int b, int & wd, int & rd)
{
  wd = a / b;
  rd = a % b;
}

int main()
{
  int i,w,r;

  for(i = 2; i <= 9; i++)
  {
     cosik(20 - i, i, w, r);
     cout << 20 - i << " : " << i << " = " << w << " i reszta " << r << endl;
  }
  return 0;
}

W powyższym przykładzie funkcja cosik przyjmuje cztery parametry. Dwa pierwsze są przekazywane przez wartość, a dwa kolejne przez referencję. Wynik jest następujący:

Podsumowując:

Parametr przekazywany przez wartość jest liczbą, którą otrzymuje funkcja od programu głównego. Z otrzymaną w ten sposób liczbą funkcja może zrobić cokolwiek i jest to działanie lokalne wewnątrz funkcji. Parametr przekazywany przez wartość może być wynikiem wyrażenia, który komputer oblicza i przekazuje do funkcji w postaci liczby.

Parametr przekazywany przez referencję jest wypożyczonym obiektem. Jeśli funkcja zmieni ten obiekt, to zmiana ta będzie również widoczna w programie, który dany obiekt wypożyczył. Parametr przekazywany przez referencję musi być zmienną.

Zmienne tworzone wewnątrz zakresu funkcji są zmiennymi lokalnymi. Ich przestrzeń życiowa ogranicza się do wnętrza funkcji, w której zostały utworzone. Przeanalizujmy poniższy program:

// Funkcje
// (C)2014 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

void cosik()
{
  int x = 555; // Zmienna lokalna dla cosik
  cout << "Funkcja: " << x << endl;
}

int main()
{
  int x = 111; // Zmienna lokalna dla main
  cout << "Program: " << x << endl;
  cosik();
  cout << "Program: " << x << endl;
  return 0;
}

Funkcja cosik (tym razem bez parametrów) tworzy zmienną x i nadaje jej wartość 555, co potwierdza wypisaniem odpowiedniego tekstu w oknie konsoli. Funkcja main również tworzy sobie zmienną o nazwie x i nadaje jej wartość 111, po czym wypisuje ją w oknie konsoli, wywołuje funkcję cosik i jeszcze raz wypisuje zawartość swojej zmiennej x. Otrzymujemy:

Widzimy więc jasno, że wewnątrz funkcji x ma inną wartość niż poza nią. Staje się to oczywiste, gdy przyjmiemy do wiadomości, że są to dwie różne zmienne, które mają tę samą nazwę. Jednak nie ma tutaj niejednoznaczności, ponieważ ich przestrzenie życiowe (czyli zakresy) są różne. Jedna zmienna x żyje wewnątrz funkcji cosik, a ta druga wewnątrz funkcji main. Pierwszej nadano wartość 555, a drugiej 111. Gdy wywołamy funkcję cosik, to będzie ona korzystała ze swojej zmiennej x, czyli tej o wartości 555. Natomiast funkcja main posiada swoją zmienną x o wartości 111. W obu przypadkach są to zmienne lokalne dla cosik i main.

Inna sytuacja wystąpi w poniższym programie:

// Funkcje
//------------------------

#include <iostream>

using namespace std;

int x; // Zmienna globalna

void cosik()
{
  x = 555;
  cout << "Funkcja: " << x << endl;
}

int main()
{
  x = 111;
  cout << "Program: " << x << endl;
  cosik();
  cout << "Program: " << x << endl;
  return 0;
}

Teraz nie tworzymy zmiennych wewnątrz funkcji, lecz na zewnątrz. Każda z funkcji zmienia zawartość zmiennej x. W funkcji main zmienna x otrzymuje wartość 111, po czym w funkcji cosik zmienna ta otrzymuje nową wartość 555 i po powrocie z cosik x wciąż tę wartość przechowuje. Dlatego otrzymujemy wynik:

W ten sposób zadeklarowana zmienna nazywa się zmienną globalną. Jest ona widoczna we wszystkich funkcjach poniżej swojej definicji – w naszym przypadku będą to obie funkcje cosik i main. Wspólna zmienna może być zarówno wygodna (np. pozwala zmniejszyć liczbę parametrów przekazywanych do funkcji) jak i niebezpieczna (przy dużej liczbie funkcji problemem może okazać się ich współpraca przy zmianach współdzielonej zmiennej globalnej). Fachowi programiści zalecają, aby nie używać zmiennych globalnych bez wyraźnej potrzeby. Na pewno mają rację.

Co się jednak stanie, jeśli w funkcji utworzymy zmienną lokalną o takiej samej nazwie jak zmienna globalna? Sprawdźmy:

// Funkcje
//------------------------

#include <iostream>

using namespace std;

int x; // Zmienna globalna

void cosik()
{
  int x = 555; // Zmienna lokalna
  cout << "Funkcja: " << x << endl;
}

int main()
{
  x = 111;
  cout << "Program: " << x << endl;
  cosik();
  cout << "Program: " << x << endl;
  return 0;
}

Jako wynik otrzymamy:

Wygląda na to, że funkcja cosik straciła dostęp do zmiennej globalnej x na rzecz zmiennej lokalnej x. Jest to zamierzone. Otóż zmienne lokalne zawsze przysłaniają zmienne globalne o tych samych nazwach. Jeśli w cosik stworzyliśmy zmienną lokalną x, to funkcja ta będzie się odwoływać do tej lokalnej zmiennej, a nie do x globalnego, które zostało przysłonięte przez x lokalne. Na pierwszy rzut oka wygląda to zagmatwanie, lecz jest zupełnie proste w momencie, gdy zrozumiemy i zapamiętamy tę regułę. Powstaje jedynie pytanie, jak odwołać się w takim przypadku do zmiennej globalnej? Musisz skorzystać z operatora zakresu ::

// Funkcje
//------------------------

#include <iostream>

using namespace std;

int x; // Zmienna globalna

void cosik()
{
  int x = 555; // Zmienna lokalna
  cout << "Funkcja: " << x << endl;
  ::x = 333;   // Zmiana zmiennej globalnej
}

int main()
{
  x = 111;
  cout << "Program: " << x << endl;
  cosik();
  cout << "Program: " << x << endl;
  return 0;
}

Teraz funkcja cosik zmienia również zawartość zmiennej globalnej x na 333, co uwidacznia się po powrocie do main.

Zasady gry w 13 są następujące:

W grze uczestniczy 2 graczy oraz 13 patyczków (mogą to być kamyczki, zapałki, szpatułki, itp.). Gracze wykonują na zmianę ruchy, które polegają na zabraniu od 1 do 3 patyczków. Grę przegrywa ten gracz, który będzie musiał wziąć ostatni patyczek.

W naszej wersji gry pierwszym graczem będzie człowiek, drugim będzie komputer. Gra rozpoczyna się od 13 patyczków (reprezentowanych przez pionowe kreski). Następnie komputer czeka na ruch człowieka, czyli zabranie od 1 do 3 patyczków przez gracza nr 1. Komputer zabiera swoje patyczki, również od 1 do 3. Aby wygrać grę komputer zawsze uzupełnia liczbę zabranych patyczków do 4. Np jeśli gracz 1 zabierze 1 patyczek, komputer zabierze 3, aby w sumie zniknęło 4 patyczki. Dlaczego tak? Zastanów się. Po trzech rundach zostanie: 13 - 4 - 4 - 4 = 1 patyczek, który będzie musiał zabrać gracz nr 1, przez co przegra.

Całą grę rozbijemy na kilka podzadań, które zrealizujemy jako funkcje. Dzięki temu program się uprości. Algorytm będzie następujący:

1. Powitanie
2. Przygotowanie rozgrywki
3. Wyświetlenie patyczków
4. Ruch gracza 1
5. Jeśli brak patyczków to koniec gry
   inaczej Ruch gracza 2
6. Idź do kroku 3

Uruchom Code::Blocks i utwórz nowy projekt konsoli, nazwij go gra13. W edytorze umieść plik main.cpp i wpisz:

// Gra w 13
// Imię Nazwisko Klasa
//--------------------

#include <iostream>

using namespace std;

int main()
{
 
    return 0;
}

Teraz musimy się zastanowić nad zmiennymi. Program musi przechowywać liczbę patyczków w grze, ilość patyczków zabieranych przez gracza 1 (człowieka) oraz informację o tym, czy gra się toczy. W funkcji main tworzymy zmienne:

int main()
{
    int gra = 1, patyczki = 13, r_gracza1

    setlocale(LC_ALL,"");

    return 0;
}

Dodajemy wywołanie funkcji setlocale(), aby przełączyć znaki konsoli na Windows 1250.

Teraz tworzymy resztę kodu funkcji main():

int main()
{
    int gra = 1, patyczki = 13, r_gracza1;

    setlocale(LC_ALL,"");

    powitanie();

    while (gra == 1)
    {
        pisz(patyczki);

        r_gracza1 = ruch_gracza1(patyczki);

        if(patyczki == 0) gra = koniec(patyczki);
        else ruch_komputera(r_gracza1,patyczki);
    }

    return 0;
}

W kodzie mamy następujące elementy:

Zmienne:
gra – określa, czy gra się toczy, czy nie.
patyczki – liczba patyczków w grze
r_gracza1 – liczba patyczków zabrana przez gracza nr 1

Funkcje:
setlocale() – ustawia w konsoli zestaw znaków Windows 1250, taki sam jaki używa Code::Blocks w systemie Windows
powitanie() – na początku gry wypisuje krótki tekst powitalny
pisz() – wypisuje patyczki
ruch_gracza1() – pobiera liczbę patyczków zabranych przez gracza nr 1. Modyfikuje ilość patyczków w grze
Jeśli po ruchu gracza nr 1 nie ma już patyczków, to funkcja koniec() wypisuje odpowiednią informację i pyta się, czy gracz nr 1 chce rozegrać nową grę. Jeśli tak, to funkcja zwraca 1, w przeciwnym razie zwraca 0 i program się kończy.
Jeśli liczba patyczków jest różna od 0, to ruch wykonuje komputer.

Wpiszmy ponad funkcją main() kolejne funkcje:

//--------------
void powitanie()
{
    cout << "Gra w trzynastkę" << endl
         << "----------------" << endl << endl;

}

Funkcja nic nie zwraca i nie potrzebuje danych od programu. Dlatego posiada typ void i pustą listę parametrów.

//--------------
void pisz(int p)
{
    int i;

    cout << "PATYCZKI: ";

    for(i = 0; i < p; i++) cout << "|";

    cout << endl;
}

Funkcja ma za zadanie wypisać w oknie konsoli pozostałe w grze patyczki. Funkcja nic nie zwraca, dlatego ma typ void. Do działania funkcja musi mieć informację o liczbie patyczków w grze. Otrzymuje ją w parametrze p.

//--------------
int ruch_gracza1(int &p)
{
    int mx = 3, r;

    if(mx > p) mx = p;

    do
    {
        cout << "Twój ruch: ";

        cin >> r;
    } while((r < 1) || (r > mx));

    p = p - r;

    return r;
}

Funkcja odczytuje liczbę patyczków zabieranych przez gracza nr 1. Liczbę tę zwraca jako swój wynik. Ponieważ funkcja modyfikuje liczbę patyczków w grze po wykonaniu ruchu przez gracza nr 1, dlatego musi mieć dostęp do zmiennej przechowującej tę liczbę i parametr ten zostaje przekazany do funkcji przez referencję.
Gracz nr 1 może zabrać maksymalnie 3 patyczki, jeśli jednak jest ich w grze mniej, to komputer musi ustalić maksymalną liczbę patyczków, które gracz nr 1 może zabrać. Wykorzystana tutaj jest zmienne lokalna mx (od max). Następnie w pętli komputer odczytuje ruch gracza do zmiennej lokalnej r dotąd, aż wprowadzi on dozwoloną liczbę patyczków: od 1 do mx. Gdy to zostanie ustalone, komputer zmniejsza liczbę patyczków o ruch gracza i zwraca ten ruch jako wynik funkcji.

//--------------
int koniec(int &p)
{
    int decyzja;

    cout << "Zabrałeś ostatni patyczek i przegrałeś partię." << endl << endl
         << "Chcesz zagrać jeszcze raz (0 = nie): ";

    cin >> decyzja;

    cout << endl;

    if(decyzja == 0)
    {
        cout << "Miłego dnia!" << endl << endl;
        return 0;
    }
    else
    {
        p = 13;
        cout << endl << endl;
        return 1;
    }
}

Kolejna funkcja jest wywoływana, gdy po ruchu gracza #1 liczba patyczków osiągnie 0, czyli gracz #1 zabierze ostatni patyczek. Oznacza to jego przegraną. Funkcja wypisuje odpowiedni tekst i pyta się gracza nr 1, czy chce kontynuować grę. Jeśli gracz da odpowiedź negatywną, funkcja wyświetli tekst pożegnalny i zwróci 0, co spowoduje wyjście z pętli while w funkcji main(), a zatem zakończy program. Jeśli gracz nr 1 da odpowiedź pozytywną, liczba patyczków zostanie zresetowana na 13 (dlatego funkcja musi mieć dostęp do zmiennej przechowującej ich liczbę i dostaje go poprzez argument p przekazywany przez referencję) i funkcja zwraca 1.

//--------------
void ruch_komputera(int x,int &p)
{
    cout << "Mój ruch: " << 4 - x << endl << endl;

    p = p - 4 + x;
}

Ostatnia funkcja wykonuje ruch komputera, uzupełniając do 4 ruch wykonany przez człowieka. Liczba patyczków w grze jest zmniejszana o ten ruch. Funkcja nic nie zwraca, dlatego ma typ void. W parametrze x funkcja otrzymuje informację o ruchu gracza nr 1. W parametrze p funkcja otrzymuje dostęp do liczby patyczków w grze.

Przykładowa partia:

Gra w trzynastkę
----------------

PATYCZKI: |||||||||||||
Twój ruch: 3
Mój ruch:  1

PATYCZKI: |||||||||
Twój ruch: 1
Mój ruch:  3

PATYCZKI: |||||
Twój ruch: 2
Mój ruch:  2

PATYCZKI: |
Twój ruch: 1
Zabrałeś ostatni patyczek i przegrałeś partię.

Chcesz zagrać jeszcze raz (0 = nie): 0

Miłego dnia!

Gotowy program należy uruchomić, usunąć błędy i przesłać do oceny plik main.cpp. W temacie listu umieszczamy swoje imię, nazwisko, klasę i kod G13.

• false – fałsz, liczbowo jest to zero.
• true – prawda, liczbowo jest to wartość różna od zera.

Wyrażenie logiczne jest wyrażeniem dającym w wyniku false lub true. Na przykład poniższy kod daje wyniki logiczne:

...
cout << 5 == 2 + 3 << endl; // true
cout << 12 > 50 << endl;    // false
...

W języku C++ dowolne wyrażenie można zinterpretować jako wyrażenie logiczne. Jeśli wynikiem wyrażenia jest dowolna liczba różna od zera, to wynik ten jest traktowany jak true. Jeśli wynikiem wyrażenia jest zero, to wynik ten jest traktowany jaj false. Dzięki tej prostej umowie można uprościć programy. Wypróbuj poniższy przykład:

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    int i;
    for(i = -3; i < 4; i++)
    {
        cout << setw(4) << i << ": ";
        if(i) cout << "true";
        else  cout << "false";
        cout << endl;
    }
    return 0;
}

Zapis if(i)...  else... czytaj: jeśli i różne od zera... inaczej ...

W programach można używać stałych true i false, które mają wartość liczbową: true → 1, false → 0.

Wartości logiczne true i false tworzą typ logiczny bool. Nazwa ta pochodzi od sławnego matematyka angielskiego George'a Boole'a, który jako pierwszy usystematyzował logikę i wprowadził rachunek logiczny podobny do rachunku arytmetycznego. W logice Boole'a mamy trzy funkcje podstawowe:

Alternatywa (ang. OR = LUB), zwana sumą logiczną z uwagi na pewne podobieństwo do sumowania. W języku C++ operator alternatywy ma postać ||. Jest to operator dwuargumentowy, tzn. że działa na dwóch wyrażeniach traktowanych jako wyrażenia logiczne (jeśli byłyby wyrażeniami innego typu, to pamiętaj, iż wyrażenie jest fałszywe, gdy ma wartość zero, a prawdziwe, gdy ma wartość różną od zera). Oznaczmy te wyrażenia jako a i b. Poniższa tabelka definiuje wynik alternatywy nad tymi wyrażeniami:

Zapamiętaj:

Alternatywa dwóch wyrażeń daje wynik false, gdy oba wyrażenia mają wynik false. Jeśli jedno z wyrażeń ma wynik true, to alternatywa daje wynik true.

Koniunkcja (ang. AND = I), zwana iloczynem logicznym posiada w języku C++ operator &&. Tabelka koniunkcji jest następująca:

Zapamiętaj:

Koniunkcja dwóch wyrażeń daje wynik false, gdy jedno z wyrażeń ma wartość false. Jeśli oba wyrażenia mają wartość true, to koniunkcja daje wynik true.

Negacja (ang. NOT = NIE), zwana zaprzeczeniem logicznym jest jednoargumentowa. Daje wynik odwrotny logicznie do wyniku wyrażenia. W języku C++ operator negacji ma postać !. Tabelka negacji jest naztępująca:

Typ logiczny bool pozwala nam tworzyć zmienne logiczne. Zmienna logiczna może przechowywać tylko wartości logiczne: 0 jako false i 1 jako true. Jeśli do zmiennej logicznej przypisujesz wartość wyrażenia, to wyrażenie to będzie potraktowane jako true (1), jeśli jest różne od zera i jako false (0), gdy jest równe zero.  Spróbuj wyjaśnić wyniki poniższego programu:

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    bool a,b;
    int i;
    for(i = -3; i < 4; i++)
    {
        a = i;
        b = (i == 0);
        cout << setw(4) << i << ": "
             << "a = " << a
             << " b = " << b << endl;
    }
    return 0;
}

Z wyrażeń logicznych korzysta w języku C++ wiele instrukcji:

if(wyrażenie_logiczne) ...
while(wyrażenie_logiczne) ...
do ... while(wyrażenie_logiczne);
for(... ;wyrażenie_logiczne; ...) ...

W klasie II napisaliśmy program sprawdzający, czy dana liczba jest pierwsza. Mając typ bool możemy napisać funkcję logiczną, która będzie zwracała wynik true, jeśli jej argument jest liczbą pierwszą, lub false, jeśli jest liczbą złożoną. Warto sobie przypomnieć sposób testowania na pierwszość:

// Szukanie liczb pierwszych
//--------------------------

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

bool jest_pierwsze(int a)
{
    if(a == 2) return true;
    if((a <= 1) || !(a % 2)) return false;
    int d;
    int g = sqrt(a);
    for(d = 3; d <= g; d = d + 2)
        if(!(a % d)) return false;
    return true;
}

int main()
{
    int i;
    for(i = 1; i < 1000; i++)
        if(jest_pierwsze(i)) cout << setw(4) << i;
    cout << endl;
    return 0;
}

   2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71
  73  79  83  89  97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409
 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659
 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809
 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941
 947 953 967 971 977 983 991 997

Dla przykładu rozważmy obliczanie wartości n!. Mamy następujący wzór:

0! = 1
Dla n > 0, n! =n × (n - 1)!

Zwróć uwagę, iż problem główny jest łatwo rozwiązywalny tutaj, jeśli n = 0 lub znamy rozwiązanie dla n - 1. Z kolei rozwiązanie dla n - 1 jest łatwe, gdy n - 1 = 0 lub znamy rozwiązanie dla n - 2.  W każdym z tych etapów n staje się coraz mniejsze, aż w końcu osiągnie 0, a wtedy rozwiązanie będzie oczywiste. Gdy mamy rozwiązanie dla 0, to, idąc z powrotem, znajdziemy rozwiązanie dla n. Prześledźmy to dla n = 5:

5! = 5 × 4! = 5 × 4 × 3! = 5 × 4 × 3 × 2! = 5 × 4 × 3 × 2 × 1! = 5 × 4 × 3 × 2 × 1 × 0! = 5 × 4 × 3 × 2 × 1 × 1 = 120

Tworząc funkcję rekurencyjną, należy w niej najpierw sprawdzić warunek zakończenia rekurencji, czyli przypadek, dla którego znane jest bezpośrednie rozwiązanie. W przeciwnym razie możemy otrzymać pętlę nieskończoną, co doprowadzi do awaryjnego przerwania programu wskutek zajęcia całej pamięci komputera – każde wywołanie funkcji powoduje umieszczenie w pamięci adresu miejsca w programie, do którego funkcja ma powrócić oraz zarezerwowanie pamięci na parametry i zmienne lokalne. Jeśli ciąg wywołań nie zostanie przerwany, to cała pamięć komputera zostanie zużyta i program zakończy się z błędem.

Wynika z tego następujący algorytm dla silni(n):

silnia(n):
K1: Jeśli n = 0, to zakończ z wynikiem 1
K2: Zakończ z wynikiem n × silnia(n - 1)

W kroku 1 sprawdzamy warunek zakończenia rekurencji.

Rekurencja powstaje w kroku 2. Zwróć uwagę, iż przy wywołaniu funkcji przekazywany argument musi być różny od argumentu otrzymanego, w przeciwnym razie również dojdzie do pętli nieskończonej i program zatrzyma się z błędem.

// Rekurencja
//-----------

#include <iostream>
#include <iomanip>

using namespace std;

long long int silnia(int n)
{
    if(!n) return 1;
    else   return n * silnia(n - 1);
}

int main()
{
    int i;
    for(i = 0; i < 21; i++)
        cout << setw(3) << i << "! = " << silnia(i) << endl;
    return 0;
}

Typ int oznacza liczbę całkowitą 32-bitową o zakresie około ±2 mld. Silnia bardzo szybko rośnie. Dlatego wprowadzamy nowy typ danych long long int, który w języku C++ oznacza liczbę 64 bitową o zakresie około ±9223372036 mld. Nawet tak duży zakres nie mieści 21!

Na podobnej zasadzie można stworzyć rekurencyjną funkcję liczącą sumę kolejnych n liczb naturalnych od 1 do n:

// Rekurencja
//-----------

#include <iostream>
#include <iomanip>

using namespace std;

int suma(int n)
{
    if(n == 1) return 1;
    else       return n + suma(n - 1);
}

int main()
{
    int i;
    for(i = 0; i < 100; i++)
        cout << "Suma " << setw(2) << i << " = " << setw(4) << suma(i) << endl;
    return 0;
}

Teraz pokażemy, jak skonstruować rekurencyjny algorytm Euklidesa. Algorytm Euklidesa znajduje największy wspólny dzielnik dwóch liczb naturalnych. Euklides oryginalnie chciał znaleźć wspólną miarę dwóch odcinków (zajmował się geometrią), czyli najdłuższy odcinek, który da się odłożyć całkowitą liczbę razy w obu odcinkach wejściowych:

Euklides zauważył, że wspólna miara odkłada się całkowitą liczbę razy również w różnicy tych dwóch odcinków. Zatem dłuższy odcinek zastępował różnicą tak długo, aż oba odcinki zrównały się długością. Wtedy ich długość była równa wspólnej mierze. Oto przykład:

Liczbowo wspólna miara jest największym wspólnym dzielnikiem obu liczb. Pierwsze podejście do algorytmu Euklidesa wykorzystuje bezpośrednio to spostrzeżenie:

nwd(a,b):
1: Dopóki a ≠ b, wykonuj krok 2
2: Jeśli a > b, to a ← a - b
    Inaczej           b ← b - a
3: Zakończ zwracając a

// Rekurencja
//-----------

#include <iostream>

using namespace std;

int nwd(int a, int b)
{
    while(a != b)
        if(a > b) a = a - b;
        else      b = b - a;
    return a;
}

int main()
{
    int i, a, b;
    for(i = 1; i < 10; i++)
    {
        a = i * 5;
        b = i * 7;
        cout << "nwd(" << a << "," << b << ") = " << nwd(a,b) << endl;
    }
    return 0;
}

Ten sposób obliczania nwd, chociaż poprawny, nie jest zbyt efektywny. Jeśli liczby a i b różnią się znacznie od siebie, to program może wykonać dużo odejmowań, zanim je zrówna. Tymczasem zauważmy, iż liczbę mniejszą można odjąć od większej tyle razy, ile ta mniejsza mieści się w większej. To, co pozostanie po odejmowaniu jest resztą z dzielenia. Liczbę większą zastępujemy mniejsza, a do mniejszej wpisujemy resztę z dzielenia. Operacje te wykonujemy dotąd, aż mniejsza liczba osiągnie zero, wtedy nwd jest w liczbie większej

Zatem drugi algorytm wygląda następująco:

nwd(a,b):
1: Dopóki b ≠ 0, wykonuj kroki 2...4
2:     reszta ← a modulo b
3:     a  ← b
4:     b  ← reszta
5: Zakończ zwracając a

// Rekurencja
//-----------

#include <iostream>

using namespace std;

int nwd(int a, int b)
{
    int r;
    while(b)
    {
       r = a % b;
       a = b;
       b = r;
    }
    return a;
}

int main()
{
    int i, a, b;
    for(i = 1; i < 10; i++)
    {
        a = i * 5;
        b = i * 7;
        cout << "nwd(" << a << "," << b << ") = " << nwd(a,b) << endl;
    }
    return 0;
}

Ten ostatni algorytm można przerobić w prosty sposób na postać rekurencyjną:

nwd(a,b)
1:    Jeśli b = 0, to zakończ z wynikiem a
       Inaczej            zakończ z wynikiem nwd(b, a % b)

// Rekurencja
//-----------

#include <iostream>

using namespace std;

int nwd(int a, int b)
{
    if(!b) return a;
    else   return nwd(b, a % b);
}

int main()
{
    int i,a,b;
    for(i = 1; i < 10; i++)
    {
        a = i * 5;
        b = i * 7;
        cout << "nwd(" << a << "," << b << ") = " << nwd(a,b) << endl;
    }
    return 0;
}

Tutaj rekurencja zastępuje nam pętlę, którą tak naprawdę jest. Osiągnięcie przez argument b wartości zero powoduje zakończenie rekurencji i zwrócenie wyniku.  Jeśli b jest różne od zera, to rekurencja jest kontynuowana (pętla wykonuje się dalej). W wywołaniu rekurencyjnym nwd parametr a zastępujemy parametrem b, a parametr b zastępujemy resztą z dzielenia a przez b.

Dzięki rekurencji program znacznie się uprościł, jednakże poprzednie rozwiązanie z pętlą jest szybsze pod względem wykonania i zajmuje mniej pamięci.