Metody -

algorytmy

rekurencyjn

e i

biblioteka

metod

Przegląd zagadnień

Pojęcie rekurencji
Przykład - Wieże Hanoi
Nadużywanie rekurencji
Algorytmy z powrotami
Demo: utworzenie biblioteki funkcji
Podsumowanie
Pytania sprawdzające
Laboratorium

Pojęcie rekurencji

Zdolność metody (funkcji) do wywołania samej

siebie
Typy rekurencji



rekurencja bezpośrednia



rekurencja pośrednia

Metoda dziel i zwyciężaj
Metoda iteracyjna

Metoda rekurencyjna

static ulong Silnia(uint n){

ulong iloczyn = 1;
for(uint i=2;i<=n;i++)

iloczyn *= i;

return iloczyn;

}

static ulong Silnia(uint n){

if(n == 0 || n == 1)

return 1;

return n * Silnia(n-1);
}

Przykład - Wieże Hanoi

w każdym kroku można przenieść dokładnie jeden krążek
krążek nie może być nigdy nałożony na krążek o

mniejszej średnicy

Mamy trzy pręty i n krążków o różnych średnicach,

które są nanizane są na pierwszy pręt w porządku

malejących średnic tworząc wieżę. Chcemy przenieść

krążki z pierwszego pręta na drugi, przy pomocy pręta

trzeciego stosując następujące zasady:

static void Hanoi(uint n, string zrodlo,string cel, string tmp)

{

if (n == 1)

Console.WriteLine("Przeniś z prętu {0} na pręt {1}.",

zrodlo, cel);

else{

Hanoi(n - 1, zrodlo, tmp, cel);

Console.WriteLine("Przeniś z prętu {0} na pręt {1}.",

zrodlo, cel);

Hanoi(n - 1, tmp, cel, zrodlo);

}

}

Nadużywanie rekurencji

static ulong Fib(ushort n){

if(n<2)

return n;

return Fib(n-1)+Fib(n-2);

}

Unikajmy rekurencji, jeżeli istnieje

oczywiste rozwiązanie iteracyjne!!!
Ciąg Fibonacciego:



















2

)

2

(

)

1

(

2

)

(

n

dla

n

Fib

n

Fib

n

dla

n

n

Fib

Fib(

5

)

Fib(

4

)

Fib(

3

)

Fib(

3

)

Fib(

2

)

Fib(

2

)

Fib(

1

)

Fib(

2

)

Fib(

1

)

Fib(

1

)

Fib(

0

)

Fib(

1

)

Fib(

0

)

Fib(

1

)

Fib(

0

)

1

1

0

1

0

1

Algorytmy z powrotami

Star

t

Metoda Sprawdz
we: krok - opis aktualnego
stanu

Wybierz następny, dopuszczalny, nieodwiedzony stan (ruch)

dostępny z bieżącej pozycji - krok, oznacz go jako krok2.

Oznacz stan krok2 jako odwiedzony

Czy osiągnięto

cel

Sprawdz(krok2);

N

Czy istnieje następny, dopuszczalny,

nieodwiedzony

stan dostępny z bieżącej pozycji

N

Stop

osiognietoCel=true;

T

osiognietoCel==

true

Oznacz stan krok2 jako nieodwiedzony

Stop

T

T

N

osignietoCel - pomocnicza
zmienne współdzielona

osiognietoCel=false;

Demo: utworzenie biblioteki

funkcji

Szablon projektu



Class Library

Korzystanie z bibliotki



w oknie Solution Explorer z menu
kontekstowego związanego z projektem
w którym chcemy skorzystać z biblioteki
wybrać Add Reference...

Podsumowanie

Pojęcie rekurencji
Przykład - Wieże Hanoi
Nadużywanie rekurencji
Algorytmy z powrotami
Demo: utworzenie biblioteki funkcji
Podsumowanie
Pytania sprawdzające
Laboratorium

Pytania sprawdzające

Co to jest rekurencja?
Na czym polega strategia "dziel i

rządź"?
Na czym polega programowanie

dynamiczne?

Laboratorium

Ćwiczenie 1:



Sortowanie szybkie - quick
sort

Ćwiczenie 2:



Problem ośmiu hetmanów