Rekurzia a funkcionálne programovanie

Rekurzia

Rekurzia znamená, že funkcia volá samu seba.

Používa sa pri problémoch, ktoré sa dajú rozdeliť na menší problém rovnakého typu:

  • faktoriál,
  • prechádzanie stromu,
  • spracovanie vnorených štruktúr,
  • spätné prehľadávanie.

Rekurzia namiesto cyklu

Namiesto opakovania pomocou cyklu môžeme problém zmenšovať pomocou volania tej istej funkcie.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Dve časti rekurzie

Každá rekurzívna funkcia potrebuje:

  • podmienku ukončenia – prípad, ktorý už nevolá ďalšiu rekurziu,
  • rekurzívny krok – volanie tej istej funkcie s menším alebo jednoduchším vstupom.
def factorial(n):
    if n == 0:          # podmienka ukončenia
        return 1
    return n * factorial(n - 1)  # rekurzívny krok

Priebeh výpočtu

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1 * factorial(0)
= 4 * 3 * 2 * 1 * 1
= 24

Najprv sa volania skladajú na zásobník, potom sa výsledky postupne vracajú späť.

Rekurzívne prechádzanie zoznamu

def sum_list(items):
    if not items:
        return 0
    return items[0] + sum_list(items[1:])

print(sum_list([1, 2, 3, 4]))

Výsledok:

10

Rekurzia vs cyklus

Rekurzia:

  • dobre vyjadruje hierarchické a vnorené štruktúry,
  • často je čitateľná pri stromoch a spätnom prehľadávaní,
  • používa volací zásobník.

Cyklus:

  • je často efektívnejší pri jednoduchom opakovaní,
  • nemá riziko prekročenia limitu rekurzie,
  • býva vhodnejší pre veľké sekvencie.

Limit rekurzie v Pythone

Python obmedzuje maximálnu hĺbku rekurzie.

import sys

print(sys.getrecursionlimit())

Pri príliš hlbokej rekurzii vznikne:

RecursionError

Čo je funkcionálne programovanie?

Funkcionálne programovanie (FP) je štýl programovania, kde:

  • funkcie sú hlavné stavebné bloky
  • vyhýbame sa meneniu dát (nemeniteľnosť), snažíme sa nemať vedľajšie efekty (napr. meniť globálne premenné)

Čisté funkcie

Čistá funkcia:

  • vždy vráti rovnaký výsledok pre rovnaký vstup
  • nemá vedľajšie efekty
         +---------+
vstup -> | funkcia | -> výstup
         +---------+

Čisté funkcie nemajú vedľajšie efekty

stav 1 je vstup -> funkcia -> výstup je stav 2

  • menej chýb spôsobených zmenou stavu
  • jednoduchšie testovanie a ladenie
  • ľahšia paralelizácia a distribuované spracovanie
def add(a, b):
    return a + b

Funkcia s vedľajším efektom

            stav
            ^   |
            |   v
         +---------+
vstup -> | funkcia | -> výstup
         +---------+
              |
              v
          vedľajší efekt

Funkcia s vedľajším efektom zmení stav sveta okolo seba (terminál, súbor, sieť, pamäť...)

Dve zavolania takej funkcie môžu mať dva rôzne výsledky

total = 0

def add(a):
    global total
    print("Ahoj Svet")
    total += a

Testovanie čistých funkcií

Čisté funkcie sa testujú jednoducho, lebo:

  • nepotrebujú globálny stav,
  • nemenia okolie programu,
  • rovnaký vstup vždy dá rovnaký výstup.
def add(a, b):
    return a + b

Test znamená overiť očakávaný výsledok:

assert add(2, 3) == 5

Funkcie sú objekty

V Pythone sú funkcie plnohodnotné objekty, čo znamená:

  • môžeš ich uložiť do premennej
  • môžeš ich posielať ako argument
  • funkcia môže byť návratovou hodnotou inej funkcie

Lambda funkcie

Funkciu je možné uložiť do premennej, alebo odobzdať ako hodnotu

Lambda = anonymná (krátka) funkcia

square = lambda x: x * x
print(square(4))

Triedenie pomocou lambda funkcie

Pomocou sorted a lambda je možné triediť zoznamy slovníkov podľa kľúča. Lambda vyjadruje spôsob ako získať hodnotu, podľa ktorej sa má triediť.

data = [
    {"name": "Alice", "age": 30},
    {"name": "Bob", "age": 25},
    {"name": "Charlie", "age": 35},
]

sorted_data = sorted(data, key=lambda x: x["age"])

Funkcie vyššieho rádu

Funkcia, ktorá:

  • berie inú funkciu ako argument
  • alebo ju vracia
def apply_function(f, x):
    return f(x)

print(apply_function(lambda x: x * 2, 5))

Funkcie vyššieho rádu pre spracovanie zoznamov

  • map
  • filter
+-----------------+     +---------+   +-----------------+
| vstupný zoznam  |  →  | funkcia | → | výstupný zoznam |
+-----------------+     +---------+   +-----------------+
  • reduce
+---------+    +---------+   +--------+
| zoznam  | →  | funkcia | → |hodnota |
+---------+    +---------+   +--------+

map()

Zoznam vstupov vytvorí zoznam výstupov podľa zadanej funkcie.

numbers = [1, 2, 3]
result = list(map(lambda x: x * 2, numbers))

🔵 filter()

Podľa zadanej funkcie vyberie zoznam vstupov, ktoré spĺňajú podmienku.

numbers = [1, 2, 3, 4]
result = list(filter(lambda x: x % 2 == 0, numbers))

🔴 reduce() – redukuje na jednu hodnotu

Funkcia má dva operandy. Prvý operand je akumulátor, druhý je aktuálny prvok zoznamu. Výsledok sa stáva novým akumulátorom.

numbers = [1, 2, 3, 4]
a = numbers[0]  # a = 1
a = f(a, numbers[1])  # a = f(1, 2)
a = f(a, numbers[2])  # a = f(f(1, 2), 3)
a = f(a, numbers[3])  # a = f(f(f(1, 2), 3), 4)
from functools import reduce

numbers = [1, 2, 3, 4]
result = reduce(lambda x, y: x + y, numbers)

Odvodenie zoznamu - list comprehension

Python má elegantnejšiu alternatívu k map a filter:

numbers = [1, 2, 3, 4]

result = [x * 2 for x in numbers if x % 2 == 0]

Uzáver - Closure

Uzáver zostaví funkciu na požiadanie podľa zadaných parametrov.

def multiplier(n):
    def multiply(x):
        return x * n
    return multiply

double = multiplier(2)

print(double(5))

Dekorátory sú funkcie vyšieho rádu

Dekorátor je funkcia, ktorá:

  • berie funkciu ako argument,
  • vracia novú funkciu (uzáver) s pridanou logikou.
import time

def meraj_cas(f):
    def obalka(*args, **kwargs):
        start = time.perf_counter()
        result = f(*args, **kwargs)
        end = time.perf_counter()
        print(f"{f.__name__}: {end - start:.4f}s")
        return result
    return obalka

@mer_cas
def pomaly_vypocet():
    total = sum(i ** 2 for i in range(10_000_000))
    return total

pomalý_výpočet()
# pomalý_výpočet: 2.1342s

Cache pre fukcie s @lru_cache

Systém si zapamätá výsledky funkcie pre rovnaké vstupy, takže sa nemusí opakovane počítať.

Funkcia by mala byť čistá (bez vedľajších efektov), aby sa dala bezpečne cache-ovať.

Urýchľuje rekurziu

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))     # 12586269025  — okamžite (niekoľko ms)
                       # bez @lru_cache by trvalo minúty

Dekorátor s parametrami

Parametre cez dvojitý uzáver:

def opakovane(n):
    def decorator(f):
        def obalka(*args, **kwargs):
            for _ in range(n):
                result = f(*args, **kwargs)
            return result
        return obalka
    return decorator

@opakovane(3)
def ahoj():
    print("Ahoj")

ahoj()
# Ahoj
# Ahoj
# Ahoj

Generátory (voliteľné)

Nie sú úplne FP, ale často sa používajú spolu s ním.

numbers = (x * 2 for x in range(10))

for n in numbers:
    print(n)

Praktický príklad: Dátový pipeline

Problém: Zoznam objednávok odfiltrovať tie s nulovou sumou, vypočítať DPH z každej a získať celkovú sumu bez DPH.


orders = [
    {"id": 1, "amount": 100, "vat_rate": 0.20},
    {"id": 2, "amount": 0, "vat_rate": 0.20},  # vyraď
    {"id": 3, "amount": 250, "vat_rate": 0.10},
    {"id": 4, "amount": 80, "vat_rate": 0.20},
]

Riešenie funkcionálnym štýlom

from functools import reduce
# 1. Odfiltrujeme nulové objednávky
active = list(filter(lambda o: o["amount"] > 0, orders))
# 2. Pripočítame DPH
with_vat = list(map(
    lambda o: {**o, "vat": o["amount"] * o["vat_rate"]},
    active
))
# 3. Spočítame celkovú sumu bez DPH
total = reduce(lambda acc, o: acc + o["amount"], with_vat, 0)

Riešenie pomocou list comprehension

active = [o for o in orders if o["amount"] > 0]
with_vat = [{**o, "vat": o["amount"] * o["vat_rate"]} for o in active]
total = sum(o["amount"] for o in with_vat)

Riešenie imperatívnym štýlom

total = 0
for order in orders:
    if order["amount"] > 0:
        vat = order["amount"] * order["vat_rate"]
        total += order["amount"]

Teaser: Objektové programovanie je opak funkcionálneho - metródy tried menia stav objektu..

Reload?