Jak działa Rekurencja w C
Jestem nowy w C i czytam o rekurencji, ale jestem całkowicie zdezorientowany.
Główną częścią, w której zaczynam się mylić, jest to, jak sprawy się rozwijają, gdy warunek wyjścia jest osiągnięty. Chciałbym się dowiedzieć jak podczas rekurencji wartości zostały wypchnięte ze stosu.
Czy mógłby mi ktoś podać diagramowy obraz rekurencji?
Dzięki...5 answers
Przyjmijmy funkcję:
int MyFunc(int counter) {
// check this functions counter value from the stack (most recent push)
// if counter is 0, we've reached the terminating condition, return it
if(counter == 0) {
return counter;
}
else {
// terminating condition not reached, push (counter-1) onto stack and recurse
int valueToPrint = MyFunc(counter - 1);
// print out the value returned by the recursive call
printf("%d", valueToPrint);
// return the value that was supplied to use
// (usually done via a register I think)
return counter;
}
}
int main() {
// Push 9 onto the stack, we don't care about the return value...
MyFunc(9);
}
Wyjście to: 0123456789
Pierwszy raz przez MyFunc, liczy się 9. Nie powiodło się sprawdzanie zakończenia (nie jest to 0), więc wywołanie rekurencyjne jest wywoływane, with (counter -1), 8.
To powtarza się, zmniejszając wartość wciśniętą na stos za każdym razem, aż licznik = = 0. W tym momencie zostanie wywołana klauzula kończąca, a funkcja po prostu zwraca wartość counter( 0), zwykle w rejestrze.
Następne wywołanie stosu, używa zwracanej wartości do print (0), następnie zwraca wartość, która została do niego dostarczona podczas wywołania (1). Powtarza się:
Następne wywołanie stosu używa zwracanej wartości do print (1), następnie zwraca wartość, która została do niego dostarczona podczas wywołania (2). itd., aż dojdziesz na szczyt..
Więc, jeśli MyFunc został wywołany z 3, otrzymasz odpowiednik (ignorując adresy zwrotne itp. ze stosu):
Call MyFunc(3) Stack: [3]
Call MyFunc(2) Stack: [2,3]
Call MyFunc(1) Stack: [1,2,3]
Call MyFunc(0) Stack: [0,1,2,3]
Termination fires (top of stack == 0), return top of stack(0).
// Flow returns to:
MyFunc(1) Stack: [1,2,3]
Print returned value (0)
return current top of stack (1)
// Flow returns to:
MyFunc(2) Stack: [2,3]
Print returned value (1)
return current top of stack (2)
// Flow returns to:
MyFunc(3) Stack: [3]
Print returned value (2)
return current top of stack (3)
// and you're done...
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-04-12 07:31:04
Jak sprawy się rozluźniają po osiągnięciu warunku wyjścia?
Po pierwsze, kilka słów o rekurencji: a metoda dziel i podbijaj używany do złożonych zadań, które można stopniowo rozkładać i sprowadzać do prostych instancji początkowego zadania, aż do postaci(Base case) pozwala to na bezpośrednie obliczenia. Jest to pojęcie ściśle związane z indukcją matematyczną .
A dokładniej rekurencyjny funkcja wywołuje się bezpośrednio lub pośrednio. W funkcji rekursji bezpośredniej, foo(), wykonuje kolejne wywołanie do siebie. W rekurencji pośredniej funkcja foo() wywołuje funkcję moo(), która z kolei wywołuje funkcję foo(), aż do osiągnięcia przypadku podstawowego, a następnie końcowy wynik jest gromadzony w dokładnym odwrotnym porządku początkowego wywołania funkcji rekurencyjnej.
Przykład:
n , oznaczane n!, jest iloczynem dodatnich liczb całkowitych od 1 do n . Czynnik można formalnie zdefiniować jako:
factorial(0)=1, (Base case)
czynnik (n) = n * czynnik(n-1) , dla n > 0. (wywołanie rekurencyjne)
Rekurencja pojawia się w tej definicji tak, jak definiujemy factorial (n) w kategoriach factorial(n-1).
Każda funkcja rekurencyjna powinna mieć warunek zakończenia , aby zakończyć rekurencję. W tym przykładzie, gdy n = 0 , rekurencja zatrzymuje się. Powyższa funkcja wyrażona w C wynosi:
int fact(int n){
if(n == 0){
return 1;
}
return (n * fact(n-1));
}
Ten przykład jest przykładem rekurencji bezpośredniej.
Jak to jest realizowane? na poziomie oprogramowania jego implementacja nie różni się od implementacji innych funkcji(procedur). Gdy zrozumiesz, że każda instancja wywołania procedury jest różna od innych, fakt, że sama funkcja rekurencyjna wywołuje nie czyni żadnego dużego różnica.
Każda aktywna procedura utrzymuje rekord aktywacji, który jest przechowywany na stosie. Rekord aktywacji składa się z argumentów , return address (of the caller), and local variables.
Rekord aktywacji pojawia się po wywołaniu procedury i znika po jej zakończeniu, a wynik jest zwracany do wywołującego. Zatem dla każdej procedury, która nie jest zakończony, zapisuje się rekord aktywacyjny zawierający stan tej procedury . Liczba rekordów aktywacji, a tym samym ilość przestrzeni stosu wymaganej do uruchomienia programu, zależy od głębokości rekurencji.
Czy mógłby mi ktoś podać diagramatyczny obraz rekurencji?
Następny rysunek pokazuje zapis aktywacji dla (3):
Jak widać z rysunku, każde wezwanie do factorial tworzy rekord aktywacji do momentu osiągnięcia podstawowego przypadku i od tego momentu gromadzimy wynik w postaci produktu.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-09-17 15:57:11
W C rekurencja jest jak zwykłe wywołania funkcji.
- Gdy funkcja jest wywoływana, argumenty, adres zwrotny i wskaźnik ramki (zapomniałem o kolejności) są popychane na stos.
- w wywołanej funkcji najpierw przestrzeń dla zmiennych lokalnych jest "wypychana" na stos.
- Jeśli funkcja zwróci coś, umieść to w określonym rejestrze (zależy od architektury, AFAIK)
- Cofnij Krok 2.
- Cofnij Krok 1.
Tak więc, z rekurencją kroków 1 i 2 są wykonywane kilka razy, następnie ewentualnie 3 (może tylko raz) i wreszcie 4 i 5 są wykonywane (tyle razy, ile razy 1 i 2).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-04-12 07:24:55
Alternatywną odpowiedzią jest to, że w ogóle nie wiesz. C jako język nie ma żadnego stosu sterty. Kompilator używa lokalizacji pamięci zwanej stosem do przechowywania informacji o przepływie sterowania, takich jak ramki stosu, adresy zwrotne i rejestry, ale w C nie ma nic zakazującego kompilatorowi przechowywania tych informacji gdzie indziej. Pod względem praktycznym poprzednie odpowiedzi są poprawne. Tak dzisiaj działają Kompilatory C.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-04-12 08:39:43
Na to pytanie udzielono szerokiej odpowiedzi. Proszę pozwolić mi włączyć dodatkową odpowiedź przy użyciu bardziej Pedagogicznego podejścia.
Można traktować rekurencję funkcji jako stosbąbelków z dwoma etapami rozróżniania: etap popychania i etap pękania.
A) PUSHING STAGE (lub" Pushing the stack", jak to nazywa OP)
0) początek Bubble #0 jest główną funkcją. Jest wysadzony tą informacją:
- Local zmienne.
- wywołanie do następnego bańki #1 (pierwsze wywołanie rekurencyjne function, MYFUNC).
1) Bańka #1 jest wysadzana na swojej turze tą informacją:
- parametry z poprzedniej bańki #0.
- zmienne lokalne w razie potrzeby.
- adres zwrotny.
- zakończenie sprawdzania z zwracaną wartością (np.: if (counter == 0) {return 1}).
- połączenie do następnej bańki # 2.
Pamiętaj, że to bańka, podobnie jak pozostałe bańki, jest funkcją rekurencyjną MYFUNC.
2) Bubble # 2 jest wysadzany tymi samymi informacjami co Bubble #1, pobierając z niego niezbędne dane wejściowe (parametry). Po tym punkcie możesz układać tyle baniek, ile chcesz, pompując INFORMACJE Zgodnie z wymienionymi elementami w Bubble #1.
I) Więc masz tyle pęcherzyków, ile chcesz: bańka #3, Bańka # 4..., Bubble #i . Ostatnia bańka ma gwóźdź w czeku kończącym. Bądź świadomy!
B) Faza pękania (lub "Popping the stack", jak to nazywa OP)
Ten etap ma miejsce, gdy osiągniesz pozytywną kontrolę zakończenia i pęknie ostatnia bańka zawierająca gwóźdź.
Powiedzmy, że ten etap dzieje się w bańce # 3. Pozytywna Kontrola zakończenia zostaje osiągnięta i Bańka # 3 zostaje rozerwana. Następnie gwóźdź z tej bańki zostaje wyzwolony. Ten gwóźdź spada na pod bańką #2 i rozerwać go. Po tym zdarzeniu gwóźdź podąża za upadkiem, aż pęknie bańka #1. To samo dzieje się z Bubble #0. Ważne jest, aby zauważyć, że gwóźdź podąża za zwracającym adresem w bańce, którą w tej chwili pęka: adres mówi gwóźdźowi, w którym kierunku należy podążać podczas upadku.
Pod koniec tego procesu odpowiedź jest uzyskiwana i dostarczana do głównej funkcji (lub bańki #0, która oczywiście nie jest pęknięta).
C) graficznie (jak OP)
To jest graficzne Wyjaśnienie. Ewoluuje od dołu, Bańka # 0 do góry, Bubble # 3.
/*Bubble #3 (MYFUNC recursive function): Parameters from Bubble #2,
local variables, returning address, terminating check (NAIL),
call (not used here, as terminating check is positive).*/
Pushing up to the bubble above ↑ ----------------------------------------------------- Nail falls to Bubble #2
/*Bubble #2 (MYFUNC recursive function): Parameters from Bubble #1,
local variables, returning address, terminating check (not used),
call to Bubble #3.*/
Pushing up to the bubble above ↑ ----------------------------------------------------- Nail falls to Bubble #1
/*Bubble #1 (MYFUNC recursive function): Parameters from Bubble #0,
local variables, returning address, terminating check (not used),
call to Bubble #2.*/
Pushing up to the bubble above ↑ ----------------------------------------------------- Nail falls to Bubble #0
/*Bubble #0 (MAIN function): local variables, the first call to Bubble #1.*/
Mam nadzieję, że takie podejście komuś pomoże. Daj mi znać, jeśli potrzebne są jakieś wyjaśnienia.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-03-31 01:53:18