Inne działy

 

 

Język C funkcje rekurencyjne

 

Język C ma możliwość tworzenia tzw. funkcji rekurencyjnych. Jest to funkcja, która w swojej własnej definicji (ciele) wywołuje samą siebie. Najbardziej klasycznym przykładem może tu być silnia. Napiszmy sobie zatem naszą funkcję rekurencyjną, która oblicza silnię:

int silnia (int liczba)
{
int sil;
if (liczba<0) return 0; /* wywołanie jest bezsensowne, */
/* zwracamy 0 jako kod błędu */
if (liczba==0 || liczba==1) return 1;
sil = liczba*silnia(liczba-1);
return sil;
}

 

Musimy być ostrożni przy funkcjach rekurencyjnych, gdyż łatwo za ich pomocą utworzyć funkcję, która będzie sama siebie wywoływała w nieskończoność, a co za tym idzie będzie zawieszała program. Tutaj pierwszymi instrukcjami if ustalamy “warunki stopu”, gdzie kończy się wywoływanie funkcji przez samą siebie, a następnie określamy, jak funkcja będzie wywoływać samą siebie (odjęcie jedynki od argumentu, co do którego wiemy, że jest dodatni, gwarantuje, że dojdziemy do warunku stopu w skończonej liczbie kroków).


Warto też zauważyć, że funkcje rekurencyjne czasami mogą być znacznie wolniejsze niż podejście nierekurencyjne (iteracyjne, przy użyciu pętli). Flagowym przykładem może tu być funkcja obliczająca wyrazy ciągu Fibonacciego:

 

#include <stdio.h>
unsigned count;
unsigned fib_rec(unsigned n) {
++count;
return n<2 ? n : (fib_rec(n-2) + fib_rec(n-1));
}
unsigned fib_it (unsigned n) {
unsigned a = 0, b = 0, c = 1;
++count;
if (!n) return 0;
while (--n) {
++count;
a = b;
b = c;
c = a + b;
}
return c;
}
int main(void) {
unsigned n, result;
printf("Ktory element ciagu Fibonacciego obliczyc? ");
while (scanf("%d", &n)==1) {
count = 0;
result = fib_rec(n);
printf("fib_ret(%3u) = %6u (wywolan: %5u)\n", n, result, count);
count = 0;
result = fib_it (n);
printf("fib_it (%3u) = %6u (wywolan: %5u)\n", n, result, count);
}
return 0;
}

 

W tym przypadku funkcja rekurencyjna, choć łatwiejsza w napisaniu, jest bardzo nieefektywna.

 

 

 

Zobacz nasze wszystkie kursy

WWW


HTML
HTML - Znaczniki
CSS - Tutorial
CSS - Selektory
PHP
JavaScript

XML

XSLT

Bazy danych


SQL
SQLite
MySQL
PostgreSQL

 

 

Programowanie


C
C++
C#
Java
VisualBasic
Python

Linux


Podstawy Linuxa
Bash
Linuks artykuły

Windows


Excel funkcje
Windows wskazówki
Outlook

Pozotałe działy


Programy
Rozrywka

 

 

 

This email address is being protected from spambots. You need JavaScript enabled to view it.