Dr Aleksander Klosow

Algorytmy i Struktury Danych

Wykład

REKURENCJA

POJĘCIE REKURENCJI

rekursja, (ang.) recursion

Rekurencja występuję wtedy, gdy definiując pewien obiekt musimy się posłużyć pojęciem tego samego obiektu !

• Odbicie w 2 lustrach

• Kamera filmująca sprzężony monitor

• Funkcja odwołująca się w trakcie swojego wykonania do samej siebie

• Algorytm wykorzystujący do rozwiązania części swojego zadania taki sam algorytm

SILA REKURENCJI

1. Możliwość definiowania nieskończonego zbioru obiektów lub działań za pomocą skończonego wyrażenia

2. Jeżeli dane wejściowe są zdefiniowane rekurencyjnie

PRZYKŁAD na dobry początek

0! = 1 n! = n(n-1)!

unsigned long int silnia(int n)

{

if(n==0) return 1;

else return n*silnia(n-1);

};

main(){ cout << silnia(5);}

Definicja algorytmu rekurencyjnego

P - algorytm rozwiązujący zadanie

S_i - instrukcje podstawowe algorytmu

ℜ - złożenie instrukcji algorytmu

P ≡ ℜ [S_i, P] - podstawowa definicja algorytmu rekurencyjnego

P ≡ if warunek then ℜ [S_i, P]

} - typowe schematy algorytmów rekurencyjnych

P ≡ ℜ [S_i, if warunek then P]

ETAPY PROJEKTOWANIA

1. Rozbić duży problem na mniejsze powtarzające się fragmenty

2. Określić warunek stopu algorytmu

3. Wybrać właściwy schemat rekurencji

! Powody niepowodzenia:

1. Źle określone warunki stopu

2. Niewłaściwa dekompozycja problemu

0! = 1 n! = n(n-1)! = n • (n-1) • (n-2) • (n-3)...2 • 1

WYKONANIE ALGORYTMU REKURENCYJNEGO W PAMIĘCI

n return

silnia(5) ------------------------------------ 5 5*silnia(4)

silnia(4) ------------------------------------ 4 4*silnia(3)

silnia(3) ------------------------------------ 3 3*silnia(2)

silnia(2) ------------------------------------ 2 2*silnia(1)

silnia(1) ------------------------------------ 1 1*silnia(0)

silnia(0) ------------------------------------ 0 1

REKURENCYJNE TYPY DANYCH

pascal (Delphi) c

type osoba = record imie : String[10]; matka : osoba; ojciec : osoba; end

typedef struct osoba { char imie[10]; osoba matka; osoba ojciec; }

ZALETY REKURENCJI

1. Krótki opis algorytmu, mało kodu programu, czytelność

2. Lepsza dla danych rekurencyjnych

3. 'Elegancja' w stylu programowania

WADY REKURENCJI

Wada 1: REDUNDANCJA OBLICZEŃ

int fib(int n) { if(n<2) return 1; else return fib(n-1)+fib(n-2); }

Function Fib(n:integer):integer; begin if n<2 then Fib:=1 else Fib:=Fib(n-1)+Fib(n-2) end

fib(4)

fib(3) fib(2)

fib(2) fib(1) fib(1) fib(0)

fib(1) fib(0)

WADY REKURENCJI

Wada 2: ZAJĘTOŚĆ PAMIĘCI

Funkcja Ackermanna

int A(int n, int p)

{

if(n==0) return 1;

if((p==0) && (n>=1))

if(n==1) return 2;

else return n+2;

if((p>=1)&&(n>=1)) return A(A(n-1,p),p-1);

}

Co zwróci funkcja przy n=1, p=1 ?

Co zwróci funkcja przy n=2, p=4 ?

Liczba wywołań funkcji Ackermanna:

A(1,4) ⇒ 2

A(2,4) ⇒ 4

A(3,4) ⇒ 65536

TYPY REKURENCJI

Naturalna P ≡ ℜ [S_i, P]

Z parametrem P ≡ if (par>0) then ℜ [S_i, P, par-1]

Bezpośrednia P ≡ ℜ [..., P]

Pośrednia P ≡ ℜ [..., T], T = ℑ[..., P]

Terminalna P ≡ ℜ [S_i, P]

Nie terminalna P ≡ ℜ [S_i, P, S_j]

Wielokrotna P ≡ ℜ [S_i, P¹, P²]

Zagnieżdżona P ≡ ℜ [S_i, P¹(P²)]

KIEDY NIE STOSOWAĆ REKURENCJE

Reguła 1: Kiedy rozwiązanie iteracyjne jest bardziej czytelne i zrozumiałe

Lub inaczej:

Kiedy można zastosować derekursywację rozwiązania rekurencyjnego

DEREKURSYWACJA

Proces przekształcenia algorytmu rekurencyjnego na algorytm iteracyjny

Schemat dla rekurencji terminalnej

P1(x) // -- program rekurencyjny { if(Warunek(x)) Instrukcja1(x) else { Instrukcja2(x); P1(F(x)); // -- rekurencja } }

P2(x) // -- program iteracyjny { while(!Warunek(x)) { Instrukcja2(x); x=F(x); } Instrukcja1(x); }

DEREKURSYWACJA, c.d.

Schemat dla rekurencji nie terminalnej

P1() // -- program rekurencyjny { if(Warunek(x)) { A(x); P1(); // -- rekurencja B(x); } else C(x); }

P2(x) // -- program iteracyjny { int N=0; // -- liczba iteracji while(Warunek(x)) { A(x); N++; // -- analogicznie N=N+1 } C(x); while(N--!=0) B(x); }

KIEDY STOSOWAĆ REKURENCJĘ

1. Do pewnej klasy zadań gier komputerowych

2. Do pewnej klasy zadań graficznych

3. Do pewnej klasy zadań "Algorytmy z powrotami"

• Wieża Hanoi

• Krzywe Hilberta

• Problem skoczka szachowego

WIEŻA HANOI

Zadanie. Dano n krążków o malających średnicach. Należy przełożyć krążki z drążka A na drążek B posługując się pomocniczym drążkiem C. Reguły: 1/ W jednym ruchu można brać jeden krążek; 2/ Krążek o mniejszej średnicy nie może być przykryty krążkiem o większej średnicy.

WIEŻA HANOI

Implementacja algorytmu w języku C (T((2ⁿ-1)*t))

Hanoi(int n, int a, int b) // -- funkcja rekurencyjna { if(n==1) { // Przesuń dysk nr n z pozycji a na b; else { Hanoi(n-1,a,3-a-b); // Przesuń dysk nr n z pozycji a na b; Hanoi(n-1,3-a-b,b); } } } void main() { Hanoi(4,0,1); }

PROBLEM SKOCZKA

Skoczek (S) musi przejść przez wszystkie

pola szachownicy NxN odwiedzając

każde pole dokładnie raz.

ALGORYTM PROBLEMU SKOCZKA

zdefiniuj ustawienie początkowe

repeat

begin

wybierz następny ruch

if ruch jest możliwy then

begin

zaznacz wykonanie ruchu

if są jeszcze wolne pola then

begin

wykonaj rekurencyjnie procedurę dla następnego ruchu

if ruch nie jest możliwy then

skasuj zapis ostatniego ruchu

end

end

end

until ruch został wykonany poprawnie lub nie ma więcej możliwych

ruchów

KRZYWE HILBERTA, 1891 rok

	Krzywe 1,2 poziomów Krzywe 1,2,3 poziomów	Krzywe 1-5 poziomów
Schemat rekurencji:

PRZYKŁADY REKURENCJI

1. Rekurencyjne wyznaczenie ekstremum w zbiorze:

int Max(int *tab, int n, int max)

{ if(n<0) return max;

else return Max(tab, n-1, ((tab[n]>max)?tab[n]:max) );

}

2. Rekurencyjne odwrcanie elementów w tablicy:

void Reverse(int *tab, int l, int r)

{ if(l>r) return;

else { int pom = tab[l]; tab[l] = tab[r]; tab[r] = pom; Reverse(tab, l+1, r-1); }

}

3. Zastosowanie rekurencji prawostronnej do problemu silni:

int Silnia(int n, int a)

{ if(n<0) return 0;

else if(n==0) return 1;

else if(n==1) return a;

else return Silnia(n-1, n*a); // rekurencja prawostronna oszczędza pamięć

}

A.Klosov, Algorytmy i Struktury Danych, REKURENCJA

3

7

4

s

5

6

6

5

 

1

2

3

6

2

8

1

2

3

5

1

4

4

---