W tym samouczku nauczysz się pisać funkcje rekurencyjne w języku C na przykładzie.
Funkcja, która wywołuje samą siebie, jest znana jako funkcja rekurencyjna. Ta technika jest znana jako rekurencja.
Jak działa rekurencja?
void recurse () (… recurse ();…) int main () (… recurse ();…)
Rekurencja trwa, dopóki nie zostaną spełnione pewne warunki, aby temu zapobiec.
Aby zapobiec nieskończonej rekurencji, można użyć instrukcji if… else (lub podobnego podejścia), gdy jedna gałąź wykonuje wywołanie rekurencyjne, a inna nie.
Przykład: suma liczb naturalnych przy użyciu rekursji
#include int sum(int n); int main() ( int number, result; printf("Enter a positive integer: "); scanf("%d", &number); result = sum(number); printf("sum = %d", result); return 0; ) int sum(int n) ( if (n != 0) // sum() function calls itself return n + sum(n-1); else return n; )
Wynik
Wpisz dodatnią liczbę całkowitą: 3 suma = 6
Początkowo sum()
wywoływana jest main()
funkcja z liczbą przekazaną jako argument.
Załóżmy, że sum()
początkowo wartość n wewnątrz wynosi 3. Podczas następnego wywołania funkcji 2 jest przekazywane do sum()
funkcji. Ten proces trwa, aż n jest równe 0.
Gdy n jest równe 0, if
warunek kończy się niepowodzeniem i else
część jest wykonywana, zwracając ostatecznie sumę liczb całkowitych do main()
funkcji.
Zalety i wady rekursji
Rekursja sprawia, że program jest elegancki. Jeśli jednak wydajność ma kluczowe znaczenie, zamiast tego użyj pętli, ponieważ rekursja jest zwykle znacznie wolniejsza.
Biorąc to pod uwagę, rekurencja jest ważną koncepcją. Jest często używany w strukturze danych i algorytmach. Na przykład rekurencja jest powszechna w przypadku problemów, takich jak przechodzenie po drzewie.