Wie weit geht ausführen Rekursion in Ihrer Funktion in C ++?
https://stackoverflow.com/questions/779282
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe mit der Führung eines Freundes rekursiven Funktionen geschrieben, die mir C ++ lehrt (als erste Sprache). Allerdings verstehe ich nicht wirklich, was los ist. Er half mir (und die SO Gemeinde, als auch) eine Zusammenführung Sortierfunktion schreiben.
std::vector<int> mergeSort(std::vector<int> original)
//code here to create two vectors, farray and sarray, out of the
//original std::vector<int> original ; each is half the length,
//note: if the size % 2 != 0, sarray takes the odd int
farray = mergeSort(farray);
sarray = mergeSort(sarray);
//code here merges the two into a single, final sorted std::vector
In dieser Funktion I zuweisen:
farray = mergeSort(farray);
sarray = mergeSort(sarray);
Was genau ist hier passiert? Er fordert MergeSort mit Farray und SFeld als Parameter und ändert den Wert. rekursiv Wie weit geht MergeSort in sich selbst ausführen? Nur bis zu dem rekursiven Funktionsaufruf?
Lösung
Jedes Mal, wenn Sie eine Funktion rekursiv aufrufen, macht es effektiv eine neue Kopie der Informationen, die er braucht, und geht weiter.
Sie können ein Programm, das „unendlich“, also erneut auf, bis es aus der Ressourcen ausgeführt wird, in der Regel Raum stapeln - den Raum, in dem diese Kopien werden. Das würde so aussehen
void recur(){
recur();
}
int main(){
recur();
exit(0); /* won't ever really get here.*/
}
Offensichtlich ist dies nicht sehr nützlich, so dass Sie ein Programm schreiben wollen, die etwas Grenze, wie oft hat sie erneut auftritt. Hier ist ein wirklich einfaches Programm, das schafft das:
#include <iostream>
using namespace std;
void recurSome(int count){
cout << "RecurSome called with " << count << endl;
if (count > 0){
recurSome(count-1);
cout << "Back at " << count << endl;
}else{
cout << "Bottom." << endl;
}
return;
}
int main(){
recurSome(10);
exit(0); /* now it will get here. */
}
Wenn Sie das kompilieren und ausführen, sagen mit:
bash $ g++ -Wall -o rc recursome.cpp
bash $ ./rc
Hier finden Sie die Ergebnisse erhalten:
RecurSome called with 10
RecurSome called with 9
RecurSome called with 8
RecurSome called with 7
RecurSome called with 6
RecurSome called with 5
RecurSome called with 4
RecurSome called with 3
RecurSome called with 2
RecurSome called with 1
RecurSome called with 0
Bottom.
Back at 1
Back at 2
Back at 3
Back at 4
Back at 5
Back at 6
Back at 7
Back at 8
Back at 9
Back at 10
bash $
Sehen Sie, wie Sie es für 10 aufgerufen wird, dann 9, und so weiter, und dann, nachdem er den Boden erreicht, zeigt er es wieder für 1 kommt, dann 2, und so weiter, bis zu 10?
Die Grundregel ist, dass alle rekursive Funktion etwas haben sollte, die einen Basisfall macht, eine, die nicht nennen sich wieder. In diesem, das Basismodell ist count == 0 und in der Tat konnten wir dies als eine rekursive Definition geschrieben
recursome:
wenn c = 0: Druck Boden
wenn c> 0: Druckzähldaten und recursome (c-1)
Sie werden viele rekursive Definitionen dieser Art sehen, wie Sie in Mathe zu bewegen.
Hier ist eine etwas niftier C-Version mit besserer Leistung:
#include <stdio.h>
#include <stdlib.h>
int max = 10;
void recurSome(int count){
printf("RecurSome %*c Called with %d\n", max-count+1, ' ', count);
if (count > 0){
recurSome(count-1);
printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
}else{
printf("RecurSome %*c Bottom.\n", 2*max, ' ');
printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
}
return;
}
int main(){
recurSome(max);
exit(0); /* now it will get here. */
}
Ausgabe:
RecurSome Called with 10
RecurSome Called with 9
RecurSome Called with 8
RecurSome Called with 7
RecurSome Called with 6
RecurSome Called with 5
RecurSome Called with 4
RecurSome Called with 3
RecurSome Called with 2
RecurSome Called with 1
RecurSome Called with 0
RecurSome Bottom.
RecurSome Back at 0
RecurSome Back at 1
RecurSome Back at 2
RecurSome Back at 3
RecurSome Back at 4
RecurSome Back at 5
RecurSome Back at 6
RecurSome Back at 7
RecurSome Back at 8
RecurSome Back at 9
RecurSome Back at 10
Andere Tipps
Überprüfen Sie es im Wörterbuch heraus:
Rekursion : Nomen. siehe Rekursion
Nun, es ernst, in dem Witz über, wird die Definition der Rekursion in Bezug auf die Rekursion selbst gegeben. Das heißt Rekursion.
Ein rekursive Algorithmus ist ein Algorithmus, deren Implementierung basiert auf dem Algorithmus selbst. Der Prozess der Entwicklung von solchen Algorithmus beginnt mit dem einfachsten Fall, dessen Lösung wird entweder im Voraus bekannt oder trivially berechnet werden kann. Dann Sie den Algorithmus in Bezug auf sich selbst definieren.
Als einfaches Beispiel, um die n-te Potenz einer gegebenen ganzen Zahl Berechnung könnte ich eine Funktion power( int number, int power ) sein. Wie könnte man es umsetzen? auf viele Arten. Die einfachste ein Aufruf einer Bibliothek ist, durch eine Schleife gefolgt, oder Sie können die Funktion in Bezug auf sich selbst definieren:
int power( int number, unsigned int pow )
{
// Basic trivial case, cuts the recursion:
if ( pow == 0 ) return 1;
// Implement power in terms of itself:
return number * power( number, pow-1 );
}
int main()
{
int power = power( 2, 10 );
}
Wir haben die Funktion in Bezug auf sich selbst definiert. Sie beginnen mit dem einfachsten Fall (n ^ 0 = 1). Wenn wir nicht im einfachsten Fall sind, können Sie Ihren Algorithmus in Bezug auf sich selbst auszudrücken.
Das Programm würde in Haupt starten, indem power( 2, 10 ) aufrufen, die power( 2, 9 ) reduziert das Problem auf eine kleiner Problem und komponieren würde würde Rekursion und rufen dann die endgültige Antwort in Bezug auf das einfachere Problem.
Die actuall Rufverfolgung wäre:
power( 2, 5 )
power( 2, 4 )
power( 2, 3 )
power( 2, 2 )
power( 2, 1 )
power( 2, 0 ) // simplest case: return 1
return 2 * 1 -> 2 // obtain next solution in terms of previous
return 2 * 2 -> 4
return 2 * 4 -> 8
return 2 * 8 -> 16
return 2 * 16 -> 32
Während rekursive Algorithmen zu entwickeln, es half in der Regel mir glauben, dass ich schon den Algorithmus hatte und läuft und funktioniert nur auf die Reduktion / Zusammensetzung des neuen Ergebnisses.
Rekursion kann als praktische Anwendung des Prinzips der Induktion zu verstehen. Um zu beweisen, eine Aussage P (n) für alle n, wobei P (n) bedeutet "Die Summe der Zahlen von 1 bis n n (n + 1) / 2" müssen wir zwei Dinge beweisen:
- Basisfall: P (n) gilt für eine bestimmte ganze Zahl ist. P (1) gilt, da 1 = 1 (1 + 1) / 2.
- Induktiv Fall: Wenn P (n) wahr ist, dann P (n + 1) muss wahr sein. 1 + ... + n + (n + 1) = n (n + 1) / 2 + (n + 1) = n (n + 1) / 2 + 2 (n + 1) / 2 = (n + 1) ((n + 1) + 1) / 2, das ist die statment P (n + 1).
In ähnlicher Weise in einer rekursiven Funktion wie MergeSort müssen wir zwei Fälle behandeln:
- Basisfall: Wenn das Array ein Element hat, wird sortiert; sonst
- Recursive Fall. Split das Array in zwei kleinere Arrays, MergeSort jedem von ihnen, und sie zusammen verschmelzen
Der Schlüssel ist, dass die beiden Arrays kleinen als das Original, sonst einer von ihnen wird nie den Basisfall getroffen. Da die Arrays grob in zwei Hälften geteilt werden, wird die Tiefe der Rekursion über log2 (n) in diesem Fall.
Was der Code in der Frage geht, gibt es drei Probleme:
- Der Basisfall fehlt.
- Wiederverwenden die Variablen Farray und SFeld ist nicht unbedingt notwendig und kann verwirrend sein.
- Der Code wird sehr langsam sein, weil die Zahl von std :: Vektoren, die erstellt und zerstört werden. Die beste Schnittstelle für MergeSort nimmt zwei vector :: Iteratoren als Eingabe, ähnlich den std :: sort () Funktion.
Neue Programmierer versuchen sollten MergeSort mit Papier und Bleistift ausgeführt wird.
Für eine rekursive Funktion nicht unendlich zu sein, braucht es eine Bedingung sein, wo es ohne selbst Aufruf zurückgibt. Für einige Algorithmen ist diese Bedingung der Punkt, an dem der Anruf auf den Daten durchführt nicht mehr sinnvoll ist.
In Ihrem Fall, wenn Sie die übergebenen in Vektor gespalten und am Ende mit zwei Vektoren, die jeweils nur 1 Punkt enthalten, ist es sinnvoll MergeSort zu nennen () auf sie? Nein.
Sie können dies umgehen, indem die Größe von Farray und SFeld Inspektion und zu entscheiden, ob MergeSort () auf einem oder beide nennen, bevor sie kombiniert und die Kombination zurück.
Was passiert, wenn man hat 2 Artikel und man hat 1? Rufen Sie MergeSort () auf der Größe 2, aber nicht von der Größe 1.
Wenn ein Anruf an MergeSort () ruft nicht MergeSort () auf entweder Farray oder SFeld vor der Rückkehr wird die Rekursion Abwickeln starten.
Haben Sie einen Blick auf die Wikipedia-Seite für Mergesort für weitere Informationen darüber, was Sie‘ re versuchen zu tun.
Als Nebenbemerkung, beachten Sie, dass Sie eine Kopie jeder Vektor machst du als Parameter angegeben sind. Verwenden Sie Vektor <> const & statt.
