Menu

Rekursja w C ++

recursion c

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Poznaj wszystko o rekurencji w C ++ z klasycznymi przykładami.

W naszym poprzednim samouczku dowiedzieliśmy się więcej o funkcjach w C ++.

Oprócz wykorzystania funkcji do dzielenia kodu na podjednostki i upraszczania kodu i jego czytelności, funkcje są przydatne w różnych innych aplikacjach, w tym do rozwiązywania problemów w czasie rzeczywistym, obliczeniach matematycznych i statystycznych.

Tworząc bardziej złożone aplikacje w C ++, napotykamy wiele wymagań, dlatego musimy zastosować kilka specjalnych koncepcji C ++. Rekursja jest jedną z takich koncepcji.

=> Odwiedź tutaj, aby zapoznać się z pełną listą samouczków języka C ++.

RECURSION W C ++

W tym samouczku dowiemy się więcej o rekurencji, gdzie i dlaczego jest używana wraz z kilkoma klasycznymi przykładami C ++, które implementują rekursję.

Czego się nauczysz:

Co to jest rekursja?

Rekursja to proces, w którym funkcja wywołuje samą siebie. Funkcja, która implementuje rekursję lub wywołuje samą siebie, nazywana jest funkcją rekurencyjną. W rekurencji funkcja rekurencyjna wywołuje siebie w kółko i działa do momentu spełnienia warunku końcowego.

Poniższy obraz przedstawia, jak działa rekurencja:

Działanie rekursji

Jak widać na powyższym diagramie, główna funkcja wywołuje funkcję funct (). Funkcja funct () z kolei wywołuje siebie w swojej definicji. Tak działa rekurencja. Ten proces wywoływania samej funkcji będzie kontynuowany, dopóki nie podamy warunku kończącego, który spowoduje jego zakończenie.

pl sql wywiad pytanie i odpowiedź

Zwykle zapewniamy gałąź kodu podczas implementacji rekurencji, tak aby zapewnić jeden warunek, który wyzwoli rekursję, a drugi, aby wykonać normalne wykonanie.

Podstawowy warunek rekursji

Kiedy przeprowadzana jest rekursja, dostarczane jest rozwiązanie przypadku podstawowego lub przypadku kończącego, a rozwiązania większych problemów są budowane w oparciu o rozwiązania mniejszych problemów.

Rozważmy klasyczny przykład rekurencji, notację czynnikową.

Wiemy, że matematycznie silnia liczby n to:

n! = nxn-1x… .x0!
biorąc pod uwagę, że 0! = 1;

Więc silnia dla n = 3 będzie wynosić 3! = 3 × 2!

3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6

Więc programowo możemy wyrazić to obliczenie w następujący sposób:

int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }

Tak więc, jak pokazano powyżej, przedstawiliśmy powyższe obliczenie silni w rekurencyjnym wywołaniu funkcji. Widzimy, że jeśli liczba n jest mniejsza lub równa 1, zwracamy 1 zamiast rekurencyjnego wywołania. Nazywa się to podstawowym warunkiem / przypadkiem dla silni, który umożliwia zatrzymanie rekurencji.

Stąd warunek podstawowy zasadniczo decyduje o tym, ile razy funkcja rekurencyjna powinna wywoływać samą siebie. Oznacza to, że możemy bardzo dobrze obliczyć silnię większej liczby, wyrażając ją za pomocą mniejszych liczb, aż do osiągnięcia klasy bazowej.

Podany poniżej jest doskonałym przykładem do obliczenia silni liczby:

#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout<

Wynik:

Wpisz liczbę, dla której ma zostać obliczona silnia: 10
10! = 3628800

W powyższym przykładzie implementujemy rekursję. Bierzemy liczbę, której silnię należy znaleźć ze standardowego wejścia, a następnie przekazujemy ją do funkcji silni.

W funkcji silni daliśmy warunek bazowy jako (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.

Alokacja pamięci dla wywołania rekurencyjnego

Wiemy, że gdy wykonywane jest wywołanie funkcji, stan funkcji wywołującej jest przechowywany na stosie, a po zakończeniu wywołania funkcji ten stan jest przywracany, aby program mógł kontynuować wykonywanie.

jak stworzyć fałszywą wiadomość e-mail

Kiedy wykonywane jest wywołanie funkcji rekurencyjnej, stan lub pamięć dla wywoływanej funkcji jest przydzielana na wierzchu stanu funkcji wywołującej i dla każdego wywołania funkcji rekurencyjnej tworzona jest inna kopia zmiennych lokalnych.

Po osiągnięciu warunku podstawowego funkcja powraca do funkcji wywołującej, a pamięć zostaje cofnięta i proces jest kontynuowany.

Przepełnienie stosu w rekursji

Gdy rekurencja trwa przez nieograniczony czas, może spowodować przepełnienie stosu.

Kiedy rekurencja może trwać w ten sposób? Jedna sytuacja ma miejsce, gdy nie określamy warunku podstawowego. Inna sytuacja ma miejsce, gdy warunek podstawowy nie jest osiągnięty podczas wykonywania programu.

Na przykład,modyfikujemy powyższy program silni i zmieniamy jego warunek bazowy.

int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }

W powyższym kodzie zmieniliśmy warunek podstawowy na (n == 1000). Teraz, jeśli podamy liczbę n = 10, możemy wywnioskować, że warunek podstawowy nigdy nie osiągnie. W ten sposób w pewnym momencie pamięć na stosie zostanie wyczerpana, powodując przepełnienie stosu.

Dlatego projektując programy rekurencyjne, musimy uważać na dostarczany przez nas warunek bazowy.

Rekursja bezpośrednia kontra pośrednia

Jak dotąd w rekurencji widzieliśmy wywołanie samej funkcji. To jest rekurencja bezpośrednia.

Istnieje inny typ rekursji, tj. Rekursja pośrednia. W tym przypadku funkcja wywołuje inną funkcję, a następnie ta funkcja wywołuje funkcję wywołującą. Jeśli f1 i f2 to dwie funkcje. Następnie f1 wywołuje z kolei f2 i f2, z kolei wywołuje f1. To jest rekursja pośrednia.

L zrewidujmy nasz program silni, aby zademonstrować rekursję bezpośrednią.

#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout<

Wynik:

Podaj liczbę, dla której ma zostać obliczona silnia: 5
5! = 120

W powyższym przykładzie pokazaliśmy rekursję pośrednią. Główna funkcja wywołuje factorial_a. Silnia_a wywołuje silnię_b. Z kolei factorial_b wywołuje factorial_a. Widzimy, że wyjście programu nie ma wpływu.

Rekursja ogonowana i nieogoniona

Ogonowa funkcja rekurencyjna to funkcja rekurencyjna, w której wykonywane jest ostatnie wywołanie funkcji.

Na przykładrozważmy następującą funkcję.

void display(int n){ if(n<=1) return; cout<<” ”<

W powyższym przykładzie wyświetlacz jest ogonową funkcją rekurencyjną, czyli ostatnim wywołaniem funkcji.

Funkcje ogonione są uważane za lepsze niż funkcje rekurencyjne nieogonione, ponieważ mogą być optymalizowane przez kompilator. Powodem jest to, że ponieważ rekurencyjne wywołanie ogonowe jest ostatnią instrukcją w funkcji, nie ma kodu do wykonania po tym wywołaniu.

W rezultacie zapisywanie bieżącej ramki stosu dla funkcji nie jest wymagane.

Plusy / minusy rekurencji w porównaniu z programowaniem iteracyjnym

Programy rekurencyjne zapewniają zwarty i czysty kod. Program rekurencyjny to prosty sposób pisania programów. Istnieją pewne nieodłączne problemy, takie jak silnia, ciąg Fibonacciego, wieże Hanoi, przechodzenie po drzewach itp., Które wymagają rekursji do rozwiązania.

Innymi słowy, są skutecznie rozwiązywane za pomocą rekursji. Można je również rozwiązać za pomocą programowania iteracyjnego przy użyciu stosów lub innych struktur danych, ale są szanse, że ich implementacja stanie się bardziej złożona.

Możliwości rozwiązywania problemów w programowaniu rekurencyjnym i iteracyjnym są takie same. Jednak programy rekurencyjne zajmują więcej miejsca w pamięci, ponieważ wszystkie wywołania funkcji muszą być przechowywane na stosie, dopóki przypadek podstawowy nie zostanie dopasowany.

Funkcje rekurencyjne mają również narzut czasowy z powodu zbyt wielu wywołań funkcji i zwracanych wartości.

Przykłady rekursji

Następnie zaimplementujemy kilka przykładów programowania rekurencyjnego.

Seria Fibonacciego

Szereg Fibonacciego to ciąg podany jako

0 1 1 2 3 5 8 13 ……

Jak pokazano powyżej, pierwsze dwie liczby szeregu Fibonacciego to 0 i 1. Następna liczba w sekwencji jest sumą dwóch poprzednich liczb.

Zaimplementujmy tę serię za pomocą rekursji.

#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '<

Wynik:

Podaj liczbę elementów dla szeregu Fibonacciego: 10
Seria Fibonacciego dla 10 liczb: 0 1 1 2 3 5 8 13 21 34

W tym przykładzie użyliśmy wywołania rekurencyjnego do wygenerowania sekwencji Fibonacciego. Widzimy, że pierwsze dwie liczby będące stałymi są drukowane bezpośrednio, a dla następnych liczb w sekwencji używamy funkcji rekurencyjnej.

Palindrom

Liczba palindromowa to liczba, która czytana w odwrotnym kierunku jest taka sama, jak czytana w kierunku od lewej do prawej.

Na przykład, liczba 121 podczas czytania od lewej do prawej i od prawej do lewej brzmi to samo, tj. 121. Stąd 121 jest palindromem.

Liczba 291, czytana od prawej do lewej, czyli w odwrotnej kolejności, brzmi jak 192. Zatem 291 nie jest palindromem.

#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '<

Wynik:

Wpisz numer, aby sprawdzić palindrom: 6556
Numer 6556 to palindrom

Zrzut ekranu dla tego samego znajduje się poniżej.

Rekursja - Palindrom

W powyższym programie odczytujemy numer wejścia ze standardowego wejścia. Następnie przekazujemy tę liczbę do funkcji rekurencyjnej, aby odwrócić cyfry liczby. Jeśli odwrócone cyfry i wprowadzona liczba są takie same, to liczba jest palindromem.

Wniosek

Na tym zakończyliśmy rekurencję. W tym samouczku szczegółowo omówiliśmy programowanie rekurencyjne, funkcję rekurencyjną, jej zalety / wady oraz różne przykłady.

to klucz bezpieczeństwa sieci taki sam jak hasło wifi

Oprócz tych przykładów rekursja jest również używana w rozwiązywaniu niektórych standardowych problemów, takich jak przechodzenie (inorder / preorder / postorder), wieże Hanoi, przechodzenie BFS itp.

=> Odwiedź tutaj, aby nauczyć się C ++ od podstaw.

rekomendowane lektury

^