Lesson 8
Funkcje i rekursja

1. Funkcje

Przypomnijmy, że w matematyce silnia liczby n jest definiowana jako n! = 1 ⋅ 2 ⋅ ... ⋅ n (jako iloczyn wszystkich liczb całkowitych od 1 do n). Na przykład 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120. Oczywiste jest, że silnię można łatwo obliczyć za pomocą pętli for. Wyobraź sobie, że w naszym programie potrzebujemy kilkakrotnie obliczyć silnię różnych liczb (lub w różnych miejscach kodu). Oczywiście, możesz raz zapisać obliczenia silni, a następnie użyć Copy-Paste, aby wstawić ją tam, gdzie jej potrzebujesz:

None

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

None

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

10
20

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.

None

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

None

def max(*a):
    res = a[0]
    for val in a[1:]:
        if val > res:
            res = val
    return res

print(max(3, 5, 4))

2. Zmienne lokalne i globalne

Wewnątrz funkcji możesz użyć zmiennych zadeklarowanych gdzieś poza nim:

None

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:

None

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:

None

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:

None

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 :

None

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ć:

5

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:

5

# 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:

None

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()

1. Nieprawidłowe warunki zatrzymania. Na przykład, jeśli w programie do obliczania czynnikowego zapominamy o sprawdzeniu, if n == 0 , factorial(0) wywoła factorial(-1) , która wywoła factorial(-2) itd.
2. Wywołanie rekurencyjne z niepoprawnymi parametrami. Na przykład, jeśli factorial(n) funkcji factorial(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.