Rekurencja, zwana także rekursją (recursion) oznacza odwoływanie się funkcji (bądź definicji) do samej siebie.

Oto przykład prostego programu, który wykorzystuje rekurencję.

#include <stdio.h>
#include <stdlib.h>
 
void gora_i_dol(int n)
{
    printf("Poziom %d\n", n);
 
    if (n < 3) {
        gora_i_dol(n + 1);
    }
 
    printf("POZIOM %d\n", n);
}
 
int main()
{
    gora_i_dol(1);
    return 0;
}

Efekt działania powyższego programu (zwróć uwagę na kolejność komunikatów):

Poziom 1
Poziom 2
Poziom 3
POZIOM 3
POZIOM 2
POZIOM 1

Zasady rekurencji:

• Każdy poziom rekurencji posiada swoje własne (niezależne od innych poziomów) zmienne – bo wywoływana jest nowa funkcja.
• Każdemu wywołaniu funkcji odpowiada jeden powrót. Po wykonaniu instrukcji return na końcu ostatniego (najgłębszego) poziomu rekurencji, program przechodzi do poprzedniego poziomu rekurencji (w miejsce tuż po wywołaniu funkcji) – a nie do funkcji main().
• Po powrocie do miejsca wywołania funkcji wykonywane są dalsze instrukcje znajdujące się w funkcji.
• Chociaż każdy poziom rekurencji posiada swój własny zestaw zmiennych, kod funkcji nie jest zwielokrotniany. Po prostu podczas kolejnego wywołania tej samej funkcji program ponownie przechodzi na jej początek, tyle że z nowym zestawem zmiennych.

Jeśli do wyboru mamy napisać pętlę bądź użyć rekurencji, to ze względów wydajności lepiej użyć pętli. Rekurencja wymaga o wiele więcej pamięci na dodatkowe zestawy zmiennych! Natomiast w niektórych przypadkach użycie rekurencji jest dużo prostsze i bardziej intuicyjne…

Przykład – obliczanie potęgi liczby

Znanym z matematyki przykładem definicji rekurencyjnej jest definicja potęgi liczby naturalnej o wykładniku naturalnym: $$ a^n := \begin{cases} 1 & \mbox{dla } n = 0; \\ a \cdot a^{n-1} & \mbox{dla } n > 0. \\ \end{cases} \qquad a, n \in \mathbb{N} $$

W poniższym programie umieszczono dodatkowe “diagnostyczne” fragmenty kodu umożliwiające śledzenie zmian wartości zmiennych.
Zmienna poziom oznacza poziom rekurencji, czyli który raz z kolei funkcja wywołała samą siebie.
(W dalszej części laboratorium znajduje się wersja pozbawiona tych fragmentów.)

#include <stdio.h>
#include <stdlib.h>
 
int potega(int a, int n, int poziom);
 
int main ()
{
    int a = 3;
    int n = 2;
 
    printf("%d^%d = %d\n", a, n, potega(a, n, 0));
 
    return 0;
}
 
int potega(int a, int n, int poziom)
{
    int p;
    int i;
 
    for (i = 0; i < poziom; i = i + 1) {
        printf(" ");
    }
    printf("poziom %d: n = %d\n", poziom, n);
 
    if (n == 0) {
        p = 1;
    } else {
        p = a * potega (a, n - 1, poziom + 1);
    }
 
    for (i = 0; i < poziom; i = i + 1) {
        printf(" ");
    }
    printf("poziom %d: p = %d\n", poziom, p);
 
    return p;
}

Schemat ilustrujący zmianę zmiennych podczas wykonania powyższego programu (szare ramki oznaczają zmienne z wyższego poziomu przesłonięte przez zmienne z niższego poziomu wywołań funkcji):

Używając notacji matematycznej rekurencyjne obliczanie potęgi można rozpisać następująco (cyfry rzymskie oznaczają poziom rekurencji): $$\text{potega($a = 3$, $n = 2$)} \colon \quad 3^2 \; \overset{I}{=} \; 3 \cdot a^1 \; \overset{II}{=} \; 3 \cdot (3 \cdot a^0) \; \overset{III/II}{=} \; 3 \cdot (3 \cdot \underbrace{1}_{a^0}) \; \overset{I}{=} \; 3 \cdot \underbrace{3}_{a^1} \; \overset{I}{=} \; 9 \; \rightarrow \text{main()}$$

Poniżej kod programu realizującego to samo zadanie, tyle że pozbawionego części “diagnostycznej”:

#include <stdio.h>
#include <stdlib.h>
 
int potega(int a, int n)
{
    if (n == 0) {
        return 1;
    } else {
        return a * potega (a, n - 1);
    }
}
 
 
int main ()
{
    int a = 3;
    int n = 4;
 
    printf("%d^%d = %d\n", a, n, potega(a, n));
 
    return 0;
}

To przykład rekurencji końcowej, kiedy to wywołanie rekurencyjne znajduje się na końcu funkcji, tuż przed instrukcją return.

Rekurencja oznacza po prostu to, że funkcja wywołuje samą siebie. Musi jednak przypadek, w którym funkcja ta nie wywoła samej siebie – w przeciwnym razie program wpadnie w nieskończony cykl wywołań, wyczerpie dostępny limit pamięci na wywołania funkcji i… zostanie “ubity” przez system operacyjny. Przypadek, w którym funkcja nie wywołuje samej siebie, nazywamy przypadkiem podstawowym (w przykładzie z potęgowaniem był to przypadek dla $n = 0$). Projektowanie funkcji rekurencyjnej sprowadza się więc do wyboru rozsądnego przypadku podstawowego, a następnie upewnieniu się, że każdy ciąg wywołań funkcji w końcu osiągnie ten przypadek.

Ciekawymi przykładami definicji rekurencyjnych są fraktale, czyli figury samopodobne.
Przykład fraktala – zbiór Mandelbrota:

Być może podobne, nieco prostsze wzory wygenerujesz już wkrótce samodzielne, w ramach naszych zajęć!

Rekurencję można wykorzystać do znajdowania największego wspólnego dzielnika dwóch liczb całkowitych.

Rekurencja stanowi serce klasy algorytmów Dziel i zwyciężaj, których idea opiera się na rekurencyjnym podziale (trudnego) problemu na (łatwe do rozwiązania) podproblemy i odpowiedniego “scalania” ich rozwiązań w celu uzyskania rozwiązania początkowego problemu.

Wskazówka ogólna: Czy ktoś Ci powiedział “ta funkcja ma przyjmować dokładnie jeden parametr”?

(poziom trudności: )

Napisz program, który obliczy silnię zadanej liczby naturalnej $n$ metodą rekurencyjną.

Rekurencyjna definicja silni: $$ n!=\begin{cases} 1 & \mbox{ dla }n=0 \\ n\cdot(n-1)! & \mbox{ dla }n\geqslant1 \end{cases} $$

(poziom trudności: )

Napisz program sprawdzający, czy zadana liczba naturalna jest liczbą pierwszą – oczywiście metodą rekurencyjną, bez użycia jakichkolwiek pętli.

Dla przypomnienia – rozwiązanie tego samego problemu z użyciem pętli "for".

(poziom trudności: )

Napisz funkcję, która w rekurencyjny sposób obliczy sumę cyfr liczby naturalnej przekazanej jako argument.

Wskazówka: Zadanie to można rozwiązać stosując podobne podejście i podobne operacje arytmetyczne, co w zadaniu na sumowanie cyfr.

(poziom trudności: )

Napisz program, który wypisze na ekranie reprezentację binarną zadanej liczby całkowitej dodatniej. Zadanie zrealizuj z użyciem rekurencji.
Przykład: dla liczby 15 program powinien wypisać 1111.

Wskazówka 1: Wypisuj kolejne pozycje liczby binarnej – znak po znaku (nie próbuj wypisać wszystkiego od razu).
Wskazówka 2: Od której strony da się zacząć wypisywanie? Zastanów się, w jakiej kolejności zrealizować operacje: (1) wyświetlanie cyfry dwójkowej na ekranie i (2) ponowne wywołanie funkcji.
Wskazówka 3: Zadanie to można rozwiązać stosując podobne podejście i podobne operacje arytmetyczne, co w zadaniu na sumowanie cyfr.
Wskazówka 4: Do weryfikacji poprawności otrzymanych wyników możesz skorzystać z windowsowego kalkulatora w widoku programisty.