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 (<listaargumentow>)
{
<instrukcje>;
if ( <warunek>) rekur (<listaargumentow2>)
<instrukcje>
}
UWAGA
Trzeba bardzo dokładnie ustalić <warunek>, ż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 <stdio.h>
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.
znajdź 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 <stdio.h>
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 <stdio.h>
#include <stdlib.h>
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