WYKA
AD 8
Funkcje i algorytmy rekurencyjne
Proste przykłady
Programy: c3_1.c ......, c3_6.c
Tomasz Zieliński
METODY REKURENCYJNE (1) - program c3_1
======================================================================================================
Funkcja rekurencyjna wewnątrz wywołuje samą siebie.
======================================================================================================
/* Przyklad 3.1 - wypisz znaki z klawiatury w odwrotnej kolejnosci */
#include
void odwrotnie( void );
void main()
{
printf("\nPisz w linii. Zakoncz . \n\n");
odwrotnie();
}
// =========================
void odwrotnie( void )
{
char c; // wczytaj znak z klawiatury i podstaw jego
if ( (c=getchar() ) != '\n' ) // kod ASCII do c; jeśli nie jest to koniec linii, to:
{ //
odwrotnie(); // wywołaj ponownie funkcję odwrotnie()
printf( "%c", c); // wyświetl na ekranie znak c
}
}
METODY REKURENCYJNE (2) - program c3_1
Wypisz w odwrotnej kolejności znaki z klawiatury
ZAA
OŻENIE: z klawiatury:  ab [ENTER]
void main()
{ .....
odwrotnie();
c �!  a ;
.....
odwrotnie();
c �!  b ;
}
c �!  \n ;
odwrotnie();
void odwrotnie( void )
wypisz c;
{
char c;
wypisz c;
if ( (c=getchar()) != '\n' )
{
odwrotnie();
printf( "%c", c);
}
c jest lokalną zmienną każdego z wywołań funkcji,
}
która ma różną wartość w każdym z wywołań
METODY REKURENCYJNE (3) - program c3_1
Wypisz w odwrotnej kolejności znaki z klawiatury
Program główny ZAA
OŻENIE: z klawiatury:  abcd [ENTER]
a printf
b printf
c printf
d printf
\n
METODY REKURENCYJNE (4) - program c3_2
Zamiana integer na ASCII
/* Przyklad 3.2 - wypisz ma ekranie liczbę calkowitą */
/* czyli wartość INTEGER */
/* na sekwencję kodów ASCII jej cyfr */
#include
#include
void wypisz( int n );
/* program glowny -------------------------------------------------------------------- */
void main()
{
int x;
printf(" \n jaka liczba calkowita ? ");
scanf("%d", &x);
printf(" \n podane = %d \n", x);
printf(" rekursja = "); wypisz( x );
printf("\n");
}
/* Funkcja rekurencyjna ----------------------------------------------------------- */
void wypisz( int n )
{
int i;
// jeśli liczba ujemna,
if ( n < 0 ) { putchar('-'); n = -n; } // to napisz  - oraz zaneguj liczbę
if ( (i=n/10) != 0 ) wypisz( i ); // jeśli  i , czyli część całkowita z  n/10 ,
// jest różna od zera, to wywołaj ponownie
// ale z argumentem  i
putchar( 0 +n%10); // to (reszta z dzielenia n przez 10)
// putchar( '0' + (unsigned char) (n - 10 * i) ); // lub to (czyli najmniej znacząca cyfra)
}
METODY REKURENCYJNE (5) - program c3_2
Zamiana integer na ASCII
Program główny ZAA
OŻENIE: z klawiatury:  12345 [ENTER]
n
 5
= putchar( 0 + (unsigned char) (n % 10)
12345 putchar putchar
i = n/10
= putchar( 0 + (unsigned char) (n  10*i)
 4
n=1234 putchar
wypisz resztę z dzielenia n przez 10,
i = n/10
czyli najmniej znaczącą cyfrę n
 3
n=123 putchar
i = n/10
 2
n=12 putchar
i = n/10
 1
n=1 putchar
METODY REKURENCYJNE (6) - program c3_3
n! czyli n-silnia
/* Przyklad 3.3 - METODY REKURENCYJNE - oblicz n! */
/* n! = 1*2*3*...*(n-1)*n np. 5! = 1*2*3*4*5 */
#include
long silnia( long n );
/* program glowny -------------------------------------------------------------- */
void main()
{
long n, x, iloczyn;
printf("\n Obliczam funkcje n ! Podaj n ? [max 12] ");
scanf("%ld", &n);
/* Metoda iteracyjna */
iloczyn = 1;
for( x = n; x > 0; x--)
{ iloczyn = iloczyn * x; }
printf( "\n Metoda iteracyjna --> n! = %ld \n", iloczyn );
/* Metoda rekurencyjna */
iloczyn = silnia( n );
printf( "\n Metoda rekurencyjna --> n! = %ld \n", iloczyn);
}
/* Funkcja rekurencyjna ----------------------------------------------------------- */
long silnia( long n )
{
long x, y;
if( n == 0L ) return(1); // L znaczy long
x = n-1;
y = silnia(x); /* rekurencyjne wywolanie */
return(n*y);
}
long silnia( long n )
{
if( n == 0L ) return(1);
return(n* silnia(n-1)); /* rekurencyjne wywolanie */
}
METODY REKURENCYJNE (7) - program c3_3
n! czyli n-silnia
Program główny ZAA
OŻENIE: z klawiatury:  4 [ENTER]
n
long silnia( long n )
24
4 4*(3*2*1*1)
{
long x, y;
n-1
if( n == 0L ) return(1);
3 3*(2*1*1)
6
x = n-1;
n-1 y = silnia(x);
return(n*y);
2
2 2*(1*1)
}
n-1
long silnia( long n )
1
1 1*(1)
{
if( n == 0L ) return(1);
n-1
return( n*silnia(n-1) );
}
0 1
1
METODY REKURENCYJNE (8) - program c3_5
szukanie elementu metodą podziału zbioru
na dwie części
indeks tablica
ZADANIE: znalez
ć indeks  i tablicy,
i
dla którego: tab[ i ] == x
N-1 2.0
"
ROZWI
ZANIE 1 (sekwencyjne):
"
i = 0;
"
while( ( x != tab[i] ) & (i < N-1) )
15 1.5
x = 1.5
i++;
"
ROZWI
ZANIE 2 (rekurencyjne):
"
int szukaj( int tab[ ], int x, int dol, int gora )
"
{ int srodek;
5
0.5
4
srodek = (dol + gora)/2;
0.4
if ( x == tab[ srodek ] ) return( srodek);
3
0.3
if ( x < tab[ srodek ] )
return( szukaj( tab, x, dol, srodek - 1 ) );
2 0.2
else
1 0.1
return( szukaj( tab, x, srodek + 1, gora ) );
0 0.0
}
METODY REKURENCYJNE (9) - program c3_5
DYGRESJA: przetworniki A/C bezpośredniego porównania
Urange Ux Urange
Urange
Nr=7 A/C=111
0
K
R
"U
Nr=6 A/C=110
K 0 Nr=5 A/C=101
Ux
Ux
R
Nr=4 A/C=100
1
K
R
U3 Nr=3 A/C=011
K 1
U2 Nr=2 A/C=010
R
R
1
K
U1 Nr=1 A/C=001
R
U0 Nr=0 A/C=000
0
METODY REKURENCYJNE (10) - program c3_5
DYGRESJA: przetworniki A/C kompensacyjne:
równomierny (po lewej) i wagowy (po prawej)
0/1
Ux
K
0/1
Ux
K
UC/A
Ulicznika
C/A UREF
UREF
C/A
0 0 1 1
Stop
0 0 1 1
Stop
Układ logiki
Licznik/Generator
Start
UC/A
Start
Uzakres Uzakres
Ulicznika
3/4Uz
Ux
Ux
1/2Uz
1/4Uz
stan licznika
" " "
0000 0001 0010 0011 0100
0 1 2 3 nr bitu C/A
METODY REKURENCYJNE (11) - program c3_5
szukanie metodą podziału na dwie części
/* Przyklad 3.5 - METODY REKURENCYJNE - szukanie "dwojkowe" */
/* WEJŚCIE: tab = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] */
/* x = liczba naturalna z klawiatury */
/* WYJŚCIE: położenie (indeks) elementu x w tablicy tab[] */
#include
int szukaj( int tab[ ], int x, int dol, int gora );
void main()/* program glowny ---------------------------------------------------------------------- */
{
int tab[ 11 ] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 };
int x, indeks, dol, gora;
printf("\n Jaka jest calkowita wartosc poszukiwanego elementu ? ");
scanf("%d", &x);
dol = 0; gora = 10;
indeks = szukaj( tab, x, dol, gora );
printf( "\n Indeks = %i \n", indeks);
}
/* funkcja rekursywna ----------------------------------------------------------------- */
int szukaj( int tab[ ], int x, int dol, int gora )
{
int srodek;
if ( dol > gora ) return(-1); // -1 oznacza brak takiego elementu w zbiorze
srodek = (dol + gora)/2;
if ( x == tab[ srodek ] ) return( srodek);
if ( x < tab[ srodek ] )
return( szukaj( tab, x, dol, srodek - 1 ) );
else
return( szukaj( tab, x, srodek + 1, gora ) );
}
/* funkcja nierekursywna ----------------------------------------------------------------- */
int szukajX( int tab[], int x, int dol, int gora)
{
int srodek;
while( dol <= gora )
{
srodek = (dol + gora)/2;
if( x==tab[srodek]) return(srodek);
if ( x < tab[ srodek ] )
gora = srodek - 1;
else
dol = srodek + 1;
}
return(-1);
}