Rekurencja
Recursive approach
Rekurencja
Rekurencja  technika pozwalająca opisać problem za pomocą jego składowych.
Rekurencja - element struktury algorytmicznej, który definiuje wartość ogólną
określonych wielkości za pomocą ich wcześniejszych wartości i podaje warunek
stopu.
Rekurencja (w ogólnym przypadku) - definiuje nowe obiekty za pomocą obiektów
wcześniej zbudowanych w szczególności z obiektów podstawowych.
Rekurencja pozwala tworzyć:
Przejrzyste struktury algorytmów,
Wydajne struktury danych.
ASD LJ S
1
Przykład rekurencji
Struktura katalogów postaci drzewa Gałęzie drzewa są drzewami
(directory tree)
ASD LJ S
Rekurencja i myślenie rekurencyjne
(x ,y )
(x,y)
Elementy myślenia rekurencyjnego:
1. Przypadek podstawowy
2 Reguła indukcyjna
ASD LJ S
2
Definicje rekurencyjne
1. Przypadek podstawowy (basis case)  wyszczególnienie obiektów podstawowych,
2. Przypadek ogólny (general case) - reguła (inductive step) umożliwiająca
konstruowanie nowych obiektów z wcześniej zbudowanych lub podstawowych.
Rekurencyjne konstruowanie zbioru N liczb naturalnych.
Definicja 1.
1. 0"N,
2. Jeżeli n"N, to (n+1) n"N,
3. Nie ma żadnych innych obiektów w zbiorze N oprócz tych, których istnienie
wynika z reguł 1 i 2.
Definicja 2.
1. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 "N
2. Jeżeli n"N, to n0, n1, n2, n3, n4, n5, n6, n7, n8, n9 "N.
3. Obiekty utworzone za pomocą reguł 1, 2 są jedynymi liczbami naturalnymi.
ASD LJ S
Definicje rekurencyjne
a0 = 1 k=0
1 n = 0
cA =
f(n) =
1
ak = ak-1+ const k>0
f(n-1) + n e" 1
f(n-1)
0 n = 0
1 n = 0
fn = 1 n = 1
n! =
fn-1+ fn-2 n > 1
n * (n-1)! n > 0
ASD LJ S
3
Implementacja rekurencji
Przejście od rekurencyjnej definicji funkcji do implementacji wymaga tłumaczenia
tej definicji na składnię języka programowania.
Pamięć programu
Program Procedura A
Kod
Instrukcje Parametry
Zmienne lokalne
Dane statyczne
Wywołanie A
Instrukcje
Stos programu
Instrukcje
.. Zwracana wartość
Instrukcje Sterta
Wykorzystanie stosu do impelementacji rekurencji (Dijkstra E).
ASD LJ S
Implementacja rekurencji
Pamięć programu
Rekord aktywacji (activation record):
Kod
Parametry wywołania
Zmienne lokalne
Dane statyczne
Wartość zwracana
Dynamiczne dowiązanie - wskaz
nik do
Stos programu
rekordu wywołania procesu wywołującego
Adres powrotu do procesu wywołania.
Sterta
Wykorzystanie stosu do impelementacji rekurencji (Dijkstra E.).
ASD LJ S
4
REKORD AKTYWACJI
REKORD AKTYWACJI
e
i
n
a
ł
o
w
y
w
p
o
w
r
ó
t
Pamięć programu
Obszar danych statycznych - dane dostępne
Kod
przez cały czas wykonywania programu np.
Dane statyczne
zmienne globalne i statyczne zmienne
lokalne.
Stos programu
Sterta - pamięć alokowana dynamicznie.
Stos programu - informacje o wywołaniach
funkcji.
Sterta
ASD LJ S
Implementacja rekurencji
Zasada wielostopniowego, rekurencyjnego wywołania procedury (funkcji).
Procedura B
Program główny Procedura A
ASD LJ S
5
e
i
n
a
ł
o
w
e
y
i
w
n
a
ł
o
w
y
w
e
i
n
a
ł
o
w
y
w
p
o
w
r
ó
t
p
o
w
r
ó
t
t
ó
r
w
o
p
Algorytmy rekurencyjne
Recursive algorithms
Algorytmy rekurencyjne
1. Rekurencja jest elementem struktury algorytmicznej.
2. W algorytmie rekurencyjnym można wyodrębnić:
a) przypadek bazowy
b) przypadek ogólny
3. Podstawowymi elementami przy układaniu algorytmów rekurencyjnych są:
a) warunek kończący algorytm (warunek stopu)
b) dekompozycja problemu
4. Rekurencja, z reguły pozwala na przejrzysty i zwarty opis algorytmu.
ASD LJ S
6
Schemat wywołań rekurencyjnych
Drzewo rekurencji dla problemu P o rozmiarze n.
PROBLEM P (rozm: n)
PROBLEM P (rozm: (n-1))
.
.
.
PROBLEM P (rozm: jednostkowy)
Spełniony warunek początkowy
ASD LJ S
Drzewo rekurencji
Obliczanie n! dla danego n.
1 dla n = 0 // warunek początkowy
n! =
n! = n(n-1)! dla n e" 1 // krok indukcyjny
3! 3 *2!
silnia ( n )
2!
2 *1!
silnia ( n-1 )
1! 1 *0!
. . . . .
1
0!
spełniony war. początkowy
silnia ( 0 )
spełniony warunek początkowy
Drzewo rekurencji dla 3!
ASD LJ S
7
Kierunek budowy drzewa rekurencji
Kierunek powrotu
Algorytmy rekurencyjne
Problem: rekurencyjne obliczanie wartości n! .
Dane wejściowe: dodatnia całkowita liczba n.
0 n =0
Dane wyjściowe: wartość n! .
T(n) =
T(n-1)+1 n e"1
Silnia (n) //alg. rekurencyjny
T(0) = 0
{
IF (n==0)
T(1) = 1
return(1);
T(2) = 2
ELSE
...............
return(n*silnia(n-1));
T(n) = n
}
Założenie: T(n) = n
Teza: T(n+1) = n+1
�! T(n+1) = T(n)+1 = n+1
�! T(n+1) = n+1 = T(n) +1
Złożoność obliczeniowa algorytmu T(n) = O(n)
ASD LJ S
Algorytm iteracyjny
Iteracyjna implementacja n!
Silnia (n)// alg. iteracyjny
{
i=2;
f=1;
WHILE ( i d" n ) {
f = f * i;
i = i + 1;
}
return (f)
}
Złożoność obliczeniowa algorytmu:
T(n) = n -1
T(n) = O(n)
ASD LJ S
8
Algorytmy rekurencyjne
Problem: rekurencyjne wyszukiwanie binarne.
Dane wejściowe: dodatnia całkowita liczba n, klucz x, posortowana tablica A.
Dane wyjściowe: lokalizacja klucza.
Bs_rec(A,p,k,x)// alg. rekurencyjny
{
IF (p>k){
return(0);
ELSE
q=�ł(p+k)/2�ł;
IF (x == A[q])
return(q);
ELSE IF (x < A[q])
Bs_rec(A,p,q-1,x);
ELSE Bs_rec(A,q+1,k,x)
}
}
Wywołanie: Bs_ rec (A, 1, n, x)
ASD LJ S
Algorytmy rekurencyjne
Równwanie rekurencyjne wyszukiwania binarnego.
T(n) = T(n/2) + 1
Porównania w wywołaniu Porównanie na
rekurencyjnym najwyższym poziomie
1 n=1
T(n) =
T(n/2) + 1 n>1, n=2k
T(n) = T(n/2) + 1= (T(n/4) + 1 ) + 1 = .... = ((...(T(n/2k)))) + k = T(1) + k = 1 + log n
T(n) = O(logn).
Dw.
T(2n) = lg (2n)+1=lgn +lg2+1=(lgn+1)+1=T(n)+1
�! T(2n) =T(n)+1=lgn+1+1= (lgn+1)+1=lg2n + 1
�!
�!
�!
ASD LJ S
9
Algorytmy rekurencyjne
0 dla n=0
Problem: ciąg Fibonacciego
1 dla n=1
Dane wejściowe: nieujemna liczba całkowita n, fn =
Dane wyjściowe: n-ty wyraz ciągu.
fn-1+ fn-2 dla n > 1
Fib(5)
Fib(n) //alg. rekurencyjny
{
Fib(4)
Fib(3)
IF (n d" 1)
return(n);
ELSE
Fib(3)
return(Fib(n-1)+Fib(n-2)); Fib(2) Fib(2)
Fib(1)
}
Fib(2)
Fib(1)
Fib(0) Fib(1) Fib(0) Fib(1)
Złożoność obliczeniowa: T(n) = O(2n)
Fib(0) Fib(1)
ASD LJ S
Algorytmy rekurencyjne
Ciąg Fibonacciego.
n 0 1 2 3 4 5 6 7 8 9 10 11 &
Fib(n) 0 1 1 2 3 5 8 13 21 34 55 89
ASD LJ S
10
Algorytmy rekurencyjne
Złożoność obliczeniowa rekurencyjnego algorytmu Fib.
T(n) > 2 * T(n-2) > 2 * 2 T(n-4) > > 2 * 2 * 2 *...* 2 * T(0)
n/2 wyrazów
T(n) > 2n/2 T(0) = 2n/2
Dw.
1. Podstawa indukcji:
T(2) =3 > 2 = 22/2
T(3) =5 > 23/2 H" 2,83
2. Hipoteza indukcyjna:
dla m < n T(m) > 2m/2
3. Krok indukcyjny:
(n-2)/2 (n-2)/2 (n-2)/2 n/2
T(n) = T(n-1)+T(n-2)+1 > 2(n-1)/2 + 2 +1 > 2 + 2 = 2
Złożoność: T(n) = O(2n)
ASD LJ S
Algorytm iteracyjny
Problem: ciąg Fibonacciego
Dane wejściowe: nieujemna liczba całkowita n,
Dane wyjściowe: n-ty wyraz ciągu.
Fib_iter (n) // algorytm
0 dla n=0
iteracyjny
{ 1 dla n=1
fn =
F[0]=0;
fn-1+ fn-2 dla n > 1
IF (n > 0) F[1]=1;
FOR i=2,...,n {
F[i]=F[i-1]+F[i-2];
Złożoność obliczeniowa iteracyjnego
}
algorytmu:
return(F[n]);
}
T(n) = n+1=O(n)
11
Algorytmy rekurencyjne
Problem: Współczynnik dwumianowy Newtona (Binomial coefficient),
Dane wejściowe: nieujemna liczby całkowite n, k (k d" n),
Dane wyjściowe: wartość współczynnika dwumianowego.
n!
n dla 0 d" k d" n
=
k
k! (n  k)!
1
dla k = 0 lub k = n
n
=
n - 1
n - 1
dla 0 < k < n
k
+
k - 1
k
n - 1 wybranie pierwszego elementu, po czym wybranie (k-1) elementów z pozostałych
k - 1 (n-1) elementów.
n - 1 niewybranie pierwszego elementu, po czym wybranie k elementów z pozostałych
k (n-1) elementów.
ASD LJ S
Algorytmy rekurencyjne
Współczynnik dwumianowy Newtona.
1
k = 0 lub k = n
n
=
n - 1
n - 1
k
+ 0 < k < n
k - 1
k
(4,2)
(3,1)
(3,2)
(2,0) (2,1)
(2,1)
(2,2)
(2,0) (1,1)
(1,0) (1,1)
ASD LJ S
12
Algorytmy rekurencyjne
Współczynnik dwumianowy.
Bc_rec(n,k)
{
1. IF(k=0 *" n=k)
2. return(1);
ELSE
3. return(Bc_rec(n-1,k-1)+Bc_rec(n-1,k))
}
Czas działania T(n) algorytmu Bc_rec.
Jeżeli algorytm Bc_rec () jest wywoływany z pierwszym argumentem
równym n, drugi jest liczbą całkowitą od 0 do n, to czas działania T(n) algorytmu
jest nie większy niż c(2n  1),
gdzie: wartość c jest czasem działania instrukcji 1, 2.
ASD LJ S
Algorytmy rekurencyjne
Złożoność obliczeniowa rekurencyjnego algorytmu Bc_rec().
1. Przypadek podstawowy:
n=1, k=0 albo k=1=n.
T(1) d" c(2n  1) = c
2. Hipoteza indukcyjna:
T(n) d" c(2n-1)
3. Krok indukcyjny:
T(n+1) = c+ 2T(n) d" c+2c(2n  1)= c(1+2n+1  2)= c(2n+1 - 1)
ASD LJ S
13
Algorytmy rekurencyjne
Złożoność obliczeniowa rekurencyjnego algorytmu Bc_rec().
T(n) = O(2n)
n
Kształt funkcji: od k dla stałej wartości n.
k
k
ASD LJ S
Algorytm iteracyjny
Współczynnik dwumianowy  algorytm iteracyjny Bc_iter().
Dla k << n:
n!
n dla 0 d" k d" n
=
k
n (n-1) ..... (n-k+1) k! (n  k)!
n
=
k
k (k-1) ... 1
Złożoność obliczeniowa:
Bc_iter(n,k) //k << n
{
Dla k << n:
1. p=1;
2. FOR(i=n,n-1,....,n-k){
T(n,k) = k O (1)+k O (1) = O (k)
3. p=p*i;
}
Dla k H" n:
4. FOR(i=2,.... k){
5. p=p/i
T(n,k) = O (n-k)
}
}
ne"k �! T(n) = O (n)
ASD LJ S
14
Algorytmy rekurencyjne
Wieże Hanoi (Towers of Hanoi).
C B
A
To Using
From
Wieże Hanoi w konfiguracji wyjściowej
ASD LJ S
Algorytmy rekurencyjne
Wieże Hanoi. Sformułowanie problemu.
Dane są trzy słupki A, B, C oraz n krążków o różnych średnicach.
Zadanie polega na przeniesieniu wszystkich krążków ze słupka A na słupek C.
Zasady przeniesienia:
W każdym kroku przenosi się dokładnie jeden krążek,
Krążek o większej średnicy nie może być nałożony na krążek o
mniejszej średnicy.
Słupek B może być użyty jako słupek pomocniczy.
ASD LJ S
15
Algorytmy rekurencyjne
Wieże Hanoi. Przykład.
A B B
C A C
1
1
2
3
2
3
B
A C
A
C
B
2 3 2
1
1
3
C
A B
A B
C 2
1 3
3
1 2
C
A B
B
A
1
C
2
1
3
3
2
ASD LJ S
Algorytmy rekurencyjne
Wieże Hanoi - algorytm rekurencyjny.
from to using
1 n = 1
T(n) =
2T(n-1) + 1 n > 1
HANOI (n,A,C,B)
{
IF n=1 {
PRZENIES (A,C);
T(n) = 2T(n-1) +1 = 2 ( 2 T(n-2) +1) + 1 =
} ELSE {
n
= 2n-1 T(1) + (2n-2 + 2n-3 + ... + 1) = 2  1
HANOI (n-1,A,B,C);
PRZENIES (A,C);
T(n) = O(2n)
HANOI (n-1,B,C,A);
}
}
ASD LJ S
16