Otwórz sobie drzwi do kariery programisty     |        Wybierz swoją ścieżkę kariery w IT!     |       Zacznij naukę z 30% rabatem

3 dni 21 godzin
close
Cart icon
User menu icon
User icon
Skontaktuj się z nami:
+48 888-916-333
Lightbulb icon
Jak to działa?
FAQ icon
FAQ
Contact icon
Kontakt
Terms of service icon
Regulamin zakupów
Privacy policy icon
Polityka prywatności
Zdjęcie główne artykułu.

Co to jest rekurencja

Ż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.