Rekurencja

Czym jest rekurencja?

Rekurencja to metoda rozwiązywania złozonych problemów w taki sposób, że że wynik końcowy jest oparty o rozwiązanie innych instancji tego samego problemu.

Problem: Obliczanie procentu składanego: odsetki za dany rok doliczane są do sumy kapitału.

rok stan konta oprocentowanie odsetki nowy stan konta
1 1000 5% 50 1050
2 1050 5% 52.5 1102.5
3 1102.5 5% 55.125 1157.625

Stan konta po 1,2,3 latach:

\(f_1(s) = s + s p\)

\(f_2(s) = (s + s p) + (s + s p) p\)

\(f_3(s) = ((s + s p) + (s + s p) p) + ((s + s p) + (s + s p) p) p\)

Rekurencyjnie:

\(f_1(s) = s + s p\)

\(f_2(s) = f_1(s) + f_1(s) p\)

\(f_3(s) = f_2(s) + f_2(s) p\)

Stan konta po \(i\) latach:

\(f_i(s) = f_{i-1}(s) + f_{i-1}(s) p\)

\(f_0(s) = s\)

Rozwiązanie z rekurencją:

def compound_interest(sum, years):
    if not years:
        return sum
    compound_sum = compound_interest(sum, years - 1)
    return compound_sum + compound_sum * 0.05

def compoundInterest(sum: Double, years: Int): Double  =
    years match {
        case 0 => sum
        case _ => {
            val compoundSum = compoundInterest(sum, years - 1)
            compoundSum + compoundSum * 0.05
        }
    }

Rozwiązanie z pętlą:

def compound_interest(sum, years):
    compound_sum = sum
    for (i in range(0, years)):
        compound_sum = 0.05 * compound_sum + compound_sum
    return compound_sum

def compoundInterest(sum: Double, years: Int): Double = {
    var compoundSum = sum
    for (i <- 0 until years)
        compoundSum = 0.05 * compoundSum + compoundSum
    compoundSum
}

Wady i zalety rekurencji

  • Twierdzenie Church’a-Rosser’a
  • Brak modyfikacji globalnej pamięci
  • Bardziej eleganckie rozwiązanie: krótsze, “czystsze” (np. iteracja po liście vs rekurencja po liście)
def count(l: List[Any]): Int =
    l match {
        case Nil     => 0
        case _::tail => 1 + count(tail)
    }
  • Łatwiej odkryć i naprawić błędy
  • Problemy których rozwiązania są naturalnie (albo z definicji) rekurencyjne (np. problemy matematyczne, finansowe, analiza statyczna, struktury drzewiaste)
  • Można udowodnić poprawność zachowania (indukcja)
  • Cacheing
  • Powolniejsze (np. alokacja stosu), bardziej pamięciochłonne, problem z wielkością stosu
  • Mniej intuicyjne, wymagają więcej wprawy żeby implementować efektywne algorytmy
def fib(n: Int): Int =
    n match {
        case 0 | 1 => 1
        case _     => fib(n - 2) + fib(n - 1)
    }

Rekurencja ogonowa

Problem z rekurencją i stosem:

compound_interest(1000, 1000)

compoundInterest(1000,1000)
compoundInterest(1000,100000)

Res Caudarum

  • Wywołanie ogonowe
  • Rekurencja ogonowa
  • Optymalizacja rekurencji ogonowej (tail call elimination)
def compound_interest(sum, years, counter):
    if counter == years:
        return sum
    return compound_interest(sum + sum * 0.05, years, counter + 1)

import scala.annotation.tailrec

@tailrec
def compoundInterest(sum: Double, years: Int, counter: Int): Double  =
    if (counter == years)
        sum
    else
        compoundInterest(sum + sum * 0.05, years, counter + 1)

Utrzymanie sygnatury funkcji:

def inner_compound_interest(sum, years, counter):
    if counter == years:
        return sum
    return inner_compound_interest(sum + sum * 0.05, years, counter + 1)

def compound_interest(sum, years):
    return inner_compound_interest(sum, years, 0)

import scala.annotation.tailrec

@tailrec
def innerCompoundInterest(sum: Double, years: Int, counter: Int): Double =
    if (counter == years)
        sum
    else
        innerCompoundInterest(sum + sum * 0.05, years, counter + 1)

def compoundInterest(sum: Double, years: Int): Double  =
    innerCompoundInterest(sum, years, 0)

Funkcje zagnieżdżone:

def compound_interest(sum, years):
    def inner_compound_interest(sum, years, counter):
        if counter == years:
            return sum
        return inner_compound_interest(sum + sum * 0.05, years, counter + 1)
    return inner_compound_interest(sum, years, 0)

import scala.annotation.tailrec

def compoundInterest(sum: Double, years: Int): Double = {
    @tailrec
    def innerCompoundInterest(sum: Double, years: Int, counter: Int): Double  =
        if (counter == years)
            sum
        else
            compoundInterest(sum + sum * 0.05, years, counter + 1)
    innerCompoundInterest(sum, years, 0)
}

Trampolinowanie

Rozwiązanie problemu wsparcia dla rekurencji ogonowej w językach niefunkcyjnech (np. Python). Trampolinowanie to wykonnanie rekurencji za pomocą iteracji.

def compound_interest(sum, years):
    def inner_compound_interest(sum, years, counter):
        if counter == years:
            return (False, sum, years, counter)
        return (True, sum + sum * 0.05, years, counter + 1)

    def trampoline(s_sum, s_years, s_counter):
        iterate, sum, years, counter = True, s_sum, s_years, s_counter
        while iterate:
            iterate, sum, years, counter = inner_compound_interest(sum, years, counter)
        return sum

    return trampoline(sum, years, 0)

Uniwersalne rozwiązanie – Tail Call Optimization Decorator (Python recipe):

@tail_call_optimized
def compound_interest(sum, years):
    def inner_compound_interest(sum, years, counter):
        if counter == years:
            return sum
        return inner_compound_interest(sum + sum * 0.05, years, counter + 1)
    return inner_compound_interest(sum, years, 0)

Ankieta

Ćwiczenia

  1. Problem: Zaimplementuj funkcję obliczającą silnię dla dowolnej liczby na trzy sposoby:

    • prosta rekurencja,
    • rekurencja ogonowa,
    • iteracja.

    Porównaj czasy wykonania funkcji zaimplementowanej dla w/w sposobów dla określonej domeny.

    Extra credit: porównaj wykonanie rekurencji ogonowej w Pythonie i w Scali. Zaimplementuj i ewaluuj rozwiązanie z trampoliną w Pythonie.

  2. Problem: Zaimplementuj funkcję obliczającą \(i\)-tą wartość ciągu Fibonacciego j/w.

  3. Problem: Zaimplementuj rekurencyjne funkcje które dla listy liczb całkowitych obliczają:

    • maksymalną i minimalną wartość na liście,
    • sumę wartości na liście,
    • średnią z wartości na liście.
  4. Problem: Zaimplementuj funkcję cenzury. Funkcja przyjmuje listę słów

    zabronionych i listę słów stanowiącą jakąś treść. Każde słowo w treści, które znajduje się na liście słów zabronionych jest zastąpione napisem [OCENZURWANO] w wynikowej liście słów.

  5. Problem: Przerób zadanie [Scala0] zastępując iterację rekurencją.

  6. Problem: Używając rekurencji napisz funkcję która liczy na ile sposobów można rozmienić wskazaną wartość pieniężną mając daną listę nominałów monet. Np. mając do dyspozycji walutę § w której występują monety o nominałach 1 i 2 wartość pieniężną 4§ mozna rozmienić na 1, 1, 2 lub na 1, 1, 1, 1, czyli na dwa sposoby.

  7. Problem: Zaimplementuj rekurencyjną funkcję łączącą dwie listy.

Zadanie [Scala1]

Zaimplementuj w Scali generyczne drzewo binarne z funkcją dodawania, usuwania, przeszukiwania i przechodzenia (traveresal) używając rekurencji.

Umieść rozwiązanie zadania w repozytorium DSG.