2008-10-14

1

Rekurencja

Wykład 02.

Algorytmy i struktury danych

Rok akademicki: 2008/09

2

Rekurencja

•

Rekurencyjny sposób zapisu kodu programu - z poziomu
podprogramu wywoływany jest ten sam podprogram.

2008-10-14

2

3

Przykład (1)

public class Rekurencja01 {

static void f() {

System.out.println("Poczatek");

f();

System.out.println("Koniec");

}

public static void main(String [] args) {

f();

}

}

4

Przykład (2)

Początek

f(x)

Koniec

Początek

f(x)

Koniec

Początek

f(x)

Koniec

Początek

f(x)

Koniec

main()
{

f()

}

i.t.d.

2008-10-14

3

5

Przykład (3)

Efekt uruchomienia programu:

Poczatek

Poczatek

Poczatek

....

Poczatek

Exception in thread "main"

java.lang.StackOverflowError

6

Warunek stopu

•

Wywołania rekurencyjne muszą się zakończyć (w
podprogramie musi zostać zdefiniowany warunek
zatrzymania się algorytmu /warunek stopu/).

2008-10-14

4

7

Przykład (1)

public class Rekurencja02 {

static int licznik = 0;
static void f() {

licznik++;
System.out.println("Poczatek");
if (licznik <=5) f();
System.out.println("Koniec");

}
public static void main(String [] args)

{

f();

}

}

8

Przykład (2)

licznik = 1

Początek

f(x)

Koniec

licznik = 2

Początek

f(x)

Koniec

licznik = 3

Początek

f(x)

Koniec

licznik = 4

Początek

f(x)

Koniec

licznik = 5

Początek

f(x)

Koniec

main()
{

f()

}

licznik = 6

Początek

Koniec

2008-10-14

5

9

Przykład (3)

Efekt uruchomienia programu:
Poczatek
Poczatek
Poczatek
Poczatek
Poczatek
Poczatek
Koniec
Koniec
Koniec
Koniec
Koniec
Koniec

10

Rekurencyjne obliczanie silni (1)

public class Rekurencja03 {

static int silnia(int n) {

int pomoc;
System.out.println("Wywolanie: silnia(" + n + ")");
if ((n == 0) || (n == 1)) pomoc = 1;
else pomoc = n * silnia(n-1);
System.out.println("Zwrocenie wyniku: " + n + "! = " + pomoc);
return pomoc;

}

public static void main(String [] args) {

System.out.println("4! = " + silnia(4));

}

}

2008-10-14

6

11

Rekurencyjne obliczanie silni (2)

12

Rekurencja może być kosztowna ...

public class Rekurencja04 {

static int licznik = 0;
static int fib(int n)
//obliczanie n-tej liczby Fibonacciego
{

licznik++;
if (n == 0) return 0;
else

if (n == 1) return 1;
else return fib(n-1) + fib(n-2);

}

public static void main(String [] args) {

System.out.println("5-ta liczba Fibonacciego to: " + fib(5));
System.out.println("Liczba wywolan funkcji:" + licznik);

}

}

2008-10-14

7

13

Efekt działania:

5-ta liczba Fibonacciego to: 5

Liczba wywolan funkcji: 15

Sposób wyznaczania liczb Fibonacciego

14

Jeśli istnieje oczywiste rozwiązanie iteracyjne, to należy je wybrać.

2008-10-14

8

Sterowanie kolejnością wykonywania działań (1)

public class Rekurencja05 {

static void sekwencja(int n) {

System.out.print(n + " ");
if (n > 0) sekwencja(n-1);

}
public static void main(String [] args) {

sekwencja(5);
System.out.println();

}

}
Efekt działania programu:
5 4 3 2 1 0

15

Sterowanie kolejnością wykonywania działań (2)

public class Rekurencja06 {

static void sekwencja(int n) {

if (n > 0) sekwencja(n-1);
System.out.print(n + " ");

}

public static void main(String [] args) {

sekwencja(5);
System.out.println();

}

}
Efekt działania programu
0 1 2 3 4 5

16

2008-10-14

9

17

Wieże Hanoi

public class Rekurencja08 {

static void przesun(int ile, char wiezaZrodlowa, char wiezaDocelowa, char wiezaPomocnicza)
{

if (ile == 1)

System.out.println(wiezaZrodlowa + " => " + wiezaDocelowa);

else
{

przesun(ile-1,wiezaZrodlowa,wiezaPomocnicza,

wiezaDocelowa);

System.out.println(wiezaZrodlowa + " => " +

wiezaDocelowa);

przesun(ile-1,wiezaPomocnicza,wiezaDocelowa,

wiezaZrodlowa);

}

}

18

Złożoność algorytmu: Wieże Hanoi (1)

•

Analizowana jest liczba przesunięć potrzebna do rozwiązania
zadania z n krążkami (liczbę przesunięć oznaczymy przez P(n))

•

gdy n = 1 to P(1) = 1

•

gdy n > 1 to P(n) = 2 * P(n – 1) + 1

2008-10-14

10

19

Złożoność algorytmu: Wieże Hanoi (2)

P(n-3)

P(n-3)

P(n-3)

P(n-3)

P(n-3)

P(n-3)

P(n-3)

P(n-3)

1

1

1

1

P(n-2)

P(n-2)

P(n-2)

P(n-2)

1

1

P(n-1)

P(n-1)

1

P(n)

Liczba
przesunięć

1

2

4

Poziom

0

1

2

3

20

Złożoność algorytmu: Wieże Hanoi (3)

•

P(n) = P1 + P2 + P3 + ... + Pn = 2

n

– 1

•

W powyższym wzorze zastosowany został wzór na sumę n
pierwszych elementów ciągu geometrycznego (o elementach
b

1

, b

2

, ..., bn i ilorazie q)

•

S

n

= b

1

* (q

n

– 1) / (q – 1)

2008-10-14

11

Inwersja elementów w wektorze (1)

public class Rekurencja07 {

static void wyswietlWektor(int [] w) {

for(int i = 0; i < w.length; i++)

System.out.print(w[i] + " ");

System.out.println();

}

21

Inwersja elementów w wektorze (2)

static void inwersja(int poczatek, int koniec, int [] w)

{

if (poczatek < koniec) {

int pomoc = w[poczatek];

w[poczatek] = w[koniec];

w[koniec] = pomoc;

inwersja(poczatek+1,koniec-1,w);

}

}

22

2008-10-14

12

Inwersja elementów w wektorze (3)

public static void main(String [] args)

{

int [] tab = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
wyswietlWektor(tab);
inwersja(0,tab.length-1,tab);
wyswietlWektor(tab);

}

}

Efekt działania programu:
1 2 3 4 5 6 7 8 9 10 11
11 10 9 8 7 6 5 4 3 2 1

23

24

Sortowanie szybkie (1)

•

Hoare, 1960

void quickSort(int tab[], int first, int last)

•

wybierz jedną z wartości znajdujących się w wektorze (w

poniższym algorytmie wybierana jest wartość znajdująca się

na pozycji o numerze first)

•

dokonaj przemieszczenia elementów w wektorze, tak aby

uzyskać:

elementy < x | x | elementy >= x

•

za pomocą tej samej procedury uporządkuj część wektora

znajdującą się na lewo od wartości „x” oraz część znajdującą

się na prawo od wartości „x”.

•

średnia złożoność obliczeniowa: O(n * log(n))

•

pesymistyczna złożoność obliczeniowa O(n

2

)

2008-10-14

13

25

Sortowanie szybkie (2)

public class QuickSort

{

public static void swap (int tab[], int x, int y) {

int temp = tab[x];

tab[x] = tab[y];

tab[y] = temp;

}

26

Sortowanie szybkie (3)

public static int partition(int tab[], int first, int last) {

int pivot = tab[first];

int up = first;
int down = last;

do {

while ((up < last) && (pivot >= tab[up])) up++;
while (pivot < tab[down]) down--;
if (up < down) swap(tab,up,down);

} while (up < down);

swap(tab,first,down);

return down;

}

2008-10-14

14

27

Sortowanie szybkie (4)

public static void quickSort(int tab[], int first,

int last) {

if (first >= last) return;

int pivot = partition(tab, first, last);

quickSort(tab, first, pivot-1);

quickSort(tab, pivot+1, last);

}

28

Sortowanie szybkie (5)

public static void main(String argv[]) {

int n = 10;

int tab[] = new int[n];
for (int i=0 ; i < n; i++)

tab[i] = (int) (100 * Math.random());

quickSort(tab, 0, n-1);

for (int i=0 ; i < n; i++)

System.out.print(tab[i] + " ");

System.out.println();

}

}

2008-10-14

15

Sortowanie przez łączenie – Mergesort (1)

•

sort(int poczatek, int koniec, int [] w),

•

podziel wektory na dwie połowy,

•

posortuj każdą z nich (za pomocą tej samej metody, o ile ich
długość > 1),

•

połącz posortowane części w całość,

•

złożoność obliczeniowa: O(n * log(n)).

29

Sortowanie przez łączenie – Mergesort (2)

public class MergeSort

{

static void wyswietlWektor(int [] w)

{

for(int i = 0; i < w.length; i++)

System.out.print(w[i] + " ");

System.out.println();

}

30

2008-10-14

16

Sortowanie przez łączenie – Mergesort (3)

static void sort(int poczatek, int koniec, int [] w)
{

if (poczatek >= koniec)

return;

int srodek = (poczatek + koniec) / 2;

sort(poczatek, srodek, w);
sort(srodek+1, koniec, w);

scal(poczatek, srodek, koniec, w);

}

31

Sortowanie przez łączenie – Mergesort (3)

static void scal(int poczatek, int srodek, int koniec, int [] w) {

int pocz1 = poczatek;
int kon1 = srodek;
int pocz2 = srodek + 1;
int kon2 = koniec;

while ((pocz1 <= kon1) && (pocz2 <= kon2))

{

if (w[pocz1] < w[pocz2]) pocz1++;
else {

int pomoc = w[pocz2];
for (int i = pocz2 - 1; i >= pocz1; i--)

w[i+1] = w[i];

w[pocz1] = pomoc;

pocz1++;
kon1++;
pocz2++;

}

}

}

32

2008-10-14

17

Sortowanie przez łączenie – Mergesort (4)

public static void main(String [] args)
{

int [] tab = {1, 5, 3, 7, 7, 9, 2, 3, 2, 2, 3};
wyswietlWektor(tab);
sort(0,tab.length-1,tab);
wyswietlWektor(tab);

}

}
Wynik działania programu
1 5 3 7 7 9 2 3 2 2 3
1 2 2 2 3 3 3 5 7 7 9

33