Ostatnia aktualizacja 13 lutego, 2024
Rekurencja to technika programistyczna, która pozwala funkcji wywoływać samą siebie. Jest to szczególnie przydatne w rozwiązywaniu problemów, które można podzielić na mniejsze, podobne do siebie zadania. W Pythonie, jak również w innych językach programowania, rekurencja pozwala na eleganckie i często intuicyjne rozwiązania dla wielu algorytmicznych wyzwań. W tym tekście przyjrzymy się bliżej, jak można wykorzystać funkcje rekurencyjne w Pythonie. Przedstawimy przykłady kodu oraz wyjaśnimy, w jaki sposób można je stosować.
Podstawy rekurencji
Rekurencja w Pythonie opiera się na zasadzie, że funkcja może wywoływać samą siebie. Aby jednak uniknąć nieskończonego wywoływania, ważne jest, aby zdefiniować warunek zakończenia rekurencji, zwanego przypadkiem bazowym.
Przypadek bazowy a funkcje rekurencyjne w Pythonie
Bez zdefiniowania przypadku bazowego funkcja rekurencyjna wchodziłaby w nieskończoną pętlę wywołań, co ostatecznie doprowadziłoby do przekroczenia limitu wywołań rekurencyjnych i zakończenia programu błędem.
Przypadek bazowy musi być osiągalny z każdego możliwego wywołania rekurencyjnego, a warunki prowadzące do jego osiągnięcia powinny być jasno zdefiniowane. W zależności od problemu, funkcja rekurencyjna może mieć jeden lub więcej przypadków bazowych.
Obliczanie silni
def silnia(n):
if n == 0:
return 1
else:
return n * silnia(n-1)W powyższym przykładzie silnia(n) wywołuje samą siebie z argumentem n-1, aż do osiągnięcia przypadku bazowego, którym jest n == 0. Wtedy funkcja zwraca 1, co umożliwia zakończenie rekurencji i obliczenie wyniku.
Sprawdź też: Praca Warszawa
Rekurencja a pętle
Często zdarza się, że problem rozwiązany za pomocą rekurencji można również rozwiązać używając pętli. Jednak rekurencja może być bardziej czytelna i naturalna dla niektórych typów problemów, zwłaszcza tych związanych z przeszukiwaniem i sortowaniem.
Ciąg Fibonacciego
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)W tym przypadku funkcja fibonacci wywołuje samą siebie dwa razy dla każdego wywołania. Ten przykład ilustruje, jak można używać rekurencji do rozwiązania problemów, w których każde zadanie da się podzielić na mniejsze podzadania.
Dalsza część tekstu znajduje się pod materiałem wideo:
Funkcje rekurencyjne w Pythonie – zastosowania
Rekurencja znajduje zastosowanie w wielu dziedzinach programowania, od algorytmów sortowania, przez przeszukiwanie drzew i grafów, po rozwiązywanie skomplikowanych problemów matematycznych.
Przeanalizujmy teraz przeszukiwanie binarne:
def przeszukiwanie_binarne(lista, element, start, koniec):
if start > koniec:
return False
srodek = (start + koniec) // 2
if lista[srodek] == element:
return True
elif lista[srodek] > element:
return przeszukiwanie_binarne(lista, element, start, srodek-1)
else:
return przeszukiwanie_binarne(lista, element, srodek+1, koniec)W powyższym przykładzie przeszukiwanie_binarne wykorzystuje rekurencję do dzielenia listy na coraz mniejsze części, aż znajdzie szukany element lub dojdzie do wniosku, że elementu nie ma na liście.
Dziękujemy, że przeczytałaś/eś nasz artykuł. Obserwuj EnterTheCode.pl w Wiadomościach Google, aby być na bieżąco.
Czytaj także:
Wprowadzenie do funkcji w Pythonie
Ciąg Fibonacciego – właściwości i zastosowania złotej proporcji
