Funkcje rekurencyjne w C++

1. Definicja rekurencji

Rekurencja to technika programistyczna, w której funkcja wywołuje samą siebie, aby rozwiązać problem poprzez rozbicie go na mniejsze podproblemy tego samego typu.

W języku C++ funkcje rekurencyjne są często wykorzystywane do:

  • obliczeń matematycznych,
  • przetwarzania struktur danych (drzewa, grafy),
  • algorytmów dziel i zwyciężaj,
  • generowania kombinacji i permutacji.

2. Elementy funkcji rekurencyjnej

Każda poprawna funkcja rekurencyjna musi zawierać dwa kluczowe elementy:

2.1 Warunek zakończenia (przypadek bazowy)

  • Określa, kiedy rekurencja ma się zatrzymać
  • Zapobiega nieskończonym wywołaniom
  • Zwykle jest to najprostszy możliwy przypadek problemu

2.2 Wywołanie rekurencyjne

  • Funkcja wywołuje samą siebie
  • Argumenty muszą przybliżać funkcję do przypadku bazowego

3. Ogólna postać funkcji rekurencyjnej w C++

4. Przykłady funkcji rekurencyjnych

4.1 Silnia liczby (n!)

Definicja matematyczna:

  • 0! = 1
  • n! = n * (n-1)!

Implementacja w C++:

4.2 Ciąg Fibonacciego

Definicja:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2)

Kod:

⚠️ Uwaga: ta implementacja jest nieefektywna dla dużych n.

4.3 Suma elementów tablicy

4.4 Potęgowanie liczby

5. Rekurencja bezpośrednia i pośrednia

5.1 Rekurencja bezpośrednia

Funkcja wywołuje samą siebie bezpośrednio.

5.2 Rekurencja pośrednia

Dwie lub więcej funkcji wywołuje się nawzajem.

6. Rekurencja a stos wywołań (stack)

  • Każde wywołanie funkcji jest zapisywane na stosie

  • Przechowywane są:

    • parametry funkcji
    • zmienne lokalne
    • adres powrotu

  • Po zakończeniu funkcji dane są usuwane ze stosu

Zbyt głęboka rekurencja może prowadzić do przepełnienia stosu (stack overflow).

7. Zalety i wady rekurencji

✅ Zalety

  • czytelny i elegancki kod,
  • naturalne odwzorowanie problemów matematycznych,
  • prostsza implementacja algorytmów drzewiastych.

❌ Wady

  • większe zużycie pamięci,
  • wolniejsze działanie niż iteracja,
  • ryzyko przepełnienia stosu.

8. Rekurencja vs iteracja

Rekurencja Iteracja
prostsza koncepcyjnie szybsza
łatwiejsza do zrozumienia mniejsze zużycie pamięci
ryzyko stack overflow brak ryzyka stack overflow

9. Optymalizacja rekurencji

9.1 Rekurencja ogonowa

Rekurencja, w której wywołanie rekurencyjne jest ostatnią instrukcją w funkcji.

⚠️ Kompilator C++ nie zawsze optymalizuje rekurencję ogonową.

9.2 Zapamiętywanie wyników (memoizacja)

Stosowane np. w Fibonaccim:

10. Zastosowania funkcji rekurencyjnych

  • algorytmy sortowania (QuickSort, MergeSort),
  • przeszukiwanie drzew i grafów (DFS),
  • generowanie kombinacji i permutacji,
  • algorytmy backtrackingowe,
  • obliczenia matematyczne.

11. Najczęstsze błędy

❌ brak warunku zakończenia

❌ niewłaściwa modyfikacja parametrów

❌ zbyt głęboka rekurencja

❌ mylenie rekurencji z pętlą

Wróć do spisu lekcji