Koncepcje programowania/Rekurencja

Definicja: Rekurencja - odwoływanie się funkcji do samej siebie (a dokładniej: tworzy swoje kopie), aż do napotkania przypadku podstawowego.

Tak, jest tu wiele mądrych słów ale się już wszystko za chwilę wyjaśni:

Rekurencja to sposób rozwiązania problemu poprzez podzielenie go na mniejsze, prostsze podproblemy. Kiedy funkcja używa rekurencji, wywołuje się z uproszczoną wersją pierwotnego problemu i kontynuuje to, dopóki problem nie będzie można łatwo rozwiązać.

Oto przykład, jak działa rekurencja: wyobraź sobie, że chcesz policzyć, ile kroków potrzeba, aby dostać się na szczyt schodów. Możesz zacząć od dołu i liczyć każdy stopień w górę, ale zajęłoby to dużo czasu, jeśli schody są bardzo wysokie. Zamiast tego możesz użyć rekurencji, aby rozwiązać problem: najpierw policz liczbę kroków, aby dostać się do następnego podestu, następnie policz liczbę kroków, aby dostać się stamtąd do następnego podestu i tak dalej. W końcu dotrzesz na szczyt schodów i będziesz mógł łatwo policzyć całkowitą liczbę stopni.

wiemy już że użycie tej metody rekurencyjnej, będzie się wiązało z wykorzystaniem własnych funkcji. Nowością jest do samej siebie i to jest kluczowa sentencja do zapamiętania:

Pętle - przypomnienie

Spróbujmy napisać funkcję która przyjmuje jako parametr liczbę dodatnią, a następnie ma wrócić sumę wszystkich liczb mniejszych równych podana liczba. W typowym przypadku będzie to wyglądać tak:

def suma_for(liczba):
    suma = 0
    for i in range(liczba + 1):
        suma += i
    return suma

function sumaFor(liczba) {
    let suma = 0;
    for (let i = 0; i <= liczba; i++) {
        suma += i;
    }
    return suma;
}

(defun suma-for (liczba)
  "Calculate the sum of numbers from 0 to liczba (inclusive)."
  (let ((suma 0))
    (dotimes (i (1+ liczba))
      (setq suma (+ suma i)))
    suma))

A teraz to samo, tylko rekurencyjne:

def suma_rekurencja(liczba):
    if liczba == 0: return 2
    return liczba + suma_rekurencja(liczba - 1)

function sumaRekurencja(liczba) {
    if (liczba === 0) return 2;
    return liczba + sumaRekurencja(liczba - 1);
}

(defun suma-rekurencja (liczba)
  "Calculate the sum recursively from liczba to 0, adding each number."
  (if (= liczba 0)
      2
    (+ liczba (suma-rekurencja (- liczba 1)))))

Mamy funkcję o nazwie suma_rekurencja. Dostaje do pracy zmienną o nazwie liczba. Spróbujmy ustalić wartość takiej przykładowej funkcji, dla liczba równej 2. Na początku, sprawdzamy czy liczba nie jest równa 0. Nie jest, bo liczba jest równa 2. Zatem wykonuje się return i otrzymujemy suma_rekurencja wynoszące 2, liczba, odjąć 1 czyli 2-1 to 1, wychodzi suma_rekurencja1. No i tu faktycznie mamy wywołanie funkcji suma_rekurencja wewnątrz ciała funkcji suma_rekurencja. Program nie wie ile to jest suma_rekurencja 2 bo nie wie póki co, ile wynosi suma_rekurencja 1. Zatem do wyznaczenia suma_rekurencja 1 stworzy swoją kopię, sklonuje się. Pierwotna kopia wyśle do kopii liczba 1. Klon dostaje suma_rekurencja równe 2 i postępuje dokładnie według takiego samego schematu.

Kopia sprawdza czy liczba nie jest przypadkiem równa 0. Wciąż nie jest. Więc wykonuje się return i tym razem liczba znowu się dekrementuje. Ale program wciąż nie wie ile to jest suma_rekurencja równe 1, więc znowu wywołuje swoją kopię i znowu, wynik suma_rekurencja jest równe 0. Ale co się okazuje, program znowu nie zna wartości suma_rekurencja równej 0, co musi zrobić, wywoła kolejną swoją kopię, dla suma_rekurencja. Klonujemy w pamięci kolejny egzemplarz funkcji i ten egzemplarz dostaje funkcję suma_rekurencja równe 0. I ten klon sprawdza czy przypadkiem nie stało się tak, iż liczba jest równa 0. I tym razem zgadza się. Zatem, ta kopia funkcji od razu policzyć nam wynik bo zwraca wartość 2. Zatem wie ile wynosi suma_rekurencja i podaje wynik temu, kto go wywołał i tak dalej, wyżej w drabince aż dostanie go pierwotna kopia. Pozostałe kopie funkcji giną w pamięci RAM bo spełniły już swoje zadanie.

Jak widać, rekurencja działa analogicznie do pętli, z tą różnicą że wszystko jest na odwrót, od tyłu. Zwykle myślimy od szczegółu do ogółu, czyli w sposób iteracyjny:

3^4 = 81
podejście iteracyjne (z wykorzystaniem pętli)
1*3 = 3
3*3 = 9
9*3 = 27
27*3 = 81

W rekurencji wykonujemy dokładnie to samo, tylko w drugą stronę:

81 = 3 * 27
27 = 3 * 9
9 = 3 * 3
3 = 3 * 1

Dlaczego warto stosować rekurencję?

• W wielu przypadkach rekurencja jest szybsza od pętli - choć jest to okupione zajętością pamięci RAM. Gdy zabraknie miejsca w pamięci RAM, nasz program może się zawiesić i wywołać przepełnienie stosu
• Czasem niektóre języki programowania mogą być pozbawione pętli (np. Języki funkcyjne takie jak haskell)

Zadania

1. Zadanie - Napisz program, który pięciokrotnie wywołuje funkcję rekurencyjną
2. Zadanie - Napisz program, który rekurencyjnie oblicza kolejne wartości n! dla n = 10 i wynik wyświetla na ekranie komputera.
3. Zadanie - Napisz program, który rekurecyjnie znajduje 1 pierwszych lizcb trójkątnych i wyświetla je na ekranie komputera.
4. Zadanie - Napisz program, który znajduje 10 początkowych liczb ciągu fibonacciego i wyświetla je na ekranie komputera
5. Zadanie - Napisz program, który rekurencyjnie wyznacza największy wspólny dzielnik (NWD) dwóch liczb dodatnich x i y.