Wprowadzenie do funkcji rekurencyjnej w C.
Proces powtarzania elementów w podobny sposób jak poprzednio jest znany jako rekurencja. Mówi się, że funkcja jest rekurencyjna, jeśli jest wywoływana w sobie. Język programowania C. obsługuje rekurencję. Poniżej znajdują się dwa warunki, które są niezbędne do wdrożenia rekurencji w C:
- Warunek wyjścia: ten warunek pomaga funkcji określić, kiedy należy wyjść z tej funkcji. W przypadku, gdy nie określimy warunku wyjścia, kod wejdzie w nieskończoną pętlę.
- Zmiana licznika: zmiana licznika przy każdym wywołaniu tej funkcji.
W ten sposób możemy zaimplementować funkcję rekurencyjną w języku programowania C. Funkcje te są przydatne do rozwiązywania problemów matematycznych związanych z pieniędzmi, które wymagają kilkukrotnego wywołania podobnego procesu. Przykładami takich problemów są obliczanie silni szeregu generacji szeregu Fibonacciego.
Składnia:
int fun(a1)
(
If(base_condition) return val;
fun(a2);
)
Jak działa funkcja rekurencyjna w C?
Funkcje rekurencyjne są sposobem na implementację równania w języku programowania C. Wywoływana jest funkcja rekurencyjna z przekazanym do niej argumentem mówiącym, pamięć na stosie jest przydzielana zarówno zmiennym lokalnym, jak i funkcjom. Wszystkie operacje obecne w funkcji są wykonywane przy użyciu tej pamięci. Warunek wyjścia jest sprawdzany, jeśli spełnia. Gdy kompilator wykryje wywołanie innej funkcji, natychmiast przydziela nową pamięć na górze stosu, gdzie tworzona jest inna kopia tych samych zmiennych lokalnych i funkcja. Wprowadź ten sam proces trwa.
Gdy warunek podstawowy zwraca wartość true, określona wartość przekazywana jest do funkcji wywołującej. Pamięć przydzielona do tej funkcji zostaje wyczyszczona. podobnie nowa wartość jest obliczana w funkcji wywołującej, a IT powraca do funkcji super wywoływania. W ten sposób wywoływane są rekurencyjne wywołania funkcji delete, która dociera do pierwszej funkcji, a cała pamięć stosu jest czyszczona, a dane wyjściowe zwracane. Warunek podstawowy Incase lub warunek wyjścia nie jest określony w funkcji, a następnie rekurencyjne wywołania funkcji mogą prowadzić do nieskończonej pętli.
Przykład funkcji rekurencyjnej
Teraz zobaczymy przykłady funkcji rekurencyjnej w C
Kod:
#include
int fun(int n)
(
if(n==1) return 1 ; //exit or base condition which gives an idea when to exit this loop.
return n*fun(n-1); //function is called with n-1 as it's argument .
//The value returned is multiplied with the argument passed in calling function.
)
int main()(
int test=4;
int result =0;
result =fun(test);
printf("%d", result);//prints the output result.
)
Wynik:
Objaśnienie powyższego kodu
Powyższy przykład polega na znalezieniu silni liczby. Gdy główna funkcja wywołuje fun (4), najpierw sprawdzany jest warunek wyjścia (4 == 1), a następnie wywoływany jest 4 * fun (3). Ponownie sprawdzany jest warunek podstawowy (3 == 1). Podobnie, zwróci 3 * wywoływana jest funkcja fun (2) i kontynuuje się do 2 * wywoływana jest funkcja fun (1), a tam, gdzie spełnia warunek podstawowy i zwraca 1, a następnie wywoływana funkcja zwraca 2 * 1, a następnie 3 * 2 * 1 a od pierwszego połączenia zwracane są 4 * 3 * 2 * 1. Tak więc wyniki w głównej funkcji przechowują 24 i drukują to na wyjściu.
Przydział pamięci funkcji rekurencyjnej
Każde wywołanie funkcji w języku c powoduje przydzielenie pamięci na szczycie stosu. Gdy wywoływana jest funkcja rekurencyjna, pamięć jest przydzielana do niej w górnej części pamięci, która została przydzielona do funkcji wywołującej, przy czym dla każdego wywołania tej funkcji tworzona jest inna kopia zmiennych lokalnych.
Jaki jest spełniony warunek podstawowy, pamięć przydzielona do funkcji zostaje zniszczona, a wskaźnik wraca do funkcji wywołującej? proces ten powtarza się, a następnie pierwsza funkcja wywołująca i na koniec pamięć stosu jest pusta.
W powyższym przykładzie do obliczenia silni liczby poniżej znajduje się scenariusz alokacji pamięci.
Krok 1
Krok 2
Krok 3
Krok 4
Krok - 5
Krok - 6
Krok - 7
Krok - 8
Krok - 9
Rodzaje rekurencji
Istnieją dwa typy rekurencji w programowaniu C, które podano poniżej:
1. Rekurencja ogona i bez ogona
Powyższy typ rekurencji wyjaśniono poniżej:
- Rekurencja ogona
Jest to rodzaj wywołania funkcji rekurencyjnej w funkcji, która jest ostatnim działaniem, jakie należy wykonać w definicji funkcji. Oznacza, że wywołanie rekurencyjne następuje po zaimplementowaniu całej logiki w funkcji.
Korzystanie z rekurencji ogona w naszym programie w hansis zapewnia wydajność programu, a także zmniejsza użycie pamięci przez taką funkcję. Dzieje się tak dlatego, że ponieważ inna logika funkcji została zaimplementowana w pamięci przydzielonej funkcji wywołującej, można ją usunąć ze stosu i ponownie użyć.
Kod:
int fun1(n)(
printf(“the result is “);
return fun1(n-1);
)
void main()
(
fun1(4);
)
- Rekursja bez ogona
Ten typ rekurencyjnego kolażu rekurencyjnego wykonany w środku definicji funkcji. Rekursja męskich spodni została zakończona, a wartości zwrócone do funkcji wywoływania wymagają wykonania większej liczby kroków, aby nie można było wyczyścić pamięci.
Kod:
int fun1(n)(
printf(“the result is “);
return n* fun1(n-1);
)
void main()(
fun1(4);
)
2. Rekurencja bezpośrednia i pośrednia
Powyższy typ rekurencji wyjaśniono poniżej:
- Pośrednia rekurencja
Mówi się, że rekurencja pośrednia występuje, gdy dana funkcja jest wywoływana w sposób rekurencyjny jako nośnik innej funkcji.
Kod:
int fun1()(
fun2();
)
int fun2()(
fun1(); // calling the procedure recursively using another function.
)
void main()(
fun1();
)
- Rekurencja bezpośrednia
Mówi się, że rekurencja bezpośrednia ma miejsce, gdy rekurencyjne wywołanie funkcji jest wykonywane w ramach jej własnej definicji ”.
Kod:
int fun1()(
fun1();
)
void main()(
fun1();
)
Wniosek
Można łatwo stwierdzić, że funkcje rekurencyjne są najważniejsze w rozwiązywaniu problemów matematycznych, które wymagają podobnej metody, aby cała logika była powtarzana do momentu spełnienia warunku wyjścia. Wiele problemów, takich jak wieże Hanoi, przechodzenie drzew, obliczanie głębokości wykresów.
Ważne jest, aby wspomnieć o podstawowym warunku funkcji rekurencyjnej. Wymagania dotyczące pamięci i czasu są większe dla programu rekurencyjnego w porównaniu do iteracyjnych, dlatego należy go używać ostrożnie.
Polecane artykuły
To jest przewodnik po przykładzie funkcji rekurencyjnej w C. Tutaj omawiamy działanie, typy, przydział pamięci i przykłady funkcji rekurencyjnej w C. Możesz również zapoznać się z następującymi artykułami, aby dowiedzieć się więcej-
- Tablice w programowaniu C.
- Program Palindrome in C.
- Wzory w programowaniu C.
- C vs C ++
- Palindrom w JavaScript
- Przewodnik po serii Fibonacciego w JavaScript