2008-10-14

Rekurencja

Wykład 02.

Algorytmy i struktury danych

Rok akademicki: 2008/09

Rekurencja

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

2

1

2008-10-14

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();

}

}

3

Przykład (2)

main()

Początek

Początek

Początek

Początek

{

f(x)

f(x)

f(x)

f(x)

i.t.d.

f()

Koniec

Koniec

Koniec

Koniec

}

4

2

2008-10-14

Przykład (3)

Efekt uruchomienia programu:

Poczatek

Poczatek

Poczatek

....

Poczatek

Exception in thread "main"

java.lang.StackOverflowError

5

Warunek stopu

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

6

3

2008-10-14

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();

}

}

7

Przykład (2)

licznik = 1

licznik = 2

licznik = 3

licznik = 4

licznik = 5

main()

licznik = 6

{

Początek

Początek

Początek

Początek

Początek

Początek

f()

f(x)

f(x)

f(x)

f(x)

f(x)

}

Koniec

Koniec

Koniec

Koniec

Koniec

Koniec

8

4

2008-10-14

Przykład (3)

Efekt uruchomienia programu:

Poczatek

Poczatek

Poczatek

Poczatek

Poczatek

Poczatek

Koniec

Koniec

Koniec

Koniec

Koniec

Koniec

9

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));

}

}

10

5

2008-10-14

Rekurencyjne obliczanie silni (2)

11

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);

}

}

12

6

2008-10-14

Efekt działania:

5-ta liczba Fibonacciego to: 5

Liczba wywolan funkcji: 15

13

Sposób wyznaczania liczb Fibonacciego

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

14

7

2008-10-14

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

8

2008-10-14

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);

}

}

17

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

18

9

2008-10-14

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

Liczba

Poziom

przesunięć

0

P(n)

1

P(n-1)

1

P(n-1)

1

2

P(n-2)

1

P(n-2)

P(n-2)

1

P(n-2)

2

3

P(n-3)

1

P(n-3)

P(n-3)

1

P(n-3)

P(n-3)

1

P(n-3)

P(n-3)

1

P(n-3)

4

19

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

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

• W powyższym wzorze zastosowany został wzór na sumę n pierwszych elementów ciągu geometrycznego (o elementach b , b , ..., bn i ilorazie q)

1

2

• S = b * (qn – 1) / (q – 1)

n

1

20

10

2008-10-14

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

11

2008-10-14

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

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(n2) 24

12

2008-10-14

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;

}

25

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;

}

26

13

2008-10-14

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);

}

27

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();

}

}

28

14

2008-10-14

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

15

2008-10-14

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

16

2008-10-14

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

17