TI/Algorytmy i struktury danych/Rekurencja

Rekurencja

Rekurencja polega na rozwiązywaniu problemów przy następującym spostrzeżeniu: gdybyśmy mieli rozwiązanie danego problemu dla mniejszej liczby danych, to rozwiązanie dla obecnej byłoby banalne. Łatwo to zobaczyć na poniższym przykładzie z obliczaniem silni:

Przykład — obliczanie silni

Silnia przedstawia się następującą zależnością matematyczną:

[math]n! = \prod_{k=1}^n k[/math]

Rekurencyjnie

Silnię można zapisać jako równanie rekurencyjne:

[math]\begin{matrix} &b_n = n\cdot b_{n-1}\\ &b_0 = 1\end{matrix}[/math]

Jak wygląda to w praktyce? Zobaczmy, co dzieje się, gdy chcemy obliczyć [math]b_4[/math]

Rekurencyjne obliczanie silni dla n = 4:
b4 = 4 * b3 = 4 * 3 * b2 = 4 * 3 * 2 * b1 = 4 * 3 * 2 * 1 * b0 = 4 * 3 * 2 * 1 * 1 = 4 * 3 * 2 * 1 = 4 * 3 * 2 = 4 * 6 = 24

Jak zapiszemy to równanie rekurencyjne w Pythonie?

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

Iteracyjnie

Silnię można oczywiście obliczyć iteracyjnie, co jest daleko bardziej wydajne.

def silnia(n):
    silnia = 1
    for i in xrange(2, n+1):
        silnia *= i
    return silnia

Przerywnik

Uruchom teraz silnia(999) i silnia(998). Co zauważasz? W pythonie jest domyślnie ustawione ograniczenie na głębokość stosu wykonania programu = 1000. Limit ten można zmienić w następujący sposób:

import sys

sys.setrecursionlimit(1500)

Ale też nie w nieskończoność. Żeby uniknąć takich problemów, optymalizuje się programy rekurencji tak, aby stosować tzw rekurencję ogonową:

def even(x):
  if x == 0:
    return True
  else:
    return odd(x - 1)

def odd(x):
  if x == 0:
    return False
  else:
    return even(x - 1)

def tail_rec(fun):
   def tail(fun):
      a = fun
      while callable(a):
         a = a()
      return a
   return (lambda x: tail(fun(x)))

def tail_even(x):
  if x == 0:
    return True
  else:
    return (lambda: tail_odd(x - 1))

def tail_odd(x):
  if x == 0:
    return False
  else:
    return (lambda: tail_even(x - 1))

even = tail_rec(tail_even)
odd = tail_rec(tail_odd)

Do czego rekurencja będzie wygodna?

<korzen litera="d">
	<lewy litera="b">
		<lewy litera="a">
		</lewy>
		<prawy litera="c">
		</prawy>
	</lewy>
	<prawy litera="f">
		<lewy litera="e">
		</lewy>
		<prawy litera="g">
		</prawy>
	</prawy>
</korzen>

• Napisz program, który wczyta następujące drzewo xml i wypisze je w porządku infiksowym.
• Napisz program, który z zadanego ciągu znaków utworzy analogiczne drzewo xml, tak, aby po wypisaniu go w porzadku infiksowym otrzymać wyjściowy ciąg znaków.
• Spróbuje oba problemu rozwiązać zarówno iteracyjnie, jak rekurencyjnie. Ile linii kodu zajęło Ci rozwiązanie iteracyjne, a ile rekurencyjne? Ile razy szybciej udało Ci się napisać rozwiązanie rekurencyjnie? Ile razy pomyliłeś się pisząc rozwiązanie iteracyjne, a ile rekurencyjne?

Ciąg Fibonacciego

def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Ciągu Fibonacciego od liczby 4 — schemat wywołań funkcji w pierwszej gałęzi.

Wyszukiwanie binarne

Szukanie za pomocą bisekcji jest jednym z najbardziej intuicyjnych sposobów szukania wartości w uporządkowanym wektorze, czy sekwencji. Wyobraź sobie, że musisz znaleźć liczbę 54 w sekwencji składającej się z [math]N[/math] liczb od 1 do 90. Zgadywałbyś zapewne, że 54 jest to element [math]\nicefrac{N}{2}[/math]. Jeżeli nie trafisz, sprawdzisz, czy wybrany element jest większy, czy mniejszy od 54. Jeżeli jest mniejszy, poszukasz go w połowie lewej części sekwencji. Jeżeli jest większy, poszukasz go w połowie prawej części sekwencji. Tak jak na rysunku:

Jeżeli w którymś momencie lewa granica sekwencji okaże się większa niż prawa, podzieliłeś sekwencję na 2 o raz za dużo i nie masz już w czym szukać. Zwracasz wtedy -1, na znak tego, że nie znalazłeś.

Rozwiązanie rekurencyjne tego algorytmu jest intuicyjne i sprowadza się do zapisu w poleceniami powyżej opisanej procedury. Poniżej kod w Pythonie.

def znajdz(lista, lewy, prawy, x):
    if lewy>prawy:
        raise IndexError
    srodek = (lewy + prawy) / 2
    if lista[srodek] == x:
        return srodek
    if lista[srodek] > x:
        return znajdz(lista, lewy, srodek - 1, x)
    else:
        return znajdz(lista, srodek + 1, prawy, x)

Zadanie

Rozwiąż ten problem iteracyjnie.

Wieże Hanoi

Wieże Hanoi: Od lewej: słupek A z całą wieżą, pusty słupek B pełniący rolę bufora i pusty słupek docelowy C.

Wieże Hanoi są łamigłówką matematyczną przypominającą dziecięcą zabawkę. Tak, jak na rysunku Figure 2 mamy trzy słupki, oznaczone A, B i C. Na słupku A znajduje się wieża — ułożone na sobie dyski, o zmniejszającej się średnicy. Słupki B — pełniący rolę bufora; i C — będący słupkiem docelowym; są puste. Zadanie polega na przeniesieniu całej wieży ze słupka A na słupek C, zachowując zależność im wyższy dysk, tym mniejsza jego średnica, posługując się słupkiem B jako buforem. Dodatkowo:

• W każdym kroku można przenieść tylko jeden dysk.
• Krok polega na przeniesieniu dysku z wybranego słupka na inny słupek i umieszczeniu go na dyskach, które znajdują się na danym słupku.
• Dysk o większej średnicy nigdy nie może znaleźć się nad dyskiem o mniejszej średnicy.

Rozwiązanie rekurencyjne

Jest banalnie proste.

• Przenieść wieżę z [math]n-1[/math] dysków ze słupka A na słupek B.
• Przenieść jeden dysk na słupek C.
• Przenieść wieżę z [math]n-1[/math] dysków ze słupka B na słupek C.

Rozwiązanie iteracyjne

Wieże Hanoi: Animacja pokazująca rozwiązanie łamigówki.

Rozwiązanie takiego problemu z wieżą o czterech dyskach można zobaczyć na animacji na rysunku Figure 3.

• Na początku należy przenieść najszerszy dysk — pomarańczowy, ze słupka A na słupek C. W tym celu:
  • czerwony na B,
  • żółty na C,
  • czerwony na C,
  • niebieski na B,
  • czerwony na A,
  • żółty na B,
  • czerwony na B.
• Uwolniony pomarańczowy jest na słupku A. Słupek C jest wolny. Pomarańczowy przechodzi na C.
• Teraz należy przenieść niebieski na C.
  • czerwony na C,
  • żółty na A,
  • czerwony na A.
• Uwolniony niebieski jest na słupku B. Na słupku C jest wyłącznie pomarańczowy. Niebieski przechodzi na C.
• Teraz należy przenieść żółty na C.
  • czerwony na B.
• Żółty jest wolny na A, można go przenieść na C.
• Czerwony zostaje przeniesiony na C.

Łamigłówkę udało się rozwiązać.

Algorytm iteracyjny

1. W przypadku parzystej liczby krążków:
   • wykonaj dozwolone przeniesienie pomiędzy słupkami A i B,
   • wykonaj dozwolone przeniesienie pomiędzy słupkami A i C,
   • wykonaj dozwolone przeniesienie pomiędzy słupkami B i C,
   • powtarzaj, aż przeniesiesz wszystkie.
2. W przypadku nieparzystej liczby krążków:
   • wykonaj dozwolone przeniesienie pomiędzy słupkami A i C,
   • wykonaj dozwolone przeniesienie pomiędzy słupkami A i B,
   • wykonaj dozwolone przeniesienie pomiędzy słupkami B i C,
   • powtarzaj, aż przeniesiesz wszystkie.

Wykonano [math]2^n-1\;[/math] ruchów.

Jak widać opis rekurencyjny jest prostszy niż iteracyjny.

Zadanie

Napisz program, który implementuje algorytm iteracyjny i rekurencyjny. Załóż, że słupki A, B i C są listami. Lista A jest wypełniona "dyskami" — liczbami albo słowami, listy B i C są puste. Sprawdź swój program na dwóch zestawach danych:

• A1 =['duzy', 'sredni', 'maly']
  

• A2 =['bardzo duzy', 'duzy', 'sredni', 'maly', 'bardzo maly']
  

Zadania różne

Rozwiąż następujące zadania

Wyznacznik macierzy (obliczany z definicji)

Napisz funkcję

def wyznacznik_1(macierz):
     "Oblicza wyznacznik korzystając z definicji."

która oblicza wyznacznik macierzy macierzy korzystając z rekurencyjnej definicji wyznacznika.

Przypomnienie: jeśli [math]M[/math] jest macierzą kwadratową o wymiarze [math]n[/math], to jej wyznacznik wynosi

[math]\left|M\right| = \sum_{k=1}^n(-)^{i+k} a_{ik} \left|M_{/i/k}\right|[/math]

gdzie [math]i[/math] jest dowolne, a [math]M_{/i/k}[/math] oznacza macierz o wymiarze zmniejszonym o 1 przez wykasowanie wiersza [math]i[/math] oraz kolumny [math]j[/math].

Sprawdź swoją funkcję na macierzy jednostkowej różnych rozmiarów, na macierzy wypełnionej jedynkami lub zerami i na paru małych macierzach dla których jesteś w stanie samemu policzyć wynik.

Uwaga o funkcjach rekurencyjnych
Funkcje mogą wywoływać same siebie. Funkcja f może też wywoływać inne funkcje, które wywołają f jeszcze raz. Tak czy inaczej, w pewnym momencie, funkcja f jest wykonywana jednocześnie dwa (lub więcej) razy. W momencie wywołania przez funkcję f funkcji potomnej, to wykonanie zostaje zawieszone — stan zmiennych i miejsce wykonywania jest zapamiętane. Funkcja zostaje wznowiona, kiedy funkcja potomna zakończy działanie.

Z rekurencyjnym wywoływaniem funkcji nie należy przesadzać. Np. obliczenie miliona liczb Fibonnaciego z definicji — w sposób rekurencyjny — raczej nie jest dobrym pomysłem. Obliczanie ich w pętli jest dużo, dużo szybsze. Niemniej, funkcje rekurencyjne są zazwyczaj bardzo czytelne i podobne do definicji matematycznych.

Macierz odwrotna

Jeżeli wyznacznik macierzy M jest niezerowy (macierz jest niezdegenerowana), można pokusić się o znalezienie macierzy odwrotnej.

[math] A^{-1}=\frac{A^D}{\vert A\vert } [/math]

Macierz [math]A^D[/math] jest macierzą dołączoną do macierzy A.

Macierz dołączona powstaje po transponowaniu macierzy dopełnień algebraicznych.

Element [math]ij[/math] macierzy dopełnień algebraicznych to wyznacznik macierzy powstałej z [math]A[/math] poprzez skreślenie jej [math]i[/math]-tego wiersza i [math]j[/math]-tej kolumny, pomnożony przez [math](-)^{i+j}[/math].

[math] A^D_{ji} = \vert A_{/i /j} \vert (-)^{i+j} [/math]

Napisz program, który:

1. wczyta macierz;
2. sprawdzi, czy nie jest osobliwa;
3. jeżeli nie jest osobliwa, obliczy macierz odwrotną;
4. i sprawdzi, czy iloczyn macierzy i macierzy odwrotnej daje macierz [math]I[/math].