Podstawy programowania. Wykład 12  rekurencja
Małgorzata Nalbach-Moszyńska
12. Rekurencja.......................................................................................................................... 2
12.1 Wykorzystanie stosu. ............................................................................................... 2
12.2 Linijka. ..................................................................................................................... 3
12.3 Ciągi zdefiniowane rekurencyjnie. .......................................................................... 4
12.4 Wieże Hanoi............................................................................................................. 6
12.5 Analiza składniowa metodą zejść rekurencyjnych. ................................................. 8
1
Podstawy programowania. Wykład 12  rekurencja
Małgorzata Nalbach-Moszyńska
12. Rekurencja.
Funkcja rekurencyjna  funkcja, która wywołuje samą siebie. Naturalne postępowanie: np.
zbierając rozsypane pionki do gry podnosi się zwykle pierwszy, a potem zbiera się resztę w
ten sam sposób.
Schemat funkcji:
void rekur ()
{
;
if ( ) rekur ()

}
UWAGA
Trzeba bardzo dokładnie ustalić , żeby mieć pewność, że ciąg wywołań się
zakończy.
12.1 Wykorzystanie stosu.
Kolejne wywołania z parametrami są umieszczane na stosie.
Rekurencja jawna jest możliwa tylko w językach obsługujących stos wywołań!
Przykład 1
#include
const int NMAKS = 15;
long int SILNIA(int n){
if(n<1)
return 1;
else
return n * SILNIA(n-1);
}
int main (){
int liczba;
printf("Jakiej liczby policzymy silnie? ");
scanf("%d", &liczba);
if (liczba > NMAKS) printf("******Niestety za duza liczba\n");
else if (liczba<0) printf("******Liczba ujemna\n");
else
printf("silnia liczby %d wynosi %d\n", liczba,
SILNIA(liczba));
return 0;
2
Podstawy programowania. Wykład 12  rekurencja
Małgorzata Nalbach-Moszyńska
Realizacja
12.2 Linijka.
Strategia: dziel i zwyciężaj
Rysowanie podziałki na linijce:
1. zaznacz dwa końce;
2. znajdz
i zaznacz środek;
3. wykonaj to samo dla lewej połowy podziału
4. wykonaj to samo dla prawej połowy podziału
3
Podstawy programowania. Wykład 12  rekurencja
Małgorzata Nalbach-Moszyńska
/* ruler.cpp - uzycie rekurencji do dzielenia linijki */
#include
const int Len = 66;
const int Divs = 6;
void subdivide(char ar[], int low, int high, int level);
int main()
{
char ruler[Len];
int i, j;
int max, min;
for (i = 1; i < Len - 2; i++)
ruler[i] = ' ';
ruler[Len - 1] = '\0';
max = Len - 2;
min = 0;
ruler[min] = ruler[max] = '|';
printf( "%s\n",ruler);
for (i = 1; i <= Divs; i++)
{
subdivide(ruler,min,max, i);
printf( "%s\n",ruler);
for (j = 1; j < Len - 2; j++)
ruler[j] = ' '; /* zerowanie linijki */
}
return 0;
}
void subdivide(char ar[], int low, int high, int level)
{
int mid;
if (level == 0) /* zmienna level kontroluje poziom
rekurencji */
/* przy każdym wywołaniu zmniejszana o 1 */
return;
mid = (high + low) / 2;
ar[mid] = '|';
subdivide(ar, low, mid, level - 1);
subdivide(ar, mid, high, level - 1);
}
12.3 Ciągi zdefiniowane rekurencyjnie.
Ciąg Fibonacciego
Obliczanie parametrów ciągu tego i innych, podobnych typów, wykonane bezpośrednio na
podstawie wzoru matematycznego, może powodować problemy w postaci zbyt wielu
dublujących się obliczeń. Ciąg Fibonacciego jest zdefiniowany rekurencyjnie, w sposób
analogiczny do definicji funkcji silnia:
4
Podstawy programowania. Wykład 12  rekurencja
Małgorzata Nalbach-Moszyńska
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2)
Zadanie obliczania elementów takiego ciągu można w języku C zapisać niemal dokładnie tak
samo, jak wyraża to wzór definicyjny:
unsigned long int FIB( int n ){
if (x<2) return 1;
else return FIB(n-1) + FIB(n-2);
}
Schemat wywołań rekurencyjnych, jak wykaże prosta analiza kodu, doprowadzi do
następującego drzewa wywołań:
Drzewo wywołań funkcji FIB dla parametru 4.
Widać od razu, że gałęzie zaznaczone kolorem wykonują się dwa razy. Zupełnie
niepotrzebnie. W sumie, wywołanie funkcji FIB dla większych parametrów n, spowoduje że
wykonane zostanie w przybliżeniu 2n obliczeń, co jest z oczywistych powodów
nieefektywne. Dlatego należy pamiętać, że nie jest dobrą metodą programowanie
rekurencyjne tam, gdzie wystarczą proste funkcje iteracyjne.
Przykład 3
/* w12p3.c - użycie rekurencji do wyliczania elementów ciągu
Fibonacci'ego. */
#include
#include
unsigned long int FIB( int n );
unsigned long int FIB2( int n );
int main()
{
int zakres;
int i;
printf("Ile elementow chcesz tworzyc? ");
scanf("%d",&zakres);
for (i=0;i<=zakres; ++i)
{
printf(" fib(%d)=%d\n",i,FIB(i));
}
5
Podstawy programowania. Wykład 12  rekurencja
Małgorzata Nalbach-Moszyńska
printf("********* Iteracyjnie\n");
FIB2(zakres);
return 0;
}
unsigned long int FIB( int n ){
if (n<2) return 1;
else return FIB(n-1) + FIB(n-2);
}
unsigned long int FIB2( int n ){
int i;
unsigned long int *fibTab= malloc(sizeof(unsigned long int)*
(n+1));
if (n<2) return 1;
else {
fibTab[0]=fibTab[1]=1;
for (i=2; i<=n; ++i){
fibTab[i]=fibTab[i-1]+fibTab[i-2];
printf("fib(%d) = %d\n",i, fibTab[i]);
}
return fibTab[n];
}
}
12.4 Wieże Hanoi.
Wieże Hanoi  problem polegający na odbudowaniu, z zachowaniem kształtu, wieży z
krążków o różnych średnicach (popularna dziecięca zabawka), przy czym podczas
przekładania wolno się posługiwać buforem (reprezentowanym w tym przypadku przez
dodatkowy słupek), jednak przy ogólnym założeniu, że nie wolno kłaść krążka o
większej średnicy na mniejszy ani przekładać kilku krążków jednocześnie. Jest to przykład
zadania, którego złożoność obliczeniowa wzrasta niezwykle szybko w miarę zwiększania
parametru wejściowego, tj. liczby elementów wieży. Dla n krążków złożoność wynosi:
2n -1
6
Podstawy programowania. Wykład 12  rekurencja
Małgorzata Nalbach-Moszyńska
Rysunek 1 Od lewej: słupek A z całą wieżą, pusty słupek B pełniący rolę bufora i pusty słupek docelowy C
http://upload.wikimedia.org/wikipedia/commons/6/60/Tower_of_Hanoi_4.gif
Wieże Hanoi można łatwo rozwiązać za pomocą prostego algorytmu rekurencyjnego lub
iteracyjnego.
" Oznaczmy kolejne słupki literami A, B i C.
" Niech n będzie liczbą krążków, które chcemy przenieść ze słupka A na słupek C
posługując się słupkiem B jako buforem.
Rozwiązanie rekurencyjne
Algorytm rekurencyjny składa się z następujących kroków:
1. przenieś (rekurencyjnie) n-1 krążków ze słupka A na słupek B posługując się
słupkiem C,
2. przenieś jeden krążek ze słupka A na słupek C,
3. przenieś (rekurencyjnie) n-1 krążków ze słupka B na słupek C posługując się słupkiem
A
Przykładowa implementacja
/* w12 p4 Problem wiez Hanoi. Trzy slupki oznaczone A,B i C.
Program wyświetla kolejność ruchów - z ktorego na ktory slupek. */
#include
int NrRuchu = 1;
void hanoi(int n, char A, char B, char C) {
/* przekłada n krążków z A korzystając z B na C */
if (n > 0) {
hanoi(n-1, A, C, B);
printf("%d. %c -> %c\n",NrRuchu++,A, C);
hanoi(n-1, B, A, C);
}
}
7
Podstawy programowania. Wykład 12  rekurencja
Małgorzata Nalbach-Moszyńska
int main() {
int LiczbaKrazkow;
printf("Podaj liczbe krazkow ");
scanf("%d",&LiczbaKrazkow);
while (LiczbaKrazkow<=0 || LiczbaKrazkow>10)
{
printf("Bledna liczba klockow. Podaj jeszcze raz liczbe od 1 do 1o.\n");
printf("Podaj liczbe krazkow ");
scanf("%d",&LiczbaKrazkow);
}
hanoi(LiczbaKrazkow, 'A', 'B', 'C');
return 0;
}
12.5 Analiza składniowa metodą zejść rekurencyjnych.
Gramatyka bezkontekstowa wyrażeń arytmetycznych:
::=  + |
 - |

::= * |
/ |

::= |
().
Dla każdego symbolu nieterminalnego (umieszczony w nawiasach <>) piszę funkcję.
Przykład 5.
Kalkulator wyrażeń arytmetycznych z nawiasami.
#include
#include
/* ::=  + |
 - |

::= * |
/
::= |
().
*/
8
Podstawy programowania. Wykład 12  rekurencja
Małgorzata Nalbach-Moszyńska
typedef enum {PlusSm,MinusSm,RazySm,
DzielSm,LewyNawSm, PrawyNawSm, LiczbaSm, PustySm}
symbole;
#define MAXBUF 101
struct symb {
symbole SymbNm;
double wart;
} symbol;
char buforek[MAXBUF];
int pozBuf = 0;
void scan()
/* pobiera z bufora kolejny symbol, rozpoznaje jego rodzaj;
jeżeli wczyta liczbę, to jej wartość umieszcza w polu wart
struktury symbol */
{
int wart;
char znak;
while ((znak = buforek[pozBuf++])== ' '); /* zjadamy spacje z
poczatku */
if (isdigit(znak))
{
symbol.SymbNm = LiczbaSm; /* argumenty tylko calkowite
*/
wart = znak - '0';
while (isdigit(znak = buforek[pozBuf]))
{wart = 10*wart+ (znak - '0');
pozBuf++;
}
symbol.wart = wart;
}
else {
switch (znak){
case '(': symbol.SymbNm = LewyNawSm;
break;
case ')': symbol.SymbNm = PrawyNawSm;
break;
case '+': symbol.SymbNm = PlusSm;
break;
case '-': symbol.SymbNm = MinusSm;
break;
case '*': symbol.SymbNm = RazySm;
break;
case '/': symbol.SymbNm = DzielSm;
break;
case '\0':
symbol.SymbNm = PustySm;
9
Podstawy programowania. Wykład 12  rekurencja
Małgorzata Nalbach-Moszyńska
break;
default: printf("Nieznany znak %c \n", znak);
}
}
}
double skladnik();
double czynnik();
double wyrazenie(){
double wart;
wart = skladnik();
if (symbol.SymbNm == PlusSm)
{
scan(); /* zjadam + */
wart += wyrazenie();
}
else
if (symbol.SymbNm == MinusSm)
{
scan();
wart -= wyrazenie();
}
return wart;
}
double skladnik(){
double wart;
wart = czynnik();
if (symbol.SymbNm == RazySm)
{
scan();
wart *= skladnik();
}
else
if (symbol.SymbNm == DzielSm)
{
scan();
wart /= skladnik();
}
return wart;
}
double czynnik (){
double wart;
if (symbol.SymbNm == LiczbaSm){
wart = symbol.wart;
scan();
}
else
10
Podstawy programowania. Wykład 12  rekurencja
Małgorzata Nalbach-Moszyńska
if (symbol.SymbNm == LewyNawSm){
scan();
wart = wyrazenie();
if (symbol.SymbNm != PrawyNawSm){
printf("**** Spodziewany nawias
zamykajacy\n");
wart = 0;
}
else
scan();
}
return wart;
}
int main(){
int i=0;
char c;
printf( "Podaj wyrazenie ");
while ((c = getchar())!= '\n')buforek[i++] = c;
buforek[i]='\0';
printf ("Wczytano |%s|\n", buforek);
symbol.wart = 0;
scan();
printf( "= %.2f\n", wyrazenie());
return 0;
}
11