Lesson 8
Funkcje i rekursja
1. Funkcje
Przypomnijmy, że w matematyce silnia liczby n jest definiowana jako
# obliczyć 3!
res = 1
for i in range(1, 4):
res *= i
print(res)
# obliczyć 5!
res = 1
for i in range(1, 6):
res *= i
print(res)
Jeśli jednak popełnimy błąd w początkowym kodzie, ten błędny kod pojawi się we wszystkich miejscach, w których skopiowaliśmy obliczenia silni. Co więcej, kod jest dłuższy niż mógłby być. Aby uniknąć ponownego wpisywania tej samej logiki w językach programowania, istnieją funkcje.
Funkcje to sekcje kodu, które są odizolowane od reszty programu i wykonywane tylko po wywołaniu. Poznałeś już funkcję sqrt() , len() i print() . Wszystkie mają coś wspólnego: mogą przyjmować parametry (zero, jeden lub kilka z nich) i mogą zwracać wartość (chociaż mogą nie zwrócić). Na przykład funkcja sqrt() przyjmuje jeden parametr i zwraca wartość (pierwiastek kwadratowy z podanej liczby). Funkcja print() może przyjmować różne liczby argumentów i niczego nie zwraca.
Teraz chcemy pokazać, jak napisać funkcję o nazwie factorial() która przyjmuje pojedynczy parametr - liczbę i zwraca wartość - silnię tego numeru.
def factorial(n):
res = 1
for i in range(1, n + 1):
res *= i
return res
print(factorial(3))
print(factorial(5))
Chcemy podać kilka wyjaśnień. Najpierw kod funkcji powinien zostać umieszczony na początku programu (przed miejscem, w którym chcemy użyć funkcji factorial() , by być precyzyjnym). Pierwsza linia def factorial(n): tego przykładu jest opisem naszej funkcji; słowo silnia to identyfikator (nazwa naszej funkcji). Zaraz za identyfikatorem pojawia się lista parametrów, które otrzymuje nasza funkcja (w nawiasach). Lista składa się z oddzielonych przecinkami identyfikatorów parametrów; w naszym przypadku lista składa się z jednego parametru n . Na końcu rzędu umieść dwukropek.
Następnie przechodzi ciało funkcyjne. W języku Python treść musi być wcięta (tabulator lub cztery spacje, jak zawsze). Ta funkcja oblicza wartość n! i przechowuje go w zmiennej res . Ostatnia linia funkcji to return res , która kończy działanie funkcji i zwraca wartość zmiennej res .
Instrukcja return może pojawić się w dowolnym miejscu funkcji. Jego wykonanie kończy działanie funkcji i zwraca określoną wartość do miejsca, w którym wywołano funkcję. Jeśli funkcja nie zwraca wartości, instrukcja return nie zwróci pewnej wartości (mimo że nadal może być używana). Niektóre funkcje nie muszą zwracać wartości, a instrukcja return może być dla nich pominięta.
Chcielibyśmy podać inny przykład. Oto funkcja max() która przyjmuje dwie liczby i zwraca ich maksymalną wartość (faktycznie ta funkcja stała się już częścią składni Pythona).
def max(a, b):
if a > b:
return a
else:
return b
print(max(3, 5))
print(max(5, 3))
print(max(int(input()), int(input())))
Teraz możesz napisać funkcję max3() która pobiera trzy liczby i zwraca ich maksimum.
def max(a, b):
if a > b:
return a
else:
return b
def max3(a, b, c):
return max(max(a, b), c)
print(max3(3, 5, 4))
Wbudowana funkcja max() w Pythonie może przyjmować różne liczby argumentów i zwracać ich maksimum. Oto przykład tego, jak można taką funkcję zapisać.
def max(*a):
res = a[0]
for val in a[1:]:
if val > res:
res = val
return res
print(max(3, 5, 4))
a , która jest oznaczona gwiazdką.
2. Zmienne lokalne i globalne
Wewnątrz funkcji możesz użyć zmiennych zadeklarowanych gdzieś poza nim:
def f():
print(a)
a = 1
f()
Tutaj zmienna a jest ustawiona na 1, a funkcja f() drukuje tę wartość, mimo że deklarując funkcję f ta zmienna nie jest inicjowana. Powodem jest, że w momencie wywołania funkcji f() (ostatniego ciągu) zmienna a ma już wartość. Dlatego funkcja f() może go wyświetlić.
Takie zmienne (zadeklarowane poza funkcją, ale dostępne wewnątrz funkcji) nazywane są globalnymi .
Ale jeśli zainicjujesz jakąś zmienną wewnątrz funkcji, nie będziesz w stanie użyć tej zmiennej poza nią. Na przykład:
def f():
a = 1
f()
print(a)
Otrzymujemy błąd NameError: name 'a' is not defined . Takie zmienne zadeklarowane w ramach funkcji nazywane są lokalnymi . Po wyjściu z funkcji stają się niedostępne.
To, co naprawdę jest czarujące, dotyczy tego, co dzieje się, gdy zmienisz wartość zmiennej globalnej w funkcji:
def f():
a = 1
print(a)
a = 0
f()
print(a)
Ten program wypisze ci cyfry 1 i 0. Pomimo faktu, że wartość zmiennej a zmieniona wewnątrz funkcji, poza funkcją pozostaje taka sama! Odbywa się to w celu "ochrony" zmiennych globalnych przed nieumyślnymi zmianami funkcji. Tak więc, jeśli jakaś zmienna zostanie zmodyfikowana wewnątrz funkcji, zmienna staje się zmienną lokalną, a jej modyfikacja nie zmieni zmiennej globalnej o tej samej nazwie.
Bardziej formalnie: interpreter języka Python uwzględnia zmienną lokalną dla funkcji, jeśli w kodzie tej funkcji istnieje co najmniej jedna instrukcja, która modyfikuje wartość zmiennej. Zmienna ta również nie może być użyta przed inicjalizacją. Instrukcje modyfikujące wartość zmiennej - operator = , += i użycie zmiennej jako pętli for parametru. Jednak nawet jeśli instrukcja zmiennej zmiennej nigdy nie zostanie wykonana, interpreter nie może jej sprawdzić, a zmienna jest nadal lokalna. Przykład:
def f():
print(a)
if False:
a = 0
a = 1
f()
Wystąpił błąd: UnboundLocalError: local variable 'a' referenced before assignment . Mianowicie, w funkcji f() identyfikator a staje się zmienną lokalną, ponieważ funkcja zawiera polecenie modyfikujące zmienną a . Instrukcja modyfikująca nigdy nie zostanie wykonana, ale interpreter jej nie sprawdzi. Dlatego przy próbie wydrukowania zmiennej a odwołujesz się do niezainicjowanej zmiennej lokalnej.
Jeśli chcesz, aby funkcja mogła zmieniać niektóre zmienne, musisz zadeklarować tę zmienną w funkcji za pomocą słowa kluczowego global :
def f():
global a
a = 1
print(a)
a = 0
f()
print(a)
W tym przykładzie wydrukujemy wynik 1 1, ponieważ zmienna a jest deklarowana jako globalna, a zmiana jej wewnątrz funkcji powoduje jej globalną zmianę.
Jednak lepiej nie modyfikować wartości zmiennych globalnych wewnątrz funkcji. Jeśli twoja funkcja musi zmienić jakąś zmienną, niech zwróci tę wartość, a wybierzesz, wywołując funkcję, jawnie przypisz zmienną do tej wartości. Jeśli stosujesz się do tych zasad, logika funkcji działa niezależnie od logiki kodu, a więc takie funkcje można łatwo kopiować z jednego programu do drugiego, oszczędzając czas.
Załóżmy na przykład, że twój program powinien obliczyć silnię podanej liczby, którą chcesz zapisać w zmiennej f. Oto jak tego nie robić:
def factorial(n):
global f
res = 1
for i in range(2, n + 1):
res *= i
f = res
n = int(input())
factorial(n)
print(f)
# robienie innych rzeczy ze zmienną f
Jest to przykład złego kodu, ponieważ trudno go użyć innym razem. Jeśli jutro potrzebujesz innego programu do korzystania z funkcji "silnia", nie będziesz mógł skopiować tej funkcji tutaj i wkleić do nowego programu. Musisz upewnić się, że ten program nie zawiera zmiennej f .
O wiele lepiej jest przepisać ten przykład w następujący sposób:
# początek fragmentu kodu, który można skopiować z programu do programu
def factorial(n):
res = 1
for i in range(2, n + 1):
res *= i
return res
# koniec fragmentu kodu
n = int(input())
f = factorial(n)
print(f)
# robienie innych rzeczy ze zmienną f
Warto powiedzieć, że funkcje mogą zwracać więcej niż jedną wartość. Oto przykład zwracania listy dwóch lub więcej wartości:
return [a, b]
Możesz wywołać funkcję takiej listy i użyć jej w wielu zadaniach:
n, m = f(a, b)
3. Rekursja
Jak widzieliśmy powyżej, funkcja może wywoływać inną funkcję. Ale funkcje mogą się również nazywać! Aby to zilustrować, rozważmy przykład funkcji silni-obliczeniowej. Powszechnie wiadomo, że 0! = 1, 1! = 1. Jak obliczyć wartość n! dla dużego n? Gdybyśmy byli w stanie obliczyć wartość (n-1) !, to łatwo obliczyć n !, ponieważ n! = N⋅ (n-1) !. Ale jak obliczyć (n-1) !? Jeśli obliczyliśmy (n-2) !, to (n-1)! = (N-1) ⋅ (n-2) !. Jak obliczyć (n-2) !? Jeśli ... Na końcu otrzymamy 0 !, co równa się 1. W ten sposób do obliczenia silni możemy użyć wartości silni dla mniejszej liczby całkowitej. Obliczenia można wykonać za pomocą Pythona:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
print(factorial(5))
Sytuacja, gdy same wywołania funkcji nazywa się rekurencją , a taka funkcja nazywa się rekursywną.
Funkcje rekurencyjne są potężnym mechanizmem programowania. Niestety nie zawsze są skuteczne i często prowadzą do błędów. Najczęstszym błędem jest nieskończona rekurencja , gdy łańcuch wywołań funkcji nigdy się nie kończy (cóż, w rzeczywistości kończy się, gdy zabraknie wolnej pamięci w komputerze). Przykład nieskończonej rekursji:
def f():
return f()
Dwa najczęstsze przyczyny powodujące nieskończoną rekurencję: - Nieprawidłowe warunki zatrzymania. Na przykład, jeśli w programie do obliczania czynnikowego zapominamy o sprawdzeniu,
if n == 0,factorial(0)wywołafactorial(-1), która wywołafactorial(-2)itd. - Wywołanie rekurencyjne z niepoprawnymi parametrami. Na przykład, jeśli
factorial(n)funkcjifactorial(n)wywoła funkcjęfactorial(n), otrzymamy również nieskończony łańcuch wywołań.
Dlatego podczas kodowania funkcji rekursywnej trzeba najpierw upewnić się, że osiągnie ona warunki zatrzymania - zastanowić się, dlaczego rekursja kiedykolwiek się zakończy.