Lekcja 3. Funkcje.

Na początku poprzedniej lekcji, analizowaliśmy przykład kodu służącego do sprawdzania czy dana liczba jest liczbą parzystą:

W przykładzie tym liczba miała przypisaną wartość początkową równą 12. Chcąc testować dowolne inne liczby przy użyciu tego kodu, musieliśmy za każdym razem do zmiennej liczba przypisać nową wartość i uruchomić program od nowa. Nie zawsze musi tak być. Możemy sobie poradzić z tym w bardziej wyrafinowany sposób:

Pojęcie funkcji

W odróżnieniu od przykładu pierwszego, tym razem nie musimy przypisywać za każdym razem nowej wartości dla zmiennej liczba. Zamiast tego podajemy interesującą nas liczbę jako parametr funkcji. W przykładzie funkcja nosi nazwę: testowanie_parzystosci(). Sama deklaracja tej konkretnej funkcji zaczyna się od słowa kluczowego def. Po nim następuje nazwa funkcji, zawsze koniecznie z nawiasami (), po których następuje :. Poeksperymentuj z tym fragmentem kodu, podając przy wywołaniu jako argument funkcji różne, inne niż 12 wartości. Wywołaj funkcję dowolną ilość razy. Zapewne zastanawiasz się czym jest taka funkcja?

Bardzo ogólnie rzecz ujmując, poprzez funkcję, będziemy rozumieli nazwany fragment kodu, do którego możemy się odwoływać wielokrotnie. Funkcje charakteryzują się istnieniem zwracanej przez nie wartości wynikowej. Używanie funkcji jest intuicyjne. Można przyjąć zasadę, że tam gdzie zachodzi konieczność powtórzenia kodu, którego zadaniem jest wykonanie tej samej procedury, tam należy kod przekształcić do postaci funkcji. Kod całego programu staje się bardziej czytelny i funkcjonalny. Idea funkcji w programowaniu, jest analogiczna do funkcji w sensie matematycznym. W odróżnieniu jednak od funkcji matematycznych, funkcje w programowaniu nie muszą posiadać argumentu (parametru), by być poprawnie zdefiniowane. Przykładowo:

Zadanie 3.1

Znakomita większość żeńskich imion kończy się na literę “a”, jednocześnie istnieje niewiele imion męskich kończących się na “a”. Napisz funkcję testującą, czy podane imię jest męskie czy żeńskie. Dodaj obsługę znanych Ci wyjątków.

Instrukcja return

W powyższych przykładach funkcje komunikowały się z nami, drukując wartości, ponieważ w swoich kodach zawierały instrukcję print. W ogólności by zwrócić wartość funkcji należy posłużyć się instrukcją return. Instrukcja ta zwraca podany obiekt, oraz powoduje wyjście z funkcji. Jeżeli chcemy zwrócić więcej niż jedną zmienną to stosujemy np. krotkę (czyli konstrukcję opisaną w lekcji 2). Aby wywołać funkcję, należy napisać jej nazwę, a po niej krotkę zawierającą argumenty funkcji. Kolejność, oraz liczba parametrów przekazywanych do funkcji, musi zgadzać się z jej definicją:

Zauważmy, że instrukcji return można użyć w kodzie funkcji wielokrotnie, tak jak w poniższym przykładzie:

W zależności, od podanej pary liczb, wykonywanie funkcji jest przerywane albo po instrukcji if x > y:, albo po instrukcji else:. Dobrą praktyką jest dokumentowanie, w formie łańcucha znaków """ ... """ do czego służy dana funkcja. Łańcuch taki, występujący zaraz po pierwszej linii definiującej funkcję nazywamy docstringiem. Ponieważ, w kursie tym, kody źródłowe omawiane są w sposób szczegółowy to w kolejnych przykładach nie zawsze uszanujemy ten zwyczaj. Wy powinniście.

Funkcje mogą się odwoływać do innych funkcji, rozpatrzmy następujący przykład:

Pierwsza z funkcji: f(a) podnosi podaną liczbę do kwadratu. Następnie, kwadrat ten, przekazywany jest jako parametr drugiej funkcji: g(a). Warto podkreślić, że funkcja g(a) nie zawiera definicji funkcji f(a). Taki a nie inny wynik działania programu, związany jest z tym, w jakiej kolejności kod odczytywany jest i wykonywany przez interpreter. Pouczające może być sprawdzenie, co stanie się, jeśli w powyższym kodzie zamienimy miejscami, obie definicje funkcji. Sprawdź to proszę. Czy uzyskany wynik powinien dziwić?

Zadanie 3.2

Napisz program sprawdzający, która z dwóch podanych liczb jest podzielna przez 3 i (lub) przez 4.

Domyślne wartości parametrów

Definiując funkcję, możemy przypisać parametrom domyślne wartości. Użyte będą one wtedy, gdy przy wywoływaniu funkcji, nie zostaną podane inne wartości dla tych parametrów. Zobrazujmy to, na przykład, rozwiązując ale tym razem z zastosowaniem wiedzy nabytej w tym rozdziale, Zadanie 102 z zestawu zadań do lekcji 1.

Zadanie 3.3

Napisz funkcję konwertującą odległość podaną w kilometrach, domyślnie na mile morskie i jardy, a opcjonalnie na dowolną inna milę i jardy.

Zakres zmiennych

Zmienne lokalne i globalne

Interpreter języka Python, śledząc zmienne, odwołuje się do tak zwanej przestrzeni nazw. Przestrzeń nazw jest reprezentowana przez słownik zwracany przez funkcję globals(). W słowniku tym kluczami są nazwy zmiennych, a jego wartościami są wartości tych zmiennych. Do przestrzeni tych nazw możemy odwołać się tak jak do słownika.

>>> globals()
{'__builtins__': <module '__builtin__' (built-in)>, '__name__': '__main__', '__doc__': None, '__package__': None}

Na chwilę obecną wystarczy nam wiedzieć, że w procesie programowania mamy dostęp do kilku przestrzeni nazw. Po pierwsze każda funkcja posiada własną przestrzeń nazw, nazywaną lokalną przestrzenią nazw, a która śledzi zmienne funkcji, włączając w to jej argumenty i lokalnie zdefiniowane zmienne. Zmienne te będziemy nazywać zmiennymi lokalnymi. Do nazw poszczególnych obiektów możemy dostać z funkcji locals(). Po drugie każdy moduł posiada własną przestrzeń nazw zwaną globalną przestrzenią nazw - patrz funkcja globals(). Na potrzeby tej lekcji, przyjmijmy, że osobnymi modułami są w całości poszczególne omawiane przykłady. Globalna przestrzeń nazw śledzi zmienne modułu, włączając w to funkcje, klasy (o których traktuje kolejna lekcja), ewentualnie wszystkie inne zaimportowane moduły, a także zmienne zdefiniowane w tym module. Zmienne zdefiniowane w tym miejscu będziemy nazywali zmiennymi globalnymi. Po trzecie istnieje także wbudowana przestrzeń nazw, dostępna z każdego modułu, a która przechowuje funkcje wbudowane i wyjątki.

Każdorazowo, gdy dochodzi do wywołania jakiejś funkcji, tworzona jest nowa lokalna przestrzeń nazw. Nowa przestrzeń obejmuje nazwy parametrów funkcji, a także nazwy zmiennych używanych wewnątrz funkcji. Przystępując do rozwiązywania nazwy interpreter zaczyna od przeszukania lokalnej przestrzeni nazw, następnie jeżeli nie zostanie znaleziona poszukiwana nazwa interpreter przeszukuje przestrzeń globalną, w którym znajduje się funkcja. Jeżeli przeszukiwanie skończy się niepowodzeniem to przeszukiwana jest przestrzeń wbudowana.

W prezentowanym powyżej przykładzie zmienną lokalną jest zmienna a = 1 ponieważ znajduje się w bloku funkcji. Natomiast zmienną globalną, osiągalną z każdego poziomu programu jest zmienna a = 2. Znajduje się ona w bloku głównym programu. Nazwy tych zmiennych są takie same, ale ich zasięg już nie. Poćwicz i przesuń zmienną globalną w dowolne inne miejsce kodu, nie będące blokiem definicji funkcji.

Należy pamiętać, że przy przypisywaniu wartości poprzez zmienne, podczas wywoływania funkcji użyte zostaną takie wartości jakie miały obiekty podczas definicji.

Powyższy kod wyświetli zatem wartość 4 a nie, 2.

Interpreter Pythona, dopuszcza możliwość modyfikacji zmiennej globalnej w ciele funkcji. Aby zmienna zdefiniowana w bloku funkcji miała zasięg globalny, czyli de facto przypisana była do globalnej, a nie lokalnej przestrzeni nazw, należy poprzedzić ją instrukcją global:

Niekreślona ilość parametrów funkcji

Język Python dopuszcza by skonstruować funkcję, która nie będzie miała zdefiniowanej górnej liczby parametrów. Aby to zrobić należy nazwę listy parametrów funkcji poprzedzić symbolem *. Funkcję taką możemy wywołać z dowolną ilością argumentów. Kod zaprezentowany niżej to funkcja wykonująca sumę tylu elementów ile podane zostanie w krotki ją wywołującej.

O tym, że pod parametrem *args kryje się lista, można się łatwo przekonać, wystarczy na przykład, odwołać się do jej elementów poprzez indeksy. Funkcja z poniższego przykładu wypisze sumę drugiego i trzeciego elementu listy args. Zwróci natomiast błąd, jeśli długość krotki ją wywołującej będzie krótsza niż wskazuje na to indeks do którego się odwołujemy. Sprawdź to. .. a*

Jak taka konstrukcja będzie działać w połączeniu z innymi parametrami? Sprawdźmy:

Jak przekazać parametry z listy? Sprawdzmy to posługując się Zadaniem 107, z zestawu zadań do lekcji 1:

Zadanie 3.4

Wykorzystując funkcję, napisz program, który toworzy tabliczkę wartości wielomianu stopnia trzeciego:

\[f(x) = a x^3 + b x^2 + c x +d ,\]

dla conajmniej pięciu wartości x. Współczynniki a, b, c oraz d niech będa wartościami podawanymi przez użytkownika.

Zagnieżdżanie funkcji

Definicje funkcji mogą być zawierane w sobie w sposób jawny, tak jak w przykładzie wyliczającym wartość kosinusa kąta pomiędzy wektorami na płaszczyźnie:

Zadanie 3.5

Wykorzystując funkcję, napisz program, który dla podanych “a”, “b” oraz “c” znajduje rozwiązania trójmianu kwadratowego.

\[a x^2 + bx + c = 0\]

Niech program informuje o ilości tych rozwiązań oraz w zależności od ich ilości wypisuje wartości pierwiastków.

Mapowanie

Funkcja map(funkcja, lista) jest przykładem jednej z wielu funkcji wbudowanych. Jej działanie polega na tym, że buduje ona listę, której elementy są wartościami danej funkcji obliczonymi dla wszystkich elementów danej listy (krotki, słownika). Operację taką nazwiemy mapowaniem:

Rekurencja

Bardzo ważnym mechanizmem używanym w programowaniu, a ściśle powiązanym z algorytmiką, jest tak zwana rekurencja (termin używany często zamiennie z terminem rekursja).

Informacja

Rekurencja jest to sposób programowania, w którym funkcja lub definicja, odwołuje się raz lub więcej razy do samej siebie.

Źródłosłów słowa rekurencja wywodzi się z łacińskiego “recurrere”, co oznacza “przybiec do siebie”. Nasz ludzki sposób myślenia oparty jest na rekurencji. Wyobraźmy sobie, że mamy przed sobą stos porozrzucanych książek. Dostajemy zadanie by ułożyć książki na półce. Prawdopodobnie większość z nas rozwiąże to zadanie następująco: weźmiemy pierwszą książkę ze stosu, ułożymy ja na półce, a następnie zabierzemy się za pozostałą część stosu. Jak to zrobimy? Jak zrealizujemy drugą część zadania? Zapewne analogicznie do pierwszej. Weźmiemy drugą książkę ze stosu i położymy ją na półce. Następnie, wrócimy do stosu, weźmiemy trzecią książkę i ułożymy ją na półce. I tak będziemy postępować do momentu kiedy ułożymy wszystkie książki na półce. Proszę zwrócić uwagę na dwa fakty, już w tym miejscu stykamy się z pewnym sposobem postępowania. Przepisem na rozwiązanie problemu. Przepis ten będziemy nazywali algorytmem. I o tym będzie traktować dalsza część kursu. Uwaga druga: zwróćmy uwagę, że złożony problem został rozłożony na problemy elementarne, charakteryzujące się mniejszym stopniem skomplikowania, innymi słowy takie, które łatwiej jest rozwiązać w porównaniu do problemu wyjściowego. Rozłożenie problemu na łatwiejsze do rozwiązania składowe będziemy nazywali dekompozycją.

Wróćmy do definicji rekursji. W inny sposób można powiedzieć, że o rekurencji mówimy wtedy gdy definicja pewnego obiektu zawiera odwołanie do transformacji tego samego obiektu. Aby znaleźć transformację tego obiektu należy ponownie zastosować tę samą definicję. Nie będziemy się zachowywać rekurencyjnie i tej definicji powtarzać w nieskończoność nie będziemy. Dodajmy jedynie, że każda definicja rekurencyjna składa się z:

  • problemu bazowego (zwanego też wyrażeniem początkowym startowym lub warunkiem brzegowym)
  • zależności rekurencyjnej.

Matematyka obfituje w przykłady definicji rekurencyjnych, my wymienimy dwie z nich:

  • Silnia:
    \[\begin{split}n! = \left\{\begin{matrix} 1 \quad dla \quad n = 0 \\ n(n-1)! \quad dla \quad n \geqslant 1 \end{matrix}\right.\end{split}\]

    wyrażeniem startowe to: 0!=1, zależność rekurencyjna to: n!=n(n-1)!

  • Współczynnik dwumianowy:
    \[\binom{n}{k}= \binom{n-1}{k-1}+\binom{n-1}{k}\]

    (zależność rekurencyjna)

    \[\binom{n}{0}= \binom{n}{n} = 1\]

    (wyrażenie startowe)

Skupmy się na znanej zapewne definicji silni. Zaimplementujmy ją w Pythonie:

Wywołaj te funkcję, sprawdź, czy działa zgodnie z założeniami.

Spróbujmy prześledzić jak ta funkcja działa, zrobimy to poprzez dodanie dwóch funkcji print w ciele definicji funkcji:

Warto tu nadmienić, że rekurencja jest często alternatywną metodą rozwiązywania problemów do tak zwanej metody iteracyjnej. Podejście iteracyjne polega na n-krotnym wykonaniu algorytmu w taki sposób, aby wyniki uzyskane podczas poprzedniej iteracji (potocznie kroku, lub bardziej fachowo przebiegu) mogły służyć jako dane wejściowe do kroków kolejnych. Zazwyczaj iteracjami steruje się za pomocą instrukcji pętli. Lepiej, zapewne prześledzić to na przykładzie:

Rozpatrzmy jeszcze jeden, bardzo popularny przykład funkcji rekurencyjnej. Zdefiniujmy funkcję, ktora będzie liczyła elementy ciągu Fibonacciego:

\[\begin{split}F_n := \left\{\begin{matrix} 0 \quad dla \quad n = 0 \\ 1 \quad dla \quad n = 1 \\ F_{n-1} + F_{n-2}\quad dla \quad n > 1 \end{matrix}\right.\end{split}\]

Elementy tego ciągu to liczby naturalne mające taką własność, że kolejny wyraz (nie licząc dwóch pierwszych) jest sumą dwóch poprzednich:

\[\{1,1,2,3,5,8,13, \ldots \}\]

Ciąg ten jest specyficzny o tyle, że odzwierciedla wiele zjawisk zachodzących w przyrodzie. Często do zobrazowania tego przyjęło się posługiwać... królikami. Załóżmy, że:

  • zaczynamy z jedną parą królików,
  • każda para królików wydaje na świat, w miesiąc po kopulacji potomstwo: samicę i samca,
  • króliki są nieśmiertelne,
  • w miesiąc po urodzeniu, królik może przystąpić do reprodukcji.

Pomijając pewne niuanse będące przedmiotem innych rozważań, wzrost populacji takiej króliczej farmy opisany będzie właśnie ciągiem Fibonacciego. Pod koniec pierwszego miesiąca możemy się spodziewać pierwszego zapłodnienia w pierwszej parze królików. Pod upływie drugiego miesiąca pojawi się druga para królików. Na farmie będą już dwie pary. W trzecim miesiącu będziemy mieli już trzy pary. Pierwsza samica wyda na świat kolejne potomstwo, a urodzone wcześniej, przystpią do kopulacji. I tak dalej...

Taki ciąg łatwo jest zaimplementować w Pythonie:

Czy podobnie jak w poprzednim przykładzie, potrafiłbyś przekształcić ten kod tak, by za pomocą funkcji print prześledzić kolejne etapy jego wykonania? Spróbuj!

Dla porównania zaprezentujmy poniżej metodę iteracyjną wyliczania wartości elementów tego ciągu:

Zadanie 3.6

Napisz funkcję, która zaimplementuje trójkąt Pascala:

\[\begin{split}\begin{array}{ccccccccccc} & & & & & 1 & & & & & \cr & & & & 1 & & 1 & & & & \cr & & & 1 & & 2 & & 1 & & & \cr & & 1 & & 3 & & 3 & & 1 & & \cr & 1 & & 4 & & 6 & & 4 & & 1 & \cr 1 & & 5 & & 10 & & 10 & & 5 & & 1 \cr \dots \cr \end{array}\end{split}\]
Next Section - Zadania do lekcji 3