Artykuł przygotował: Codenga 08.06.2022

Żeby zrozumieć rekurencję trzeba najpierw poznać rekurencję. To taki żart, który krąży od lat i straszy początkujących programistów..

Rekurencja to po prostu specyficzne podejście do rozwiązywania problemów programistycznych. Ta technika, w dużym skrócie, polega na użyciu funkcji, która wywołuje samą siebie. Tylko po co to wszystko? Zaraz o tym trochę opowiemy.

Dwie główne koncepcje

Wiele typowych problemów można rozwiązać na dwa podstawowe sposoby.

• Iteracyjnie - za pomocą pętli
• Rekurencyjnie - za pomocą funkcji wywołującej samą siebie.

Każdy z tych sposobów ma swoje plusy oraz minusy. Najlepiej będzie jak od razu przejdziemy do przykładów.

Problem - rozwiązanie iteracyjne

Zacznijmy od zdefiniowania problemu. Mamy tablicę liczb całkowitych: 1, 5, 1, 2. Chcemy te liczby zsumować. Spróbujemy najpierw użyć pętli. To się wydaje być, na pierwszy rzut oka, najbardziej naturalnym podejściem do takiego problemu.

Oto kod naszego rozwiązania:

def sum_iter(digits):
result = 0
for digit in digits:
result += digit
return result

print(sum_iter([1, 5, 1, 2]))

Używamy języka Python bo ma on prostą, przejrzystą składnię, która doskonale nadaje się do zilustrowania naszego problemu.

Mamy prostą funkcję sum_iter(). Przyjmuje ona jako parametr listę digits z liczbami, które chcemy zsumować. Za pomocą pętli, przy każdej iteracji dodajemy do zmiennej result kolejną liczbę z listy. Dzięki temu na wyjściu otrzymamy wyjściową sumę liczb.

To jest rozwiązanie iteracyjne. Czyli takie, które oparte jest na pętli. Pętla działa dopóki wszystkie liczby nie zostaną zsumowane.

Problem - rozwiązanie rekurencyjne

Ten sam problem spróbujemy rozwiązać rekurencyjnie. Popatrz na kod:

def sum_rec(digits):
if len(digits) > 0:
last_element = digits[-1]
digits.pop()
return sum_rec(digits) + last_element
else:
return 0

print(sum_rec([1, 5, 1, 2]))

Trochę więcej kodu niż przy rozwiązaniu iteracyjnym. Skupmy się więc na kluczowych elementach.

• Mamy funkcję sum_rec(), która przyjmuje jako parametr tablicę z liczbami.
• Za pomocą instrukcji if sprawdzamy czy długość tablicy jest większa od 0.
• Do zmiennej last_element przypisujemy ostatni element z tablicy.
• Za pomocą metody pop() usuwamy ostatni element z tablicy.
• I wreszcie najważniejsza część. Zwracamy wywołanie funkcji sum_rec(digits). Czyli można powiedzieć, że funkcja sum_rec() wywołuje samą siebie.

Bądźmy szczerzy. W tym powyższym przykładzie podejście rekurencyjne jest skomplikowane - na pewno jest mniej przejrzyste niż rozwiązanie iteracyjne. Po co więc to wszystko?

Rekurencja u podstaw

Jak można uprościć problem polegający na sumowaniu liczb z tablicy? Mamy tu tak naprawdę dwa problemy:

• sumowanie kolejnych liczb
• wykrycie momentu, w którym wszystkie liczby są już zsumowane.

Problem pierwszy jest rozwiązywany za pomocą operacji, o których mówiliśmy przed chwilą. Wywołujemy funkcję sum_rec(digits) i dodajemy ostatni element z listy (zmienna last_element). Tyle, że taki kod będzie się wykonywał w nieskończoność jeśli go nie przerwiemy we właściwym momencie.

Dlatego mamy wewnątrz funkcji instrukcję warunkową. Sprawdza ona czy są jeszcze jakieś wartości w tablicy: if len(digits) > 0. Jeśli tak, to możemy kontynuować wywoływanie funkcji. A jeśli nie, to musimy przerwać za pomocą return 0.

I to jest cała idea rekurencyjnego podejścia do rozwiązywania problemów.

Wady, zalety, sens użycia

W tych powyższych przykładach wyraźnie było widać, że tradycyjne podejście z użyciem pętli jest prostsze, bardziej przejrzyste i bardziej przyjazne. Po co więc nam ta cała rekurencja?

• Są języki, które nie mają typowych pętli. Takie języki czasami skazują nas na rekurencyjne podejście. To jest co prawda niszowy przypadek ale może się coś takiego zdarzyć.
• Algorytmy rekurencyjne czasami łatwiej jest zwizualizować i rozbić na prostsze składniki. To jednak zależy od natury problemu, z którym masz do czynienia.
• Są sytuacje, w których rekurencyjne podejście będzie bardziej wydajne. W praktyce jednak wymaga to doświadczenia i dobrego zrozumienia zawiłości problemu z jakim masz do czynienia.

Rekurencja to dość specyficzne podejście. Prawidłowe wykorzystanie rekurencji wymaga zazwyczaj doświadczenia i dobrej oceny sytuacji.

Więcej w kursie

Chcesz dowiedzieć się więcej? Zapraszamy na kurs, który wprowadzi cię w temat rekurencyjnego podejścia do programowania. Znajdziesz w nim aż kilkanaście problemów, które nauczysz się rozwiązywać za pomocą algorytmów rekurencyjnych.