Koncepcja funkcji rekurencyjnych w języku Python: samouczek języka Python dla początkujących

W świecie informatyki rekurencja odnosi się do techniki definiowania rzeczy w jej własnych terminach. Innymi słowy, funkcja rekurencyjna wywołuje samą siebie do przetwarzania. W tym artykule zrozumiemy pojęcie funkcji rekurencyjnej w Pythonie , powszechnie używanym języku programowania XXI wieku.

Co to jest rekurencja Pythona ?

W Pythonie grupa powiązanych instrukcji, które wykonują określone zadanie, nazywana jest „funkcją”. Tak więc funkcje dzielą twój program na mniejsze części. A powszechnie wiadomo, że funkcja może wywoływać inne funkcje w Pythonie.

Ale niektóre inne funkcje mogą się wywoływać same. Są to tak zwane funkcje rekurencyjne. Rozważmy dwa równoległe lustra ustawione naprzeciw siebie. Teraz każdy przedmiot trzymany między lustrami będzie odbijał się rekursywnie.

Przejdźmy do szczegółów funkcji rekurencyjnej, aby jasno zrozumieć jej działanie.

Funkcja rekurencyjna

Wiemy, że funkcja rekurencyjna w Pythonie wywołuje siebie tak, jak jest zdefiniowana za pomocą wyrażeń samoodnoszących się, tj. w terminach samej siebie. Powtarza swoje zachowanie, dopóki nie zostanie spełniony określony warunek, aby zwrócić wartość lub wynik. Spójrzmy teraz na przykład, aby dowiedzieć się, jak to działa.

Przeczytaj także: Pytania i odpowiedzi dotyczące wywiadu w Pythonie

Załóżmy, że chcesz poznać silnię liczby całkowitej. Silnia to nic innego jak iloczyn wszystkich liczb, począwszy od 1 do tej liczby całkowitej. Na przykład silnia 5 (zapisana jako 5!) będzie równa 1*2*3*4*5*6, czyli 720. Mamy funkcję rekurencyjną calc_factorial(x), która jest zdefiniowana w następujący sposób:

def calc_factorial(x):

#Funkcja rekurencyjna do znajdowania silni liczby całkowitej

jeśli x == 1:

powrót 1

w przeciwnym razie

return (x * calc_factorial(x-1))

Co by się stało, gdybyś nazwał tę funkcję dodatnią liczbą całkowitą, taką jak 4? Cóż, każde wywołanie funkcji doda ramkę stosu, dopóki nie osiągniemy przypadku podstawowego (gdy liczba zmniejszy się do 1). Warunek bazowy jest wymagany, aby rekurencja zakończyła się i nie trwała w nieskończoność. Czyli w danym przypadku wartość 24 zostanie zwrócona po czwartym wywołaniu.

Implementacja funkcji rekursywnej w Pythonie

W Pythonie mogą istnieć różne zastosowania funkcji rekurencyjnych. Na przykład, chcesz zrobić grafikę z powtarzającym się wzorem, powiedzmy płatek śniegu Kocha. Rekurencji można używać do generowania wzorów fraktalnych, które składają się z mniejszych wersji tego samego projektu.

Innym przykładem jest rozwiązywanie gier. Potrafisz pisać rekurencyjne algorytmy rozwiązywania Sudoku i wielu złożonych gier. Rekurencja jest najczęściej używana w problemach wyszukiwania, sortowania i przechodzenia.

Uderzającą cechą tej funkcji jest to, że implementacja rekurencyjna umożliwia cofanie się. Tak więc rekurencja polega na stopniowym budowaniu rozwiązania i usuwaniu tych rozwiązań, które nie spełniają ograniczeń problemu na dowolnym etapie. Do tego potrzebne są dwie rzeczy – utrzymanie stanu i odpowiedniej struktury danych. Czytaj dalej, aby zapoznać się z tymi terminami.

Przeczytaj: Wynagrodzenie programisty Pythona w Indiach

Utrzymanie państwa

Każde wywołanie rekurencyjne w Pythonie ma swój własny kontekst wykonania. Mając do czynienia z funkcjami rekurencyjnymi w Pythonie, musisz wątkować stan przez każde wywołanie rekurencyjne. Dzięki temu bieżący stan staje się częścią kontekstu wykonania bieżącego wywołania. Możesz również zachować stan w zakresie globalnym.

Na przykład, jeśli używasz rekurencji do obliczenia 1+2+3+4+…….+10. Tutaj aktualna liczba, którą dodajesz, i suma skumulowana do tego punktu tworzą stan, który musisz utrzymać. Utrzymanie stanu polega na przekazywaniu zaktualizowanego stanu bieżącego jako argumentów w każdym wywołaniu. Oto jak możesz to zrobić.

def sum_liczby(bieżąca_liczba, skumulowana_suma)

#Przypadek podstawowy

#Zwróć stan końcowy

jeśli aktualna liczba==11:

return skumulowana_suma

#Przypadek rekurencyjny

#Połącz stan przez wywołanie rekurencyjne

W przeciwnym razie:

return sum_numbers(bieżąca_liczba + 1, skumulowana_suma + bieżąca_liczba)

Alternatywnie możesz użyć globalnego stanu mutowalnego. Aby zachować stan przy użyciu tej metody, należy zachować stan w zakresie globalnym.

bieżąca_liczba = 1

skumulowana_suma = 0

def sum_liczby():

globalny numer_bieżący

globalna suma_skumulowana

#Przypadek podstawowy

jeśli bieżąca_liczba==11

return skumulowana_suma

#Przypadek rekurencyjny

w przeciwnym razie:

skumulowana_suma = skumulowana_suma + bieżąca_liczba

aktualny_numer = aktualny_numer + 1

zwróć sum_liczby()

Rekurencyjne struktury danych

Struktura danych jest uważana za rekurencyjną, jeśli można ją zdefiniować w kategoriach mniejszych i prostszych wersji samej siebie. Przykładami rekurencyjnych struktur danych są listy, drzewa, struktury hierarchiczne, słowniki itp. Lista może zawierać inne listy jako elementy. Drzewo ma poddrzewa, węzły liści i tak dalej.

Należy tutaj zauważyć, że struktura funkcji rekurencyjnych jest często modelowana na podstawie struktur danych, które przyjmuje jako dane wejściowe. Tak więc rekurencyjne struktury danych i funkcje rekurencyjne idą w parze.

Rekurencja w obliczeniach Fibonacciego

Włoski matematyk Fibonacci po raz pierwszy zdefiniował liczby Fibonacciego w XIII wieku, aby modelować wzrost populacji królików. Wydedukował, że począwszy od jednej pary królików w pierwszym roku liczba par królików urodzonych w danym roku jest równa liczbie par urodzonych w każdym z ostatnich dwóch lat. Można to zapisać jako: Fn = Fn-1 + Fn-2 (Przypadki bazowe: F0=1 i F1=1).

Kiedy piszesz funkcję rekurencyjną do obliczania liczby Fibonacciego, może to skutkować naiwną rekurencją. Dzieje się tak, gdy definicja funkcji rekurencyjnej jest naiwnie przestrzegana i niepotrzebnie przeliczasz wartości. Aby uniknąć ponownego przeliczenia, możesz zastosować dekorator lru_cache do funkcji. Buforuje wyniki i chroni proces przed nieefektywnością.

Przeczytaj więcej: 10 najlepszych narzędzi Pythona, które powinien znać każdy programista Pythona

Plusy i minusy rekurencji

Rekurencja pomaga uprościć złożone zadanie, dzieląc je na podproblemy. Funkcje rekurencyjne sprawiają, że kod jest czystszy, a także nieskomplikowane generowanie sekwencji. Ale rekurencja nie jest pozbawiona ograniczeń. Czasami połączenia mogą okazać się drogie i nieefektywne, ponieważ zużywają dużo czasu i pamięci. Funkcje rekurencyjne mogą być również trudne do debugowania.

Zawijanie

W tym artykule omówiliśmy koncepcję rekurencji Pythona , zademonstrowaliśmy ją na kilku przykładach, a także omówiliśmy niektóre jej zalety i wady. Mając wszystkie te informacje, możesz łatwo wyjaśnić funkcje rekurencyjne podczas następnego wywiadu w Pythonie!

Jeśli jesteś zainteresowany nauką o danych, sprawdź IIIT-B i upGrad's PG Diploma in Data Science, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z ekspertami z branży, 1- on-1 z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.