TI/Algorytmy i struktury danych/Rekurencja

Z Brain-wiki

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]\frac{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:

Przykład wyszukiwania binarnego

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)

Macierz.svg

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].
Źródło: „http://brain.fuw.edu.pl/edu/index.php?title=TI/Algorytmy_i_struktury_danych/Rekurencja&oldid=1934”