1
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 pozwala tworzyć:
Przejrzyste struktury algorytmów,
Wydajne struktury danych.
Rekurencja (w ogólnym przypadku) - definiuje nowe obiekty za pomocą obiektów
wcześniej zbudowanych w szczególności z obiektów podstawowych.
ASD
LJ
S
2
Przykład rekurencji
Struktura katalogów postaci drzewa
(directory tree)
Gałęzie drzewa są drzewami
ASD
LJ
S
Rekurencja i myślenie rekurencyjne
(x’,y’)
(x,y)
ASD
LJ
S
Elementy myślenia rekurencyjnego:
1.
Przypadek podstawowy
2
Reguła indukcyjna
3
Definicje rekurencyjne
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.
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.
ASD
LJ
S
Definicje rekurencyjne
a
0
= 1
k=0
a
k
= a
k-1
+ const
k>0
c
A
=
f
n
=
0
n = 0
1
n = 1
f
n-1
+ f
n-2
n > 1
1 n = 0
n * (n-1)!
n > 0
n! =
f(n) =
1 n = 0
f(n-1) + n ≥ 1
1
f(n-1)
ASD
LJ
S
4
Implementacja rekurencji
Kod
Dane statyczne
Stos programu
Sterta
R
E
K
O
R
D
A
K
T
Y
W
A
C
J
I
Pamięć programu
Przejście od rekurencyjnej definicji funkcji do implementacji wymaga tłumaczenia
tej definicji na składnię języka programowania.
Wykorzystanie stosu do impelementacji rekurencji (Dijkstra E).
ASD
LJ
S
pow
rót
Program
Instrukcje
Wywołanie A
++++..
Instrukcje
Instrukcje
Procedura A
Parametry
Zmienne lokalne
Instrukcje
Zwracana wartość
wywo
łanie
Implementacja rekurencji
Rekord aktywacji (
activation record
):
Parametry wywołania
Zmienne lokalne
Wartość zwracana
Dynamiczne dowiązanie - wskaźnik do
rekordu wywołania procesu wywołującego
Adres powrotu do procesu wywołania.
Kod
Dane statyczne
Stos programu
Sterta
R
E
K
O
R
D
A
K
T
Y
W
A
C
J
I
Pamięć programu
Wykorzystanie stosu do impelementacji rekurencji (
Dijkstra E.
).
ASD
LJ
S
5
Pamięć programu
Obszar danych statycznych - dane dostępne
przez cały czas wykonywania programu np.
zmienne globalne i statyczne zmienne
lokalne.
Sterta - pamięć alokowana dynamicznie.
Stos programu - informacje o wywołaniach
funkcji.
ASD
LJ
S
Kod
Dane statyczne
Stos programu
Sterta
Implementacja rekurencji
Zasada wielostopniowego, rekurencyjnego wywołania procedury (funkcji).
wywo
łanie
po
wró
t
wy
wo
ła
nie
powrót
wy
wo
ła
nie
pow
rót
Program główny
Procedura A
Procedura B
ASD
LJ
S
6
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
7
Schemat wywołań rekurencyjnych
PROBLEM P (rozm: n)
PROBLEM P (rozm: (n-1))
.
.
.
PROBLEM P (rozm: jednostkowy)
Spełniony warunek początkowy
K
ie
ru
n
e
k
b
u
d
o
w
y
d
rz
e
w
a
r
e
k
u
re
n
c
ji
K
ie
ru
n
e
k
p
o
w
ro
tu
Drzewo rekurencji dla problemu P o rozmiarze n.
ASD
LJ
S
Drzewo rekurencji
silnia ( n )
silnia ( n-1 )
. . . . .
silnia ( 0 )
spełniony warunek początkowy
Obliczanie n! dla danego n.
Drzewo rekurencji dla 3!
3!
2!
0!
spełniony war. początkowy
1!
1
2 *1!
1 *0!
3 *2!
1
dla n = 0 // warunek początkowy
n! =
n! = n(n-1)!
dla n ≥ 1 // krok indukcyjny
ASD
LJ
S
8
Algorytmy rekurencyjne
Silnia (n) //alg. rekurencyjny
{
IF (n==0)
return(1);
ELSE
return(n*silnia(n-1));
}
0
n =0
T(n) =
T(n-1)+1 n ≥1
T(0) = 0
T(1) = 1
T(2) = 2
...............
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)
Problem: rekurencyjne obliczanie wartości n! .
Dane wejściowe: dodatnia całkowita liczba n.
Dane wyjściowe: wartość n! .
ASD
LJ
S
Algorytm iteracyjny
Silnia (n)// alg. iteracyjny
{
i=2;
f=1;
WHILE ( i ≤ n ) {
f = f * i;
i = i + 1;
}
return (f)
}
Złożoność obliczeniowa algorytmu:
T(n) = n -1
T(n) = O(n)
Iteracyjna implementacja n!
ASD
LJ
S
9
Algorytmy rekurencyjne
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)
}
}
Problem: rekurencyjne wyszukiwanie binarne.
Dane wejściowe: dodatnia całkowita liczba n, klucz x, posortowana tablica A.
Dane wyjściowe: lokalizacja klucza.
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
rekurencyjnym
Porównanie na
najwyższym poziomie
1
n=1
T(n) =
T(n/2) + 1
n>1, n=2
k
T(n) = T(n/2) + 1= (T(n/4) + 1 ) + 1 = .... = ((...(T(n/2
k
)))) + 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
10
Algorytmy rekurencyjne
Fib(n) //alg. rekurencyjny
{
IF (n ≤ 1)
return(n);
ELSE
return(Fib(n-1)+Fib(n-2));
}
f
n-1
+ f
n-2
dla n > 1
1
dla n=1
0
dla n=0
f
n
=
Problem: ciąg Fibonacciego
Dane wejściowe: nieujemna liczba całkowita n,
Dane wyjściowe: n-ty wyraz ciągu.
Fib(5)
Fib(4)
Fib(3)
Fib(1)
Fib(2)
Fib(3)
Fib(2)
Fib(0)
Fib(1)
Fib(0)
Fib(1)
Fib(1)
Fib(2)
Fib(0)
Fib(1)
Złożoność obliczeniowa: T(n) = O(2
n
)
ASD
LJ
S
Algorytmy rekurencyjne
Ciąg Fibonacciego.
n
Fib(n)
0
0
1
1
2
1
3
2
4
3
5
5
6
8
7
13
8
21
9
34
10
55
11
89
…
N
ASD
LJ
S
11
Algorytmy rekurencyjne
Złożoność obliczeniowa rekurencyjnego algorytmu Fib.
T(n) > 2 * T(n-2) > 2 * 2 T(n-4) > N> 2 * 2 * 2 *...* 2 * T(0)
n/2 wyrazów
T(n) > 2
n/2
T(0) = 2
n/2
Dw.
1. Podstawa indukcji:
T(2) =3 > 2 = 2
2/2
T(3) =5 > 2
3/2
≈ 2,83
2.
Hipoteza indukcyjna:
dla m < n T(m) > 2
m/2
3.
Krok indukcyjny:
T(n) = T(n-1)+T(n-2)+1 > 2
(n-1)/2
+ 2
(n-2)/2
+1 > 2
(n-2)/2
+ 2
(n-2)/2
= 2
n/2
Złożoność: T(n) = O(2
n
)
ASD
LJ
S
Algorytm iteracyjny
f
n-1
+ f
n-2
dla n > 1
1
dla n=1
0
dla n=0
f
n
=
Fib_iter (n) // algorytm
iteracyjny
{
F[0]=0;
IF (n > 0) F[1]=1;
FOR i=2,...,n {
F[i]=F[i-1]+F[i-2];
}
return(F[n]);
}
Problem: ciąg Fibonacciego
Dane wejściowe: nieujemna liczba całkowita n,
Dane wyjściowe: n-ty wyraz ciągu.
Złożoność obliczeniowa iteracyjnego
algorytmu:
T(n) = n+1=O(n)
12
Algorytmy rekurencyjne
n
k
n - 1
k - 1
=
+
n - 1
k
dla 0 < k < n
1
dla k = 0 lub k = n
Problem: Współczynnik dwumianowy Newtona (Binomial coefficient),
Dane wejściowe: nieujemna liczby całkowite n, k (k ≤ n),
Dane wyjściowe: wartość współczynnika dwumianowego.
n
k
n!
=
k! (n – k)!
dla 0 ≤ k ≤ n
n - 1
k - 1
wybranie pierwszego elementu, po czym wybranie (k-1) elementów z pozostałych
(n-1) elementów.
niewybranie pierwszego elementu, po czym wybranie k elementów z pozostałych
(n-1) elementów.
n - 1
k
ASD
LJ
S
Algorytmy rekurencyjne
n
k
n - 1
k - 1
=
+
n - 1
k
0 < k < n
1
k = 0 lub k = n
Współczynnik dwumianowy Newtona.
(4,2)
(3,2)
(3,1)
(2,0)
(2,1)
(2,2)
(2,1)
(2,0)
(1,1)
(1,0)
(1,1)
ASD
LJ
S
13
Algorytmy rekurencyjne
Złożoność obliczeniowa rekurencyjnego algorytmu Bc_rec().
1.
Przypadek podstawowy:
n=1, k=0 albo k=1=n.
T(1) ≤ c(2
n
– 1) = c
2. Hipoteza indukcyjna:
T(n) ≤ c(2
n
-1
)
3.
Krok indukcyjny:
T(n+1) = c+ 2T(n) ≤ c+2c(2
n
– 1)= c(1+2
n+1
– 2)= c(2
n+1
- 1)
ASD
LJ
S
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(2
n
– 1),
gdzie: wartość c jest czasem działania instrukcji 1, 2.
ASD
LJ
S
14
Algorytmy rekurencyjne
Złożoność obliczeniowa rekurencyjnego algorytmu Bc_rec().
T(n) = O(2
n
)
Kształt funkcji:
n
k
od k dla stałej wartości n.
k
ASD
LJ
S
Algorytm iteracyjny
Współczynnik dwumianowy – algorytm iteracyjny Bc_iter().
n
k
n (n-1) ..... (n-k+1)
=
k (k-1) ... 1
Bc_iter(n,k) //k << n
{
1.
p=1;
2.
FOR(i=n,n-1,....,n-k){
3.
p=p*i;
}
4.
FOR(i=2,.... k){
5.
p=p/i
}
}
Dla k << n:
Złożoność obliczeniowa:
Dla k << n:
T(n,k) = k O (1)+k O (1) = O (k)
Dla k ≈ n:
T(n,k) = O (n-k)
n≥k ⇒ T(n) = O (n)
ASD
LJ
S
n
k
n!
=
k! (n – k)!
dla 0 ≤ k ≤ n
15
Algorytmy rekurencyjne
Wieże Hanoi (
Towers of Hanoi
).
Wieże Hanoi w konfiguracji wyjściowej
A
From
B
Using
C
To
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
16
Algorytmy rekurencyjne
Wieże Hanoi. Przykład.
C
3
2
1
A
B
B
1
C
3
2
A
3
A
B
2
1
C
3
A
B
2
1
C
A
1
C
3
2
B
A
B
2
1
C
3
B
C
2
3
A
1
B
3
2
1
C
A
ASD
LJ
S
Algorytmy rekurencyjne
Wieże Hanoi - algorytm rekurencyjny.
HANOI (n,A,C,B)
{
IF n=1 {
PRZENIES (A,C);
} ELSE {
HANOI (n-1,A,B,C);
PRZENIES (A,C);
HANOI (n-1,B,C,A);
}
}
from
to
using
1
n = 1
T(n) =
2T(n-1) + 1
n > 1
T(n) = 2T(n-1) +1 = 2 ( 2 T(n-2) +1) + 1 =
= 2
n-1
T(1) + (2
n-2
+ 2
n-3
+ ... + 1) = 2
n
– 1
T(n) = O(2
n
)
ASD
LJ
S