Rekurencja w C++ — silnia, Fibonacci i wieże Hanoi ze śladem wywołań

Funkcja rekurencyjna wywołuje samą siebie z mniejszym problemem, aż dojdzie do przypadku, który rozwiązuje bez dalszych wywołań (przypadek bazowy). Na lekcji uczniowie oglądają ślad wywołań silni, liczą, ile razy wywoła się naiwny Fibonacci, i sprawdzają, że wieże Hanoi dla 10 dysków wymagają 1023 ruchów.

Scenariusz jest przeznaczony na 45 minut dla klasy po lekcji o liczbach pierwszych w C++ i funkcjach. Ten sam temat w Pythonie omawia lekcja o rekurencji.

Przygotowanie stanowisk

Potrzebny jest kompilator C++ (na przykład g++ z MinGW-w64, Code::Blocks lub Dev-C++) i edytor tekstu. Rozpakuj pakiet z sekcji materiałów do osobnego folderu. W folderze projektu skompiluj program poleceniem g++ -std=c++17 -Wall start.cpp -o program, a potem uruchom go: ./program (Linux, macOS) albo program.exe (Windows). W środowisku z przyciskiem Build and Run (Code::Blocks) wystarczy otworzyć plik .cpp i je użyć. Rozwiązanie jest w pliku rozwiazanie.cpp, zadanie dla chętnych — w rozszerzenie.cpp.

Cele i plan lekcji

Po zajęciach uczeń potrafi:

• wskazać przypadek bazowy i krok rekurencyjny;
• odczytać ślad wywołań funkcji rekurencyjnej;
• policzyć liczbę wywołań naiwnego Fibonacciego;
• zapisać rekurencyjnie sumę cyfr i potęgę;
• wyjaśnić działanie wież Hanoi i wzór 2^n − 1.

Przypadek bazowy i krok

W silnia(n) przypadkiem bazowym jest n <= 1 (wynik 1), a krokiem — n * silnia(n - 1). Bez przypadku bazowego funkcja wywoływałaby się w nieskończoność, aż skończy się pamięć stosu. Ślad wywołań pokazuje, że funkcje „schodzą w dół” do silnia(1), a potem zwracają wyniki „w górę”.

Fibonacci i koszt

fib(n) = fib(n−1) + fib(n−2) jest elegancki, ale wołany naiwnie liczy te same wartości wielokrotnie. Dla fib(10) funkcja wywołuje się aż 177 razy, chociaż wynik to tylko 55. Zliczanie wywołań licznikiem globalnym pokazuje, jak szybko rośnie koszt.

Wieże Hanoi

Aby przenieść n dysków z A na C: przenieś n−1 dysków na B, przenieś największy na C, przenieś n−1 dysków z B na C. Liczba ruchów to 2^n − 1: 7 dla 3 dysków, 1023 dla 10.

Zadania

Zadanie 1. Ślad silni. Napisz silniaZeSladem(n, poziom), która wypisuje wcięciem kolejne wywołania i wyniki, i wywołaj ją dla 4.

Zadanie 2. Trzy funkcje. Napisz fib, sumaCyfr i potega rekurencyjnie. Wypisz fib(10) wraz z liczbą wywołań, sumę cyfr liczby 12345 i 2^10.

Zadanie 3. Hanoi. Wypisz ruchy dla 3 dysków i policz ruchy dla 3 oraz 10 dysków.

Dla chętnych: napisz rekurencyjną funkcję nwd(a, b) (plik rozszerzenie.cpp).

Rozwiązanie i wyniki

#include <iostream>
#include <string>
using namespace std;

int wywolania = 0;

int silniaZeSladem(int n, int poziom) {
    cout << string(poziom * 2, ' ') << "silnia(" << n << ")" << endl;
    if (n <= 1) {
        return 1;
    }
    int wynik = n * silniaZeSladem(n - 1, poziom + 1);
    cout << string(poziom * 2, ' ') << "wynik " << wynik << endl;
    return wynik;
}

int fib(int n) {
    wywolania++;
    if (n < 2) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

int sumaCyfr(int n) {
    if (n < 10) {
        return n;
    }
    return n % 10 + sumaCyfr(n / 10);
}

int potega(int podstawa, int wykladnik) {
    if (wykladnik == 0) {
        return 1;
    }
    return podstawa * potega(podstawa, wykladnik - 1);
}

int liczbaRuchow = 0;

void hanoi(int n, char z, char na, char pomocniczy, bool pokaz) {
    if (n == 0) {
        return;
    }
    hanoi(n - 1, z, pomocniczy, na, pokaz);
    liczbaRuchow++;
    if (pokaz) {
        cout << "dysk " << n << ": " << z << " -> " << na << endl;
    }
    hanoi(n - 1, pomocniczy, na, z, pokaz);
}

int main() {
    // Zadanie 1: silnia ze sladem wywolan
    int w = silniaZeSladem(4, 0);
    cout << "wynik: " << w << endl;

    // Zadanie 2: Fibonacci, suma cyfr, potega
    cout << "fib(10) = " << fib(10) << ", wywolan: " << wywolania << endl;
    cout << "suma cyfr 12345 = " << sumaCyfr(12345) << ", 2^10 = " << potega(2, 10) << endl;

    // Zadanie 3: wieze Hanoi
    hanoi(3, 'A', 'C', 'B', true);
    cout << "ruchow dla 3 dyskow: " << liczbaRuchow << endl;
    liczbaRuchow = 0;
    hanoi(10, 'A', 'C', 'B', false);
    cout << "ruchow dla 10 dyskow: " << liczbaRuchow << endl;
    return 0;
}

Program wypisze:

silnia(4)
  silnia(3)
    silnia(2)
      silnia(1)
    wynik 2
  wynik 6
wynik 24
wynik: 24
fib(10) = 55, wywolan: 177
suma cyfr 12345 = 15, 2^10 = 1024
dysk 1: A -> C
dysk 2: A -> B
dysk 1: C -> B
dysk 3: A -> C
dysk 1: B -> A
dysk 2: B -> C
dysk 1: A -> C
ruchow dla 3 dyskow: 7
ruchow dla 10 dyskow: 1023

Zadanie dla chętnych (rozszerzenie.cpp):

#include <iostream>
using namespace std;

int nwd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return nwd(b, a % b);
}

int main() {
    cout << nwd(48, 18) << " " << nwd(17, 5) << endl;
    return 0;
}

Wynik:

6 1

Programy kompilowano kompilatorem g++ 15.2 z opcjami -std=c++17 -Wall -Wextra, bez ostrzeżeń.

Typowe błędy

Pytania kontrolne i punktacja

1. Co to jest przypadek bazowy i po co on jest?
2. Dlaczego fib(10) wywołuje się 177 razy?
3. Ile ruchów potrzeba dla 10 dysków i dlaczego?

Odpowiedzi: To przypadek rozwiązywany bez kolejnego wywołania; zatrzymuje rekurencję. Bo każde wywołanie rozgałęzia się na dwa i te same wartości są liczone wielokrotnie. 1023, bo liczba ruchów to 2^n − 1.

Proponowana punktacja (razem 10 punktów): zadanie 1 — ślad i wynik 3 pkt; zadanie 2 — trzy funkcje 3 pkt, liczba wywołań 1 pkt; zadanie 3 — ruchy i liczniki 2 pkt; pytania kontrolne 1 pkt. Zadanie dla chętnych nie jest wymagane do pełnej oceny.

Materiały do pobrania

• Pakiet C++: materiały do lekcji, rozwiązanie i karta pracy
• Karta pracy ucznia — otwórz i wydrukuj

Rozpakuj ZIP przed otwarciem plików. Materiały są dostępne bez logowania; publiczne rozwiązanie służy nauce i samodzielnemu sprawdzeniu, a nie poufnemu sprawdzianowi.

Co dalej?

Następny krok to dziedziczenie i polimorfizm. Ten materiał rozwija dział o algorytmach w kursie C++ w TablicaPro, gdzie znajdziesz prezentacje, ćwiczenia i testy do prowadzenia lekcji.

Źródła techniczne: Rekurencja w Wikipedii oraz Wieże Hanoi w Wikipedii. Zobacz też lekcję o funkcjach w C++.