Matematyka Dyskretna
Andrzej Szepietowski
25 czerwca 2002 roku
Rozdział 1
Rekurencja
1.1 Wieże Hanoi
Rekurencja jest to zdolność podprogramu (procedury lub funkcji) do wywoływania sa-
mego siebie. Zacznijmy od przykładu wież Hanoi. Przypuśćmy, że mamy trzy wieże lub

trzy paliki: , i . Na pierwszym paliku, , znajduja sie trzy krażki różnej wielkości,
¸ ¸ ¸
nanizane w porzadku od najwiekszego na dole do najmniejszego na górze. Paliki i
¸ ¸

sa na poczatku puste. Należy przenieść wszystkie krażki z palika na , posługujac sie
¸ ¸ ¸ ¸ ¸
w razie potrzeby palikiem , według nastepujacych reguł:
¸ ¸

można przenosić po jednym krażku z jednego palika na inny,
¸

nie można umieszczać wiekszego krażka na mniejszym.
¸ ¸
Rozwiazaniem tej łamigłówki dla trzech krażków jest nastepujacy ciag siedmiu przeło-
¸ ¸ ¸ ¸ ¸
żeń:



gdzie zapis oznacza przeniesienie szczytowego krażka z palika na palik .
¸
Chodzi nam teraz o algorytm, który dla dowolnej liczby krażków wypisze ciag
¸ ¸

operacji potrzebnych do przełożenia krażków z palika na palik .
¸
Algorytm przekładania krażków
¸


jeżeli , to przekładamy ten jeden krażek ,
¸

jeżeli , to:


przekładamy krażków z na pomocniczy palik (posługujac sie w
¸ ¸ ¸
razie potrzeby palikiem ),


przekładamy -ty krażek z na ,
¸


przekładamy krażków z na (za pomoca palika ).
¸ ¸
3
4 Rozdział 1. Rekurencja
Nietrudno zauważyć, że jeżeli proces przekładania krażków jest prawidłowy, to
¸
cały proces też jest prawidłowy, ponieważ obecność najwiekszego krażka na dole palika
¸ ¸
nie przeszkadza w przekładaniu mniejszych krażków.
¸
Powyższy algorytm opiszmy teraz za pomoca rekurencyjnej procedury przenieś, któ-
¸
ra odwoÅ‚uje ¸ sama do siebie i wypisuje ciag instrukcji przeniesienia krażków z palika
sie ¸ ¸
na palik .

procedura przenieś( krażków z na , za pomoca ):
¸ ¸


jeżeli , to wypisz ,

jeżeli , to


przenieś( krażków z na , za pomoca ),
¸ ¸


wypisz ,


przenieś( krażków z na , za pomoca ).
¸ ¸
Rysunek 1.1: Schemat działania procedury przenieś dla wież Hanoi z trzema krażkami
¸













Na rysunku 8.1 zilustrowano działanie procedury przenieś dla . Skrót




oznacza wywołanie procedury przenieś( krażków z na , za pomoca ). Strzałki
¸ ¸
w dół oznaczaja wywołanie procedury, strzałki w góre powroty po wykonaniu procedu-
¸ ¸
ry, a strzałki poziome odpowiadaja nastepstwu 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że być rekurencyjna wersja algorytmu
Euklidesa, który oblicza najwiekszy wspólny dzielnik dwóch dodatnich liczb naturalnych
¸


i :
Å»
funkcja NWD(a,b):



jeżeli , to ,


jeżeli , to ,



jeżeli , to .

W jezyku Pascal powyższa procedure możemy zapisać w nastepujacy 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ć funkcje za pomoca wzoru rekurencyjnego. Na przy-
¸
kład funkcje silnia definiuje sie zwykle za pomoca nastepujacych dwóch równań:
¸ ¸ ¸ ¸ ¸







6 Rozdział 1. Rekurencja
Podobnie można definiować inne funkcje ze zbioru liczb naturalnych w zbiór liczb natu-
ralnych. Definicja taka zawiera przepis, jak policzyć wartość funkcji dla wartości poczatkowych,
¸

oraz drugi przepis, jak wyliczyć wartość dla argumentu za pomoca wartości funkcji dla
¸
mniejszych argumentów.
1.4 Funkcja (ciag) Fibonacciego
¸
Nastepnym przykładem rekurencyjnego definiowania funkcji jest funkcja Fibonacciego,
¸
określona równaniami:








Kolejne wartości funkcji Fibonacciego to:



Udowodnimy teraz przez indukcje, że
¸




(1.1)




gdzie oraz


Równość (1.1) zachodzi dla i . teraz, że zachodzi dla wszystkich
Załóżmy
argumentów mniejszych . Zauważmy, że oraz sa rozwiazaniami równania
od ¸ ¸



, mamy wiec oraz a także oraz
¸





. A
atwo teraz można pokazać, że




.




Ponieważ , mamy , wiec wartość jest równa
¸


po zaokragleniu do najbliższej liczby naturalnej i funkcja Fibonacciego rośnie
¸
wykładniczo.
1.5 Funkcja Ackermanna

Funkcja Ackermanna określona jest, dla liczb naturalnych , nastepujacymi rów-
¸ ¸
naniami:













Funkcja Ackermanna jest przykładem funkcji majacej dość prosta definicje, ale jest prak-
¸ ¸ ¸
tycznie nieobliczalna z tego powodu, że jej wartości szybko rosna. Na przykład:
¸




1.6. Algorytm sortowania przez scalanie 7




i ogólnie








1.6 Algorytm sortowania przez scalanie
Zajmijmy sie teraz pewnym prostym rekurencyjnym algorytem sortowania ciagu. Dla
¸ ¸
prostoty załóżmy, że długość ciagu jest potega dwójki.
¸ ¸ ¸
Algorytm sortowania

jeżeli ciag ma długość jeden, to jest już posortowany,
¸

jeżeli ciag jest dłuższy, to:
¸

dzielimy go na połowy,

sortujemy te połowy,

łaczymy posortowane połowy w jeden posortowany ciag.
¸ ¸
Istota pomysłu polega na tym, że można szybko połaczyć dwa posortowane ciagi w jeden
¸ ¸
posortowany ciag. Algorytm łaczenia wyjaśnijmy na przykładzie. Przypuśćmy, że mamy
¸ ¸
dwa ciagi:
¸



i że chcemy je połaczyć w posortowany ciag . Na poczatku ciag jest pusty. Usta-
¸ ¸ ¸ ¸
wiamy dwa wskaz
niki po jednym na poczatku każdego ciagu (wskazane elementy beda
¸ ¸ ¸ ¸
oznaczone daszkiem):



Porównujemy wskazane elementy. Mniejszy z porównanych elementów przepisujemy na
ciag i przesuwamy wskaz
nik w tym ciagu, z którego był wziety element do ciagu .
¸ ¸ ¸ ¸
W wyniku otrzymamy:



Powtarzamy ten proces tak długo, aż w jednym z ciagów ostatni element zostanie zabrany
¸
do ciagu .
¸















8 Rozdział 1. Rekurencja
W takiej sytuacje pozostałe elementy tego drugiego ciagu przenosimy do ciagu :
¸ ¸



Liczba porównań potrzebna do scalenia ciagów nie jest wieksza od sumy długości tych
¸ ¸
ciagów.
¸
Algorytm merge-sort (inaczej  sortowanie przez scalanie), który sortuje ciag ,
¸
można rekurencyjnie opisać tak (rysunek 8.3):
merge-sort(S):

jeżeli ma tylko jeden element, to koniec,

jeżeli ma wiecej elementów, to:
¸

dzielimy ciag na połowy i ,
¸


merge-sort( ),

merge-sort( ),


Å‚aczymy i .
¸

Rysunek 1.3: Schemat działania algorytmu merge-sort dla ciagu 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 zwycieżaj , którego
¸
ogólny schemat wyglada tak:
¸

jeżeli problem jest małego rozmiaru, to rozwiazujemy go bezpośrednio,
¸
1.7. Rozwiazywanie równań i nierówności rekurencyjnych 9
¸

jeżeli problem jest duży, to:

dzielimy problem na podproblemy,

rozwiazujemy podproblemy,
¸

łaczymy rozwiazania podproblemów w rozwiazanie całego problemu.
¸ ¸ ¸
1.7 Rozwiazywanie równań i nierówności rekurencyjnych
¸

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

liczbe operacji porównania potrzebna do posortowania ciagu długości . Mamy nastepujace
¸ ¸ ¸ ¸ ¸
oszacowania:

(1.2)



(1.3)

Druga zależność wynika stad, że aby posortować ciag długo ści , sortujemy dwa ciagi
¸ ¸ ¸


długości , a nastepnie potrzebujemy porównań, aby scalić te dwie połówki. Dla pro-
¸


stoty rozważań zakładamy tutaj, że jest potega dwójki, dka jakiegoś naturalnego
¸ ¸

.
Istnieje wiele sposobów wyliczania lub szacowania funkcji określonej rekurencyjnie.
Przedstawimy teraz dwa najprostsze z nich: metode podstawiania i metode iteracji.
¸ ¸
1.8 Metoda podstawiania
W metodzie podstawiania odgadujemy rozwiazanie albo jego oszacowanie, a nstepnie
¸ ¸
pokazujemy, że jest ono poprawne. Pokażemy działanie tej metody szacujac złożoność
¸
czasow¸ merge-sortu okreÅ›lona rekurencja (1.2)-(1.3). Zgadujemy, że
a ¸ ¸




dla jakiejś stałej i udowodnimy przez indukcje, że powyższa nierówność zacho-
¸

dzi dla ¸ dwójki . Zachodzi ona dla . ZakÅ‚adamy teraz, że
każdego potegi




i podstawiamy do nierówności (1.3)











Ostatnia nierówność jest spełniona, jeżeli .
Metoda podstawiania została zastosowana w podrozdziale o funkcji Fibonacciego do
pokazania, że




(1.4)

10 Rozdział 1. Rekurencja
ale tam odgadnieto dokładne rozwiazanie. Teraz pokażemy jak dojść do rozwiaznia zaczynajac
¸ ¸ ¸ ¸
od ogólniejszej postaci. Zacznijmy od równania



(1.5)


Sprawdz
my, jakie funkcje postaci spełniaja to równanie. Po podstawieniu do
¸
równania (1.5) mamy





Po podzieleniu stromnami przez , otrzymamy






Jest równanie kwadratowe z dwoma ¸
to rozwiazaniami oraz




, czyli dwie funkcje oraz spełniaja równanie (1.5).
¸

Zauważmy, że także każda funkcja postaci






gdzie i to stałe, spełnia równanie (1.5). Sprawdz
my teraz, dla jakich stałych i

funkcja spełnia zależności i . Otrzymujemu układ równości








Powyższy układ jest spełniony dla









Tak wiec otrzymujemy wzór na funkcje Fibonacciego
¸ ¸




(1.6)

1.9 Metoda iteracyjna
Moteda iteracyjna polega na rozwijaniu rekursji. Jako pierwszy przykład rozważmy za-
leżność.









Dla uproszczenia zakładamy, że jest potega , dla jakiegoś naturalnego. Funkcje
¸ ¸ ¸
¸ ¸
rozwijamy w nastepujacy sposób:




1.10. Metoda rekurencji uniwersalnej 11























Iteracje powtarzamy, aż ostatni składnik bedzie zawierał , czyli gdy .
¸ ¸
Otrzymamy wtedy
























Skorzystaliśmy tu z równości oraz z faktu, że i


.
Jako drugi przykład rozważmy rekursje
¸






Jak bedziemy ja rozwijać, to otrzymamy
¸ ¸





















Dla . Otrzymamy wtedy

















(1.7)
1.10 Metoda rekurencji uniwersalnej
Przypuśćmy, że mamy równanie rekurencyjne



(1.8)
12 Rozdział 1. Rekurencja


gdzie i . Równanie takie otrzymamy szacujac czas działania algorytmu
¸

rekurencyjnego, który metoda "dziel i rzadz
" dzieli problem na podproblemów rozmiaru
¸ ¸


. Funkcja opisuje czas potrzebny na podzielenie problemu na podproblemy i na
połaczenie rozwiazań podproblemów w rozwiazanie całego problemu.
¸ ¸ ¸
Na koniec podamy bez dowodu twierdzenie mówiace jak można szacować funkcje
¸ ¸

określona równaniem (1.8).
¸

¸
Twierdzenie 1.1 (o rekurencji uniwersalnej) Niech bedzie określone dla nieujem-
nych liczb całkowitych równaniem rekurencyjnym







gdzie , i oznacza lub . Wtedy



Jeżeli dla pewnej stałej , to .



Jeżeli , to .



Jeżeli dla pewnej stałej oraz dla



pewnej stałej , to .

1.11 Zadania
1. Napisz program, który rekurencyjnie oblicza: a) funkcje silnia, b) funkcje Fibonac-
¸ ¸


ciego, c) funkcje wykładnicza .
¸ ¸
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 funkcje:
¸







4. Oblicz według rekurencyjnego algorytmu Euklidesa.




5. Według algorytmu łaczenia połacz ciagi
¸ ¸ ¸

i .

1.11. Zadania 13
6. Stosujac algorytm merge-sort posortuj ciag słów: słowik, wróbel, kos, jaskółka,
¸ ¸
kogut, dziecioł, 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 ciag przełożeń potrzebnych do przeniesienia czterech krażków na wieżach
¸ ¸
Hanoi.

10. Udowodnij, że algorytm opisany w podrozdziale 8.1 wymaga przełożeń do

przeniesienia krażków.
¸