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