Podstawy programowania
(język C)
funkcje rekurencyjne
Wykład 13.
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-1- -2-
Funkcje rekurencyjne (1) Funkcje rekurencyjne (2)
Ilustracja rekurencji pośredniej jest trochę bardziej zło\
ona. N.p.
W języku C funkcja mo\
e wywoływać samą siebie.
int H ( int x ); // niezbędna deklaracja
Taką funkcję nazywamy funkcją rekurencyjną.
Rekurencja mo\
e być realizowana bezpośrednio, jak i pośrednio. int G ( int x ) // funkcja rekurencyjna
{
int y, z;
N.p. Schemat funkcji
...................................
z = H( y );
...................................
int F ( int x )
}
{
int H ( int x ) // funkcja pośrednicząca
int y, z;
{
...................................
int y, z;
................................... ...................................
z = G( y );
z = F( y );
...................................
...................................
}
...................................
W powy\
szym przykładzie rekurencyjna funkcja G wywołuje samą siebie
}
za pośrednictwem funkcji H.
Oczywiście, głębokość takiego pośrednictwa mo\
e być większa.
ilustruje realizację rekurencji bezpośredniej.
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-3- -4-
Funkcje rekurencyjne (3) Funkcje rekurencyjne (4a)
Klasycznym przykładem jest u\
ycie rekurencji do obliczania wartości
Ale wzór dla n >= 2
silni ( ! ):
n! == 1* 2 * ...* (n-1) * n
0! == 1
1! == 1
mo\
emy zapisać w postaci:
dla n >= 2
n! == n * (n-1)!
n! == 1* 2 * ...* (n-1) * n
Ten ostatni wzór mo\
e być zrealizowany iteracyjnie
albo
int i, s=1;
silnia(n) == n * silnia(n-1)
for ( i=2; i<=n; ++i ) s = s * i;
co prowokuje, \
eby napisać definicję funkcji:
co pozwala napisać definicję funkcji:
int silnia ( int n )
int Silnia ( int n )
{
{
int i, s=1;
if ( n <= 1 ) return 1;
if ( n < 2 ) return 1;
for ( i=2; i<=n; ++i ) s *= i;
return n * Silnia( n-1 );
return s;
}
}
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-5- -6-
Funkcje rekurencyjne (4b) Funkcje rekurencyjne (5)
Ale wzór dla n >= 2
n! == 1* 2 * ...* (n-1) * n
mo\
emy zapisać w postaci:
n! == n * (n-1)!
albo
silnia(n) == n * silnia(n-1)
ewentualnie:
int Silnia ( int n )
{
return ( n < 2 ) ? 1 : n * Silnia( n-1 );
}
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-7- -8-
Funkcje rekurencyjne (5) Funkcje rekurencyjne (6)
Inny przykład funkcji rekurencyjnej mo\
na znalez
ć w ksią\
ce Kerninhana
i Ritchie'go. Funkcja realizuje wypisywanie liczby całkowitej w postaci
ciągu znaków.
#include
/* printd: wypisz n dziesiętnie */
void printd ( int n )
{
if ( n < 0 )
{
putchar ( '-' );
n = -n;
}
if ( n / 10 ) printd ( n / 10 );
putchar ( n % 10 + '0' );
}
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-9- -10-
Sortowanie (1)
Sortowanie jest zadaniem polegającym na porządkowaniu elementów
jakiegoś zbioru według ustalonego kryterium.
N.p.
porządkowanie tablicy liczb
według rosnących/malejących wartości jej elementów
porządkowanie listy struktur zawierających dane osobowe
SORTOWANIE
według alfabetycznej kolejności nazwisk
porządkowanie pliku dyskowego zawierającego opisy
magazynowanych towarów
według rosnących/malejących wielkości cen
Istnieje bardzo wiele algorytmów sortowania. N.p. bąbelkowe,
przez wstawianie, quicksort, ... Wybór zale\
y od sposobu reprezentacji
i wielkości (liczebności elementów) rozpatrywanego zbioru.
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-11- -12-
Sortowanie (2) Sortowanie (3a)
Jednym z najprostrzych algorytmów sortowania jest tzw.
sortowanie bąbelkowe.
Metoda polega na wielokrotnym przeglądaniu zawartości zbioru
i porównywaniu wartości kolejnych par jego elementów.
Je\
eli para jest w niewłaściwej kolejności, to jej elementy są zamieniane
miejscami.
Dla przykładu rozpatrzmy tablicę
To nasza tablica, którą chcemy
int A[ 5 ] = { 2, 5, 8, 1, 4 };
uporządkować w kolejności
którą chcemy uporządkować według rosnących wartości jej elementów.
rosnących wartości elementów.
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-13- -14-
Sortowanie (3b) Sortowanie (3c)
Pierwsza para elementów. Kolejna para elementów.
We właściwym porządku.
Te\
we właściwym porządku.
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-15- -16-
Sortowanie (3d) Sortowanie (3e)
Po wykonaniu zamiany.
Elementy w niewłaściwym porządku.
Trzeba je zamienić miejscami.
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-17- -18-
Sortowanie (3f) Sortowanie (3g)
Po wykonaniu zamiany.
Elementy w niewłaściwym porządku.
Trzeba je zamienić miejscami.
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-19- -20-
Sortowanie (3h) Sortowanie (4)
Mo\
emy łatwo opisać jeden przebieg algorytmu:
int n=5, i;
for ( i = 0; i < n-1; i++ )
if ( A[ i ] > A[ i+1 ] )
{
int tmp = A[ i ];
A[ i ] = A[ i+1 ];
A[ i+1 ] = tmp;
}
Po wykonaniu pierwszego przebiegu
W kolejnym przebiegu warunek i < n-1
element o największej wartości
powinniśmy zastąpić przez i < n-2
w następnym przez i < n-3
znajduje się na ostatniej pozycji.
itd.., itd..,
a\
do i<1 co mo\
na zapisać jako i < n-(n-1)
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-21- -22-
Sortowanie (5) Sortowanie (6)
Powy\
szą uwagę uwzględnimy definicji funkcji:
Czyli cały algorytm
void bubblesort ( int A[ ], int n )
{
int n=5, i, j;
int i, j;
if ( n < 2 ) return;
for ( j = 1; j< n; j++ )
for ( j = 1; j< n; j++ )
for ( i = 0; i < n-j; i++ )
{
if ( A[ i ] > A[ i+1 ] ) int przerwij = 1;
{
for ( i = 0; i < n-j; i++ )
int tmp = A[ i ];
if ( A[ i ] > A[ i+1 ] )
{
A[ i ] = A[ i+1 ];
int tmp = A[ i ];
A[ i+1 ] = tmp;
A[ i ] = A[ i+1 ];
} A[ i+1 ] = tmp;
przerwij = 0;
}
if ( przerwij ) break;
Zauwa\
my, \
e jeśli dla jakiegoś j pętla for ( i=0; i}
"wykręci" się bez wykonania choćby jednej zamiany, to znaczy,
}
\
e wszystkie elementy są ju\
we właściwej kolejności, a więc obliczenia
nale\
y przerwać.
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-23- -24-
Sortowanie (7)
A teraz zobaczmy rekurencyjną wersję naszej funkcji:
void bubsort ( int A[ ], int n )
{
int i, przerwij = 1;
jeszcze na temat ...
if ( n < 2 ) return;
// zaczynamy sortowanie tablicy n-elementowej
SORTOWANIE
for ( i = 0; i < n-1; i++ )
if ( A[ i ] > A[ i+1 ] )
{
int tmp = A[ i ];
A[ i ] = A[ i+1 ];
funkcja qsort( )
A[ i+1 ] = tmp;
przerwij = 0;
}
if ( przerwij ) return; // tablica jest ju\
posortowana
bubsort( A, n-1 ); // trzeba posortować tablicę (n-1)-elementową
}
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-25- -26-
qsort (1) qsort (2)
Funkcja wskazana przez cmp musi zwracać:
Funkcja standardowa qsort ma deklarację w pliku stdlib.h
wartość ujemną, gdy obiekt *a jest mniejszy obiektu *b;
void qsort ( void *base, size_t n, size_t size,
zero, gdy obiekt *a jest równy *b;
int (*cmp)(const void* a, const void* b) );
wartość dodatnią, gdy obiekt *a jest większy od obiektu *b.
N.p. dla tablicy danych typu int odpowiednia funkcja mo\
e mieć postać:
Porządkuje w kolejności rosnącej tablicę
int i_cmp ( const void* a, const void* b )
tab[0], tab[1], ...... tab[n-1]
{
int A = *(int*)a, B = *(int*)b;
składającej się z
return A - B;
n elementów
}
o rozmiarze
lub
size bajtów,
int i_cmp ( const void* a, const void* b )
cmp jest wskazaniem funkcji porównującej 2 elementy.
{
return *(int*)a - *(int*)b;
Parametr base przekazuje adres początku tablicy tab, t.zn.
}
base == (void *) tab
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-27- -28-
qsort (3) qsort (4)
N.p. dla tablicy danych typu double odpowiednia funkcja mo\
e mieć N.p. dla tablicy danych typu
postać:
struct Osoba
{
int d_cmp ( const void* a, const void* b ) char nazwisko [20];
{ char imie [20];
double A = *(double*)a, int wiek;
B = *(double*)b; double waga;
}
return (A-B<0) ? -1 : ( (A-B>0) ? 1 : 0 );
}
dla uporządkowania według alfabetycznej kolejności nazwisk
odpowiednia funkcja mo\
e mieć postać:
int On_cmp ( const void* a, const void* b )
UWAGA: return A  B; nie będzie tu właściwym rozwiązaniem. {
int k = strcmp ( (struct Osoba*)a->nazwisko, (struct Osoba*)b->nazwisko );
Dlaczego???
}
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-29- -30-
qsort (5) qsort (6)
N.p. dla tablicy danych typu
Dla tablic danych
struct Osoba
int A[100];
{
char nazwisko [20];
double B[30];
char imie [20];
int wiek;
struct Osoba C[75];
double waga;
}
wywołania porządkujące powy\
sze tablice powinny mieć postać:
dla uporządkowania według alfabetycznej kolejności nazwisk i imion
odpowiednia funkcja mo\
e mieć postać:
qsort ( A, 100, sizeof(int), i_cmp );
qsort ( B, 30, sizeof(double), d_cmp );
int Oni_cmp ( const void* a, const void* b )
{
qsort ( C, 75, sizeof(struct Osoba), On_cmp ); // dla nazwisk
int k = strcmp ( (struct Osoba*)a->nazwisko, (struct Osoba*)b->nazwisko );
if ( k ) return k; qsort ( C, 75, sizeof(struct Osoba), Oni_cmp ); // dla nazwisk i imion
return strcmp ( (struct Osoba*)a->imie, (struct Osoba*)b->imie );
}
Tomasz Marks - Wydział MiNI PW Tomasz Marks - Wydział MiNI PW
-31- -32-
Koniec wykładu 13.
Tomasz Marks - Wydział MiNI PW
-33-