Matematyka Dyskretna

Andrzej Szepietowski

25 czerwca 2002 roku

Rozdział 1

Rekurencja

1.1

Wie˙ze Hanoi

Rekurencja jest to zdolno´s´c podprogramu (procedury lub funkcji) do wywoływania sa-
mego siebie. Zacznijmy od przykładu wie˙z Hanoi. Przypu´s´cmy, ˙ze mamy trzy wie˙ze lub
trzy paliki:

,

i



. Na pierwszym paliku,

, znajduj¸a si¸e trzy kr¸a˙zki ró˙znej wielko´sci,

nanizane w porz¸adku od najwi¸ekszego na dole do najmniejszego na górze. Paliki

i



s¸a na pocz¸atku puste. Nale˙zy przenie´s´c wszystkie kr¸a˙zki z palika

na

, posługuj¸ac si¸e

w razie potrzeby palikiem



, według nast¸epuj¸acych reguł:



mo˙zna przenosi´c po jednym kr¸a˙zku z jednego palika na inny,



nie mo˙zna umieszcza´c wi¸ekszego kr¸a˙zka na mniejszym.

Rozwi¸azaniem tej łamigłówki dla trzech kr¸a˙zków jest nast¸epuj¸acy ci¸ag siedmiu przeło-

˙ze´n:















 



 









gdzie zapis



oznacza przeniesienie szczytowego kr¸a˙zka z palika

na palik



.

Chodzi nam teraz o algorytm, który dla dowolnej liczby



kr¸a˙zków wypisze ci¸ag

operacji potrzebnych do przeło˙zenia



kr¸a˙zków z palika

na palik

.

Algorytm przekładania kr¸a˙zków



je˙zeli



, to przekładamy ten jeden kr¸a˙zek



,



je˙zeli



, to:



przekładamy



kr¸a˙zków z

na pomocniczy palik



(posługuj¸ac si¸e w

razie potrzeby palikiem

),



przekładamy



-ty kr¸a˙zek z

na

,



przekładamy



kr¸a˙zków z



na

(za pomoc¸a palika

).

3

4

Rozdział 1. Rekurencja

Nietrudno zauwa˙zy´c, ˙ze je˙zeli proces przekładania



kr¸a˙zków jest prawidłowy, to

cały proces te˙z jest prawidłowy, poniewa˙z obecno´s´c najwi¸ekszego kr¸a˙zka na dole palika
nie przeszkadza w przekładaniu





mniejszych kr¸a˙zków.

Powy˙zszy algorytm opiszmy teraz za pomoc¸a rekurencyjnej procedury przenie´s, któ-

ra odwołuje si¸e sama do siebie i wypisuje ci¸ag instrukcji przeniesienia



kr¸a˙zków z palika

na palik



.

procedura przenie´s(



kr¸a˙zków z

na



, za pomoc¸a

):



je˙zeli





, to wypisz



,



je˙zeli



, to



przenie´s(



kr¸a˙zków z

na

, za pomoc¸a



),



wypisz



,



przenie´s(



kr¸a˙zków z

na



, za pomoc¸a

).

Rysunek 1.1: Schemat działania procedury przenie´s dla wie˙z Hanoi z trzema kr¸a˙zkami





 







































 































Na rysunku 8.1 zilustrowano działanie procedury przenie´s dla





. Skrót





oznacza wywołanie procedury przenie´s(



kr¸a˙zków z

na



, za pomoc¸a

). Strzałki

w dół oznaczaj¸a wywołanie procedury, strzałki w gór¸e powroty po wykonaniu procedu-
ry, a strzałki poziome odpowiadaj¸a nast¸epstwu instrukcji w ramach jednego wykonania
procedury.

1.2. Algorytm Euklidesa, wersja rekurencyjna

5

1.2

Algorytm Euklidesa, wersja rekurencyjna

Innym przykładem algorytmu rekurencyjnego mo˙ze by ´c rekurencyjna wersja algorytmu
Euklidesa, który oblicza najwi¸ekszy wspólny dzielnik dwóch dodatnich liczb naturalnych

i

:

fun¯kcja NWD(a,b):



je˙zeli



, to









,



je˙zeli



, to









 







,



je˙zeli



, to









 







.

W j¸ezyku Pascal powy˙zsz¸a procedur¸e mo˙zemy zapisa´c w nast¸epuj¸acy sposób:

function NWD(a,b:integer):integer;

begin

if a=b then NWD:=a

else if



then NWD:=NWD(a-b,b)

else NWD:=NWD(a,b-a)

end;

Rysunek 1.2: Schemat działania rekurencyjnej wersji algorytmu Euklidesa

NWD(5,3):=1

NWD(2,3):=1

NWD(2,1):=1

NWD(1,1):=1

Na rysunku 8.2 przedstawiono proces obliczania funkcji NWD(7,3).

1.3

Funkcje rekurencyjne

Czasami wygodnie jest zdefiniowa´c funkcje za pomoc¸a wzoru rekurencyjnego. Na przy-
kład funkcj¸e silnia definiuje si¸e zwykle za pomoc¸a nast¸epuj¸acych dwóch równa ´n:























 















"!

6

Rozdział 1. Rekurencja

Podobnie mo˙zna definiowa´c inne funkcje ze zbioru liczb naturalnych w zbiór liczb natu-
ralnych. Definicja taka zawiera przepis, jak policzy´c warto´s´c funkcji dla warto´sci pocz¸atkowych,
oraz drugi przepis, jak wyliczy´c warto´s´c dla argumentu



za pomoc¸a warto´sci funkcji dla

mniejszych argumentów.

1.4

Funkcja (ci¸ag) Fibonacciego

Nast¸epnym przykładem rekurencyjnego definiowania funkcji jest funkcja Fibonacciego,
okre´slona równaniami:

























































!

Kolejne warto´sci funkcji Fibonacciego to:





























!!!

Udowodnimy teraz przez indukcj¸e, ˙ze









 











(1.1)

gdzie





















"



oraz























"



Równo´s´c (1.1) zachodzi dla







i







. Załó˙zmy teraz, ˙ze zachodzi dla wszystkich

argumentów mniejszych od



. Zauwa˙zmy, ˙ze



oraz

s¸a rozwi¸azaniami równania















, mamy wi¸ec











oraz



 

a tak˙ze





 







 

oraz















. Łatwo teraz mo˙zna pokaza´c, ˙ze

































 











.

Poniewa˙z









, mamy





















, wi¸ec warto´s´c







jest równa

!





po zaokr¸agleniu do najbli˙zszej liczby naturalnej i funkcja Fibonacciego ro´snie

wykładniczo.

1.5

Funkcja Ackermanna

Funkcja Ackermanna okre´slona jest, dla liczb naturalnych



#"



, nast¸epuj¸acymi rów-

naniami:





$"





&%



"











































#"

















$"













$"

"!

Funkcja Ackermanna jest przykładem funkcji maj¸acej do´s´c prost¸a definicj¸e, ale jest prak-
tycznie nieobliczalna z tego powodu, ˙ze jej warto´sci szybko rosn¸a. Na przykład:

















('

















)



+*

,



1.6. Algorytm sortowania przez scalanie

7















)

)













'







)

)

)



i ogólnie























)

 

!

1.6

Algorytm sortowania przez scalanie

Zajmijmy si¸e teraz pewnym prostym rekurencyjnym algorytem sortowania ci¸agu. Dla
prostoty załó˙zmy, ˙ze długo´s´c ci¸agu jest pot¸eg¸a dwójki.

Algorytm sortowania



je˙zeli ci¸ag ma długo´s´c jeden, to jest ju˙z posortowany,



je˙zeli ci¸ag jest dłu˙zszy, to:



dzielimy go na połowy,



sortujemy te połowy,



ł¸aczymy posortowane połowy w jeden posortowany ci¸ag.

Istota pomysłu polega na tym, ˙ze mo˙zna szybko poł¸aczy ´c dwa posortowane ci¸agi w jeden
posortowany ci¸ag. Algorytm ł¸aczenia wyja´snijmy na przykładzie. Przypu´s´cmy, ˙ze mamy
dwa ci¸agi:



























'









i ˙ze chcemy je poł¸aczy´c w posortowany ci¸ag



. Na pocz¸atku ci¸ag



jest pusty. Usta-

wiamy dwa wska´zniki po jednym na pocz¸atku ka˙zdego ci¸agu (wskazane elementy b¸ed¸a
oznaczone daszkiem):



























'

















!

Porównujemy wskazane elementy. Mniejszy z porównanych elementów przepisujemy na
ci¸ag



i przesuwamy wska´znik w tym ci¸agu, z którego był wzi¸ety element do ci¸agu



.

W wyniku otrzymamy:



























'



















!

Powtarzamy ten proces tak długo, a˙z w jednym z ci¸agów ostatni element zostanie zabrany
do ci¸agu



.































'

























































'

























































'































'

































'































'































'































'







!

8

Rozdział 1. Rekurencja

W takiej sytuacje pozostałe elementy tego drugiego ci¸agu przenosimy do ci¸agu



:

























'



























'











!

Liczba porówna ´n potrzebna do scalenia ci¸agów nie jest wi¸eksza od sumy długo´sci tych
ci¸agów.

Algorytm merge-sort (inaczej — sortowanie przez scalanie), który sortuje ci¸ag

,

mo˙zna rekurencyjnie opisa´c tak (rysunek 8.3):

merge-sort(S):



je˙zeli

ma tylko jeden element, to koniec,



je˙zeli

ma wi¸ecej elementów, to:



dzielimy ci¸ag

na połowy



i



,



merge-sort(



),



merge-sort(



),



ł¸aczymy



i



.

Rysunek 1.3: Schemat działania algorytmu merge-sort dla ci¸agu 3, 7, 5, 2, 6, 1, 8, 4

3752|6186

37|52

61|84

3|7

5|2

6|1

8|4

3

7

5

2

6

1

8

4

37

25

16

48

2357

1468

12345678

Algorytm merge-sort jest przykładem algorytmu typu „dziel i zwyci¸e˙zaj”, którego

ogólny schemat wygl¸ada tak:



je˙zeli problem jest małego rozmiaru, to rozwi¸azujemy go bezpo´srednio,

1.7. Rozwi¸azywanie równa ´n i nierówno´sci rekurencyjnych

9



je˙zeli problem jest du˙zy, to:



dzielimy problem na podproblemy,



rozwi¸azujemy podproblemy,



ł¸aczymy rozwi¸azania podproblemów w rozwi¸azanie całego problemu.

1.7

Rozwi¸azywanie równa ´

n i nierówno´

sci rekurencyjnych

Oszacujmy teraz czas działania algorytmu sortowania przez scalanie. Niech







oznacza

liczb¸e operacji porównania potrzebn¸a do posortowania ci¸agu długo´sci



. Mamy nast¸epuj¸ace

oszacowania:













(1.2)



















!

(1.3)

Druga zale˙zno´s´c wynika st¸ad, ˙ze aby posortowa´c ci¸ag długo´sci



, sortujemy dwa ci¸agi

długo´sci





, a nast¸epnie potrzebujemy



porówna ´n, aby scali´c te dwie połówki. Dla pro-

stoty rozwa˙za ´n zakładamy tutaj, ˙ze



jest pot¸eg¸a dwójki,









dka jakiego´s naturalnego



.

Istnieje wiele sposobów wyliczania lub szacowania funkcji okre´slonej rekurencyjnie.

Przedstawimy teraz dwa najprostsze z nich: metod¸e podstawiania i metod¸e iteracji.

1.8

Metoda podstawiania

W metodzie podstawiania odgadujemy rozwi¸azanie albo jego oszacowanie, a nst¸epnie
pokazujemy, ˙ze jest ono poprawne. Poka˙zemy działanie tej metody szacuj¸ac zło˙zono´s´c
czasow¸a merge-sortu okre´slon¸a rekurencj¸a (1.2)-(1.3). Zgadujemy, ˙ze










 



dla jakiej´s stałej







i udowodnimy przez indukcj¸e, ˙ze powy˙zsza nierówno´s´c zacho-

dzi dla ka˙zdego pot¸egi dwójki





. Zachodzi ona dla







. Zakładamy teraz, ˙ze










 













i podstawiamy do nierówno´sci (1.3)























































Ostatnia nierówno´s´c jest spełniona, je˙zeli





.

Metoda podstawiania została zastosowana w podrozdziale o funkcji Fibonacciego do

pokazania, ˙ze









 











(1.4)

10

Rozdział 1. Rekurencja

ale tam odgadni¸eto dokładne rozwi¸azanie. Teraz poka˙zemy jak doj´s´c do rozwi¸aznia zaczynaj¸ac
od ogólniejszej postaci. Zacznijmy od równania

























!

(1.5)

Sprawd´zmy, jakie funkcje postaci









,

spełniaj¸a to równanie. Po podstawieniu do

równania (1.5) mamy



















Po podzieleniu stromnami przez





, otrzymamy









"!

Jest to równanie kwadratowe z dwoma rozwi¸azaniami

















oraz















, czyli dwie funkcje











 

oraz













spełniaj¸a równanie (1.5).

Zauwa˙zmy, ˙ze tak˙ze ka˙zda funkcja postaci

































gdzie





i





to stałe, spełnia równanie (1.5). Sprawd´zmy teraz, dla jakich stałych





i





funkcja

spełnia zale˙zno´sci









i











. Otrzymujemu układ równo´sci



























Powy˙zszy układ jest spełniony dla













































Tak wi¸ec otrzymujemy wzór na funkcj¸e Fibonacciego









 











(1.6)

1.9

Metoda iteracyjna

Moteda iteracyjna polega na rozwijaniu rekursji. Jako pierwszy przykład rozwa˙zmy za-
le˙zno´s´c.

























'





Dla uproszczenia zakładamy, ˙ze



jest pot¸eg¸a





'



, dla jakiego´s



naturalnego. Funkcj¸e

rozwijamy w nast¸epuj¸acy sposób:

















'



1.10. Metoda rekurencji uniwersalnej

11











'







,















'







,









'















'





,











'



!!!









'





,

!!!







'



Iteracj¸e powtarzamy, a˙z ostatni składnik b¸edzie zawierał







, czyli gdy







*



.

Otrzymamy wtedy















'





,

!!!























'






 





'





















Skorzystali´smy tu z równo´sci





 









  

oraz z faktu, ˙ze



*







i





 











.

Jako drugi przykład rozwa˙zmy rekursj¸e































Jak b¸edziemy j¸a rozwija´c, to otrzymamy







































'























'

































!!!









!!!











Dla





 





. Otrzymamy wtedy











 

)















)

























(1.7)

1.10

Metoda rekurencji uniwersalnej

Przypu´s´cmy, ˙ze mamy równanie rekurencyjne






















(1.8)

12

Rozdział 1. Rekurencja

gdzie



i





. Równanie takie otrzymamy szacuj¸ac czas działania algorytmu

rekurencyjnego, który metod¸a "dziel i rz¸ad´z" dzieli problem na

podproblemów rozmiaru



. Funkcja









opisuje czas potrzebny na podzielenie problemu na podproblemy i na

poł¸aczenie rozwi¸aza ´n podproblemów w rozwi¸azanie całego problemu.

Na koniec podamy bez dowodu twierdzenie mówi¸ace jak mo˙zna szacowa ´c funkcj¸e







okre´slon¸a równaniem (1.8).

Twierdzenie 1.1 (o rekurencji uniwersalnej) Niech







b¸edzie okre´slone dla nieujem-

nych liczb całkowitych równaniem rekurencyjnym













"












gdzie



,



i



"

oznacza



"


lub







. Wtedy



Je˙zeli



















 







dla pewnej stałej







, to







 













.



Je˙zeli

















 







, to















 











.



Je˙zeli

















 







dla pewnej stałej







oraz



















dla

pewnej stałej







, to





















.

1.11

Zadania

1. Napisz program, który rekurencyjnie oblicza: a) funkcj¸e silnia, b) funkcj¸e Fibonac-

ciego, c) funkcj¸e wykładnicz¸a



.

2. Napisz program, który oblicza symbol Newtona:

a) według wzoru rekurencyjnego





























b) według wzoru

































 

!

Porównaj te programy.

3. Napisz program, który rekurencyjnie oblicza funkcj¸e:

















































!

4. Oblicz











'



według rekurencyjnego algorytmu Euklidesa.

5. Według algorytmu ł¸aczenia poł¸acz ci¸agi































i













'















.

1.11. Zadania

13

6. Stosuj¸ac algorytm merge-sort posortuj ci¸ag słów: słowik, wróbel, kos, jaskółka,

kogut, dzi¸ecioł, gil, kukułka, szczygieł, sowa, kruk, czubatka.

[Fragment wiersza Ptasie radio Juliana Tuwima]

7. Dana jest funkcja











:





































"!

Oblicz











. Co oblicza funkcja



?

8. Dana jest funkcja



 







:











































!

Oblicz





'







. Co oblicza funkcja



?

9. Wypisz ci¸ag przeło˙ze ´n potrzebnych do przeniesienia czterech kr¸a˙zków na wie˙zach

Hanoi.

10. Udowodnij, ˙ze algorytm opisany w podrozdziale 8.1 wymaga









przeło˙ze´n do

przeniesienia



kr¸a˙zków.