Was ist Rekursion und wann sollte ich es verwenden?

stimmen
121

Eines der Themen, die regelmäßig auf Mailinglisten und Online-Diskussionen zu kommen scheint, ist die Sache (oder deren Fehlen) von einem Computer Science Degree tun. Ein Argument, das immer wieder für die negative Partei zu kommen scheint, ist, dass sie für eine bestimmte Anzahl von Jahren haben Codierung und sie haben nie Rekursion verwendet.

Die Frage ist also:

  1. Was ist Rekursion?
  2. Wann würde ich Rekursion verwenden?
  3. Warum die Leute nicht Rekursion verwenden?
Veröffentlicht am 06/08/2008 um 03:29
quelle vom benutzer
In anderen Sprachen...                            


40 antworten

stimmen
86

Es gibt eine Reihe von guten Erklärungen der Rekursion in diesem Thread, diese Antwort ist , warum sollten Sie es nicht in den meisten Sprachen verwenden. * In den meisten großen imperativen Sprache Implementierungen (dh jede größere Implementierung von C, C ++, Basic, Python , Ruby, Java und C #) Iteration ist erheblich vorzuziehen Rekursion.

Um zu sehen, warum, zu Fuß durch die Schritte, dass die oben genannten Sprachen verwenden, eine Funktion aufzurufen:

  1. Platz ist auf geschnitzt dem Stapel für die Argumente der Funktion und lokale Variablen
  2. die Argumente der Funktion werden in diesen neuen Raum kopiert
  3. springt die Steuerung zu der Funktion
  4. der Code der Funktion läuft
  5. das Ergebnis der Funktion wird in einen Rückgabewert kopiert
  6. der Stapel in seine vorherige Position zurückgespult
  7. springt die Steuerung zurück, wo die Funktion aufgerufen wurde

Doing all diese Schritte braucht Zeit, in der Regel ein wenig mehr , als es durch eine Schleife zu durchlaufen nimmt. Allerdings ist das eigentliche Problem in Schritt # 1. Wenn viele Programme starten, weisen sie einen einzigen Teil des Speichers für ihre Stapel, und wenn sie aus diesem Speicher laufen (oft, aber nicht immer wegen Rekursion), stürzt das Programm aufgrund eines Stapelüberlauf .

Also in dieser Sprache ist Rekursion langsamer und es macht Dich anfällig für Absturz. Es gibt noch einige Argumente dafür allerdings verwenden. Im Allgemeinen geschriebener Code ist rekursiv kürzer und ein bisschen mehr elegant, wenn Sie wissen, wie es zu lesen.

Es ist eine Technik , die Sprache Implementierer genannt verwenden kann Endrekursion Optimierung , die einige Klassen von Stack - Überlauf beseitigen. Setzen Sie den Punkt: wenn eine Rückkehr Ausdruck der Funktion einfach das Ergebnis eines Funktionsaufrufs ist, dann müssen Sie keine neue Ebene auf den Stapel hinzufügen möchten , können Sie die aktuelle eine für die Funktion Wiederverwendung aufgerufen wird. Bedauerlicherweise wenige imperative Sprache-Implementierungen haben Tail-Call - Optimierung eingebaut.

* Ich liebe Rekursion. Mein Liebling statische Sprache Schleifen gar nicht verwenden, Rekursion ist der einzige Weg , etwas wiederholt zu tun. Ich glaube einfach nicht , dass Rekursion ist in der Regel eine gute Idee , in Sprachen , die nicht für sie abgestimmt sind.

** Durch die Art und Weise Mario, der typische Name für Ihre ArrangeString Funktion ist „join“, und ich würde überrascht sein, wenn die Sprache Ihrer Wahl nicht bereits eine Implementierung davon hat.

Beantwortet am 06/08/2008 um 06:09
quelle vom benutzer

stimmen
63

Einfaches Englisch Beispiel für Rekursion.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.
Beantwortet am 04/05/2010 um 17:38
quelle vom benutzer

stimmen
49

Im einfachsten Informatik Sinne ist Rekursion eine Funktion, die sich selbst aufruft. Sagen Sie bitte eine verknüpfte Listenstruktur haben:

struct Node {
    Node* next;
};

Und Sie wollen herausfinden, wie lange eine verkettete Liste ist, dass Sie dies mit Rekursion tun können:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Dies könnte natürlich mit einem for-Schleife als auch getan werden, aber ist nützlich als eine Darstellung des Konzepts)

Beantwortet am 04/05/2010 um 12:25
quelle vom benutzer

stimmen
46

Jedes Mal, wenn eine Funktion sich selbst aufruft, eine Schleife zu schaffen, dann ist das Rekursion. Wie bei allem gibt es gute und schlechte Verwendungen Verwendungen für Rekursion.

Das einfachste Beispiel ist Endrekursion wo die letzte Zeile der Funktion eine Verbindung zu sich selbst ist:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

Dies ist jedoch ein lahmes, fast sinnlos Beispiel, weil es leicht durch effizientere Iteration ersetzt werden kann. Immerhin leidet Rekursion von oben Funktionsaufruf, der in dem obigen Beispiel erheblichen Vergleich innerhalb der Funktion selbst für den Betrieb sein könnte.

So ist der ganze Grund Rekursion zu tun , anstatt Iteration sollten auch die Vorteile des nehmen Call - Stack einige clevere Sachen zu tun. Zum Beispiel, wenn Sie eine Funktion mehrmals mit unterschiedlichen Parametern innerhalb derselben Schleife aufrufen , dann ist das eine Art und Weise zu erreichen Verzweigung . Ein klassisches Beispiel ist das Sierpinski Dreieck .

Geben Sie hier image description

Sie können jene, die man sehr einfach mit Rekursion, wo die Call-Stack Zweige in 3 Richtungen ziehen:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

Wenn Sie die gleiche Sache mit Iteration zu tun versuchen, ich glaube, Sie finden es viel mehr Code nimmt zu erreichen.

Andere häufige Anwendungsfälle könnten gehören durchqueren Hierarchien, zB Website-Crawler, Verzeichnisvergleiche etc.

Fazit

In der Praxis macht Rekursion am sinnvollsten, wenn Sie iterative Verzweigung benötigen.

Beantwortet am 04/05/2010 um 14:33
quelle vom benutzer

stimmen
28

Rekursion ist ein Verfahren der Probleme auf der Grundlage der Teile und Herrsche Geisteshaltung lösen. Die Grundidee ist, dass Sie das ursprüngliche Problem nehmen und teilen sie in kleinere (leichter gelöst) Instanzen von sich selbst, lösen diese kleineren Instanzen (in der Regel durch den gleichen Algorithmus wieder verwendet wird) und sie dann in die endgültige Lösung wieder zusammenzusetzen.

Das bekannteste Beispiel ist eine Routine, die Fakultät von n zu erzeugen. Die Fakultät von n wird durch die Multiplikation aller Zahlen zwischen 1 und n berechnet. Eine iterative Lösung in C # sieht wie folgt aus:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

Es gibt nichts überraschend über die iterative Lösung und es soll Sinn für jedermann vertraut mit C # machen.

Die rekursive Lösung durch Erkennen, dass das n-te Factorial ist n * Fact (n-1) gefunden wird. Oder um es anders auszudrücken, wenn Sie wissen, was eine bestimmte Factorial Zahl ist, können Sie die nächsten berechnen. Hier ist die rekursive Lösung in C #:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

Der erste Teil dieser Funktion ist bekannt als ein Basisfall (oder manchmal Schutz - Klausel) und ist das, was immer der Algorithmus ausgeführt wird verhindert. Es gibt nur den Wert 1 , wenn die Funktion mit einem Wert von 1 oder weniger genannt wird. Der zweite Teil ist interessanter und ist bekannt als der rekursive Schritt . Hier nennen wir die gleiche Methode mit einem leicht modifizierten Parameter (wir oder vermindern, um 1) und dann das Ergebnis mit unserer Kopie von n multiplizieren.

Als erstes begegnet kann diese Art von verwirrend sein, so ist es lehrreich ist zu untersuchen, wie es bei der Ausführung funktioniert. Stellen Sie sich vor, dass wir FactRec nennen (5). Wir betreten die Routine, werden nicht von dem Basisfall abgeholt und so haben wir am Ende so zusammen:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

Wenn wir die Methode mit dem Parameter erneut eingeben 4 wir wieder nicht durch die Schutzklausel gestoppt und so landen wir an:

// In FactRec(4)
return 4 * FactRec(3);

Wenn wir diesen Rückgabewert in den Rückgabewert ersetzen oben erhalten wir

// In FactRec(5)
return 5 * (4 * FactRec(3));

Dies sollten Sie geben einen Hinweis darauf, wie die endgültige Lösung bei so angekommen ist, werden wir schnell verfolgen und jeden Schritt auf dem Weg zeigen nach unten:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

Die endgültige Substitution geschieht, wenn der Basisfall ausgelöst wird. An dieser Stelle haben wir eine einfache Formel algrebraic zu lösen, die in erster Linie direkt auf die Definition von Faktorielle entspricht.

Es ist lehrreich zu beachten, dass jeder Anruf in die Methode führt entweder zu einem Basisfall oder einen Aufruf der gleichen Methode ausgelöst wird, in dem die Parameter näher an einen Basisfall sind (oft einen rekursiven Aufruf genannt). Ist dies nicht der Fall ist, dann wird das Verfahren für immer laufen.

Beantwortet am 06/08/2008 um 03:54
quelle vom benutzer

stimmen
12

Rekursion ist ein Problem mit einer Funktion zu lösen, die sich selbst aufruft. Ein gutes Beispiel hierfür ist eine Fakultätsfunktion. Factorial ist ein mathematisches Problem, wo die Fakultät von 5, beispielsweise 5 * 4 * 3 * 2 * 1. Diese Funktion löst dieses Problem in C # für positive ganze Zahlen (nicht getestet - es kann ein Fehler sein).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}
Beantwortet am 04/05/2010 um 12:29
quelle vom benutzer

stimmen
9

Betrachten wir ein altes, bekanntes Problem :

In der Mathematik, der größte gemeinsame Teiler (GCD) , ... von zwei oder mehr Nicht-Null - Zahlen, ist die größte positive ganze Zahl, die die Zahl ohne Rest trennt.

Die Definition von GCD ist überraschend einfach:

gcd Definition

wobei mod die ist Modulo - Operator (das heißt, der Rest nach der Division der ganzen Zahl).

In Englisch, sagt diese Definition der größte gemeinsame Teiler von beliebiger Anzahl und null ist diese Zahl, und der größte gemeinsame Teiler von zwei Zahlen m und n der größte gemeinsame Teiler von n und der Rest nach dem Dividieren m von n .

Wenn Sie möchten wissen , warum dies funktioniert, finden Sie in der Wikipedia - Artikel auf dem euklidischen Algorithmus .

Lassen Sie uns berechnen gcd (10, 8) als ein Beispiel. Jeder Schritt ist gleich der, kurz bevor es:

  1. gcd (10, 8)
  2. gcd (10, 10 mod 8)
  3. gcd (8, 2)
  4. gcd (8, 8 mod 2)
  5. gcd (2, 0),
  6. 2

Im ersten Schritt, tut 8 nicht gleich Null, so dass der zweite Teil der Definition gilt. 10 mod 8 = 2, da 8 geht in 10 einmal mit einem Rest von 2. In Schritt 3 gilt der zweiten Teil erneut, aber diesmal 8 mod 2 = 0, da 2 dividieren 8 ohne Rest. In Schritt 5 ist das zweite Argument 0, so ist die Antwort 2.

Haben Sie bemerkt , dass gcd auf beiden erscheint die linken und rechten Seite des Gleichheitszeichens? Ein Mathematiker würde sagen , diese Definition ist rekursiv , weil der Ausdruck Sie definieren wiederholt innerhalb seiner Definition.

Rekursive Definitionen sind in der Regel elegant sein. Zum Beispiel ist eine rekursive Definition für die Summe aus einer Liste

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

wobei headdas erste Element in einer Liste aus, und tailist der Rest der Liste. Beachten Sie, dass sumam Ende innerhalb seiner Definition wiederkehrt.

Vielleicht würden Sie den maximalen Wert in einer Liste bevorzugen statt:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

Sie könnten rekursiv Multiplikation von nicht-negativen ganzen Zahlen definieren es in eine Reihe von Ergänzungen zu machen:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

Wenn das Bit über Multiplikation in eine Reihe von Ergänzungen Umwandlung macht keinen Sinn, versuchen Sie ein paar einfachen Beispiele erweitern, um zu sehen, wie es funktioniert.

Mergesort eine schöne rekursive Definition hat:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Rekursive Definitionen sind überall , wenn Sie wissen , was zu suchen. Beachten Sie, wie alle diese Definitionen sehr einfache Basis Fällen, zum Beispiel , ggT (m, 0) = m. Die rekursive Fällen beschneiden das Problem auf die einfachen Antworten unten zu erhalten.

Mit diesem Verständnis können Sie nun die anderen Algorithmen in schätzen Wikipedia Artikel über Rekursion !

Beantwortet am 04/05/2010 um 14:58
quelle vom benutzer

stimmen
9

Rekursion bezieht sich auf ein Verfahren, das durch Lösen eine kleinere Version des Problems ein Problem löst und dann das Ergebnis mit und eine andere Berechnung, die Antwort auf das ursprüngliche Problem zu formulieren. Oft in dem Prozess der kleinere Version der Lösung wird das Verfahren eine noch kleinere Version des Problems lösen, und so weiter, bis er einen „Basisfall“ erreicht, die trivial zu lösen.

Zum Beispiel kann eine faktorielle für die Zahl zu berechnen X, kann man es als repräsentieren X times the factorial of X-1. Somit werden die Verfahren „rekursiv“ zu finden die Fakultät X-1, und dann multipliziert , was es bekam durch Xeine endgültige Antwort zu geben. Natürlich die Fakultät zu finden X-1, es wird zuerst die Fakultät berechnen X-2, und so weiter. Der Basisfall wäre , wenn X0 oder 1 ist , in welchem Fall er weiß zurückkehren 1da 0! = 1! = 1.

Beantwortet am 04/05/2010 um 12:26
quelle vom benutzer

stimmen
9
  1. Eine Funktion, die sich selbst aufruft
  2. Wann kann eine Funktion (leicht) sein, in einen einfachen Vorgang zerlegt und die gleiche Funktion auf etwas kleineren Teil des Problems. Ich würde sagen, eher, dass dies es für Rekursion ein guter Kandidat macht.
  3. Tun sie!

Das bekannteste Beispiel ist die Fakultäts, die wie folgt aussieht:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

Im Allgemeinen ist die Rekursion nicht unbedingt schnell (Funktionsaufruf Overhead dazu neigt, hoch zu sein, weil rekursiven Funktionen, klein sein neigen, siehe oben) und kann von einigen Problemen leiden (Stack-Überlauf anyone?). Manche sagen, sie neigen dazu, hart zu sein ‚Recht‘ in nicht-trivialen Fällen zu bekommen, aber ich weiß nicht wirklich in dem kaufen. In einigen Situationen macht Rekursion am meisten Sinn und ist die eleganteste und klare Art und Weise um eine bestimmte Funktion zu schreiben. Es sollte beachtet werden, dass einige Sprachen rekursive Lösungen bevorzugen und optimieren sie viel mehr (LISP in den Sinn kommt).

Beantwortet am 06/08/2008 um 03:35
quelle vom benutzer

stimmen
7

Eine rekursive Funktion ist eine, die sich selbst aufruft. Der häufigste Grund, den ich gefunden habe, es zu benutzen ist eine Baumstruktur durchquert. Zum Beispiel, wenn ich eine TreeView mit Checkboxen haben (man denke an die Installation eines neuen Programms „Funktionen zur Installation auswählen“ Seite), könnte ich möchte eine Schaltfläche „alle überprüfen“, die so etwas wie dieses (Pseudo-Code) sein würde:

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

So können Sie sehen, dass die checkRecursively zuerst den Knoten überprüft, die sie übergeben wird, dann nennt sich für jede dieses Knotens der Kinder.

Sie brauchen ein bisschen vorsichtig mit Rekursion sein. Wenn Sie in eine unendliche rekursive Schleife erhalten, werden Sie einen Stack-Überlauf Ausnahme bekommen :)

Ich kann nicht glauben, der Grund, warum die Menschen nicht verwenden sollten, wenn angemessen. Es ist nützlich, in einigen Fällen, und in anderen nicht.

Ich denke, dass, weil es eine interessante Technik ist, vielleicht einige Programmierer es oft am Ende mit, als sie sollten, ohne wirkliche Rechtfertigung. Dies hat Rekursion einen schlechten Ruf in einigen Kreisen gegeben.

Beantwortet am 06/08/2008 um 03:44
quelle vom benutzer

stimmen
5

Rekursion ist ein Ausdruck, die direkt oder indirekt referenziert selbst.

Betrachten wir rekursive Akronyme als ein einfaches Beispiel:

  • GNU steht für GNU nicht Unix
  • PHP steht für PHP: Hypertext Preprocessor
  • YAML steht für YAML Is not Markup - Sprache
  • WEIN steht für Wein ist kein Emulator
  • VISA steht für Visa International Service Association

Weitere Beispiele auf Wikipedia

Beantwortet am 04/05/2010 um 12:56
quelle vom benutzer

stimmen
5

Hier ist ein einfaches Beispiel: wie viele Elemente in einem Satz. (Es gibt bessere Möglichkeiten, Dinge zu zählen, aber das ist ein schönes einfaches rekursive Beispiel.)

Erstens müssen wir zwei Regeln:

  1. wenn der Satz leer ist, ist die Anzahl der Elemente in dem Satz Null (duh!).
  2. wenn der Satz nicht leer ist, ist die Zahl eins plus die Anzahl der Elemente in dem Satz nach einem Element entfernt wird.

Angenommen, Sie haben einen Satz wie folgt aus: [xxx]. Lassen Sie uns zählen, wie viele Elemente gibt.

  1. der Satz ist [xxx], die nicht leer ist, so wenden wir Regel 2 die Anzahl der Elemente ist eins plus die Anzahl der Elemente in [xx] (dh wir ein Element entfernt).
  2. der Satz ist [xx], so wenden wir die Regel 2 wieder: ein + Anzahl der Elemente in [x].
  3. der Satz ist [x], die Regel entspricht noch 2: eine + Anzahl der Elemente in [].
  4. Nun ist die Reihe ist [], die Regel entspricht 1: die Zählung Null!
  5. Nun, da wir wissen, die Antwort in Schritt 4 (0), können wir Schritt 3 (1 + 0) lösen
  6. Ebenso nun, dass wir wissen, die Antwort in Schritt 3 (1), können wir Schritt 2 (1 + 1) lösen
  7. Und schließlich jetzt, dass wir die Antwort in Schritt 2 (2) kennen, können wir Schritt 1 (1 + 2) lösen und die Anzahl der Elemente in [xxx] erhalten, die 3. Hooray ist!

Wir können dies darstellen als:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

Wenn eine rekursive Lösung anwenden, haben Sie in der Regel mindestens zwei Regeln:

  • die Basis, der einfache Fall in dem es heißt, was passiert, wenn man „verbraucht“ hat alle Ihre Daten. Dies ist in der Regel eine gewisse Variation von „wenn Sie aus Daten zu verarbeiten sind, Ihre Antwort ist X“
  • die rekursive Regel, die besagt, was passiert, wenn Sie noch Daten. Dies ist in der Regel eine Art von Regel, die sagt, dass „etwas tun, um Ihren Datensatz kleiner zu machen und Ihre Regeln auf den kleineren Datensatz erneut anwenden.“

Wenn wir die oben Pseudo-Code übersetzen, erhalten wir:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

Es gibt eine Menge mehr nützliche Beispiele (Verfahrweg einen Baum, zum Beispiel), die ich bin sicher, dass andere Menschen decken.

Beantwortet am 06/08/2008 um 04:12
quelle vom benutzer

stimmen
5

Rekursion funktioniert am besten mit dem, was Ich mag „Fraktal Probleme“ nennen, wo man mit einer großen Sache zu tun hat, die von kleineren Versionen dieser großen Sache gemacht hat, von denen jedem eine noch kleineren Version der großen Sache, und so weiter. Wenn Sie schon einmal durchlaufen müssen oder durch so etwas wie ein Baum oder verschachtelte identische Strukturen suchen, haben Sie ein Problem, dass ein guter Kandidat für die Rekursion sein könnte.

Menschen Rekursion für eine Reihe von Gründen vermeiden:

  1. Die meisten Menschen (mich eingeschlossen) schneiden ihre Programmierung Zähne auf prozedurale oder Programmierung objektorientierte als funktionale Programmierung gegenüber. Solche Menschen, der iterative Ansatz (in der Regel unter Verwendung von Schleifen) fühlt sich natürlicher.

  2. Diejenigen von uns, schneiden unsere Programmierung Zähne auf prozeduralen oder objektorientierten Programmierung haben oft gesagt worden, Rekursion zu vermeiden, weil es fehleranfällig ist.

  3. Wir oft gesagt, dass Rekursion langsam ist. Anrufen und von einer Routine zurückkehrt beinhaltet immer wieder eine Menge Stapel schieben und Knallen, die langsamer ist als Looping ist. Ich denke, einige Sprachen handhaben dies besser als andere, und diese Sprachen sind höchstwahrscheinlich nicht diejenigen, bei denen das vorherrschende Paradigma prozedurale oder objektorientiert.

  4. Für zumindest ein paar Programmiersprachen ich verwendet habe, ich erinnere mich hören Empfehlungen nicht Rekursion zu verwenden, wenn es über eine gewisse Tiefe bekommt, weil seine Stapel nicht so tief ist.

Beantwortet am 06/08/2008 um 04:12
quelle vom benutzer

stimmen
4

1.) Verfahren ist rekursiv, wenn sie sich selbst aufrufen kann; entweder direkt:

void f() {
   ... f() ... 
}

oder indirekt:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Wenn Rekursion verwenden

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) Die Leute benutzen nur Rekursion, wenn es sehr komplex ist iterativ Code zu schreiben. Zum Beispiel Baumdurchlauftechniken wie vorbestellen, Postorder kann sowohl iterativen und rekursiven gemacht werden. Aber in der Regel verwenden rekursive wir wegen seiner Einfachheit.

Beantwortet am 11/03/2014 um 10:47
quelle vom benutzer

stimmen
4

Eine rekursive Aussage ist eine, in der Sie den Prozess der Definition, was als nächstes als eine Kombination der Eingänge zu tun und was Sie bereits getan haben.

Nehmen wir zum Beispiel faktorielles:

factorial(6) = 6*5*4*3*2*1

Aber es ist einfach faktorielles zu sehen (6) auch ist:

6 * factorial(5) = 6*(5*4*3*2*1).

So im Allgemeinen:

factorial(n) = n*factorial(n-1)

Natürlich ist die heikle Sache über Rekursion, dass, wenn man die Dinge in Bezug auf definieren wollen, was Sie bereits getan haben, es einen Ort zu starten sein muss.

In diesem Beispiel machen wir nur einen Sonderfall von Fakultäts definieren (1) = 1.

Jetzt sehen wir es von unten nach oben:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Da wir factorial (1) = 1 definiert sind, erreichen wir den "Boden".

Im Allgemeinen rekursive Prozeduren bestehen aus zwei Teilen:

1) Der rekursive Teil, das einige Verfahren im Hinblick auf neue Eingänge definiert kombiniert mit dem, was du hast „bereits getan“ über das gleiche Verfahren. (dh factorial(n) = n*factorial(n-1))

2) Ein Basisteil, das dafür sorgt , dass der Prozess nicht ewig wiederholen , indem es einen Platz geben zu beginnen (dh factorial(1) = 1)

Es kann ein wenig verwirrend sein Kopf um zuerst zu bekommen, aber nur Blick auf ein Bündel von Beispielen und es sollten alle zusammen kommen. Wenn Sie ein viel tieferes Verständnis des Konzepts wollen, studieren mathematische Induktion. Beachten Sie außerdem, dass einige Sprachen für rekursive Aufrufe zu optimieren, während andere dies nicht tun. Es ist ziemlich einfach irrsinnig langsam rekursive Funktionen zu machen, wenn Sie nicht vorsichtig sind, aber es gibt auch Techniken, um sie in den meisten Fällen performant zu machen.

Hoffe das hilft...

Beantwortet am 04/05/2010 um 14:30
quelle vom benutzer

stimmen
4

Ich mag diese Definition:
In Rekursion löst eine Routine einen kleinen Teil eines Problem selbst, teilt das Problem in kleinere Stücke, und dann nennt mich jede der kleineren Stücke zu lösen.

Ich mag auch Steve McConnells Diskussion der Rekursion in Code Complete, wo er die Beispiele in der Informatik Bücher über Rekursion verwendet kritisiert.

Verwenden Sie keine Rekursion für factorials oder Fibonacci-Zahlen

Ein Problem, mit dem Computer-Wissenschaft Lehrbüchern ist, dass sie dumme Beispiele für Rekursion präsentieren. Die typischen Beispiele sind das Berechnen einer faktoriellen oder eine Fibonacci-Sequenz zu berechnen. Rekursion ist ein mächtiges Werkzeug, und es ist wirklich dumm es in einem dieser Fälle zu verwenden. Wenn ein Programmierer, der für mich gearbeitet verwendet Rekursion eine faktorielle zu berechnen, würde ich jemand anderes mieten.

Ich dachte, dies ist ein sehr interessanter Punkt war zu erhöhen und kann ein Grund sein, warum Rekursion wird oft falsch verstanden.

EDIT: Das bei Dav Antwort kein dig war - ich hatte diese Antwort nicht gesehen, als ich gepostet

Beantwortet am 04/05/2010 um 12:29
quelle vom benutzer

stimmen
3

Ein Beispiel: Eine rekursive Definition einer Treppe ist: Eine Treppe besteht aus: - ein einziger Schritt und eine Treppe (Rekursion) - oder nur ein einziger Schritt (Terminierung)

Beantwortet am 04/05/2010 um 14:34
quelle vom benutzer

stimmen
3

Nun, das ist eine ziemlich anständige Definition Sie haben. Und wikipedia hat eine gute zu Definition. Also werde ich für Sie eine andere (wahrscheinlich schlechter) Definition hinzufügen.

Wenn die Leute zu „Rekursion“ beziehen, reden sie in der Regel über eine Funktion, die sie geschrieben haben, die sich immer wieder aufruft, bis er mit seiner Arbeit fertig ist. Rekursion kann hilfreich sein, wenn Hierarchien in Datenstrukturen durchlaufen.

Beantwortet am 04/05/2010 um 12:27
quelle vom benutzer

stimmen
3

Um Rekursion auf einem gelöstes Problem: nichts tun, sind Sie fertig.
Um auf ein offenes Problem Rekursion: den nächsten Schritt tun, dann Rekursion auf den Rest.

Beantwortet am 06/08/2008 um 04:32
quelle vom benutzer

stimmen
2

Dies ist eine alte Frage, aber ich mag eine Antwort aus logistischer Sicht hinzuzufügen (dh nicht vom Algorithmus Richtigkeit Sicht oder Performance-Sicht).

Ich benutze Java für Arbeit und Java nicht verschachtelte Funktion unterstützen. Als solcher, wenn ich Rekursion tun möchte, könnte ich eine externe Funktion definieren müssen (die Bumps gegen Javas bürokratischer Herrschaft nur, weil mein Code vorhanden ist), oder ich könnte den Code ganz Refactoring haben (was ich hasse wirklich).

So vermeide ich oft Rekursion und Verwendung Stapelbetrieb statt, weil Rekursion selbst im Wesentlichen eine Stapeloperation ist.

Beantwortet am 30/08/2014 um 11:09
quelle vom benutzer

stimmen
2

Eine rekursive Funktion ist eine Funktion, die eine Verbindung zu sich selbst enthält. Eine rekursive Struktur ist eine Struktur, die eine Instanz selbst enthält. Sie können die beiden als rekursive Klasse kombinieren. Der wichtigste Teil eines rekursiven Punkt ist, dass es eine Instanz / Aufruf von selbst enthält.

Betrachten wir zwei Spiegel einander gegenüber. Wir haben die ordentlich Unendlichkeit Effekt gesehen sie machen. Jede Reflexion ist ein Beispiel für einen Spiegel, der innerhalb einer anderen Instanz eines Spiegels enthalten ist, usw. der Spiegel eine Reflexion von sich selbst enthält Rekursion ist.

Ein binärer Suchbaum ist ein gutes Beispiel zur Programmierung der Rekursion. Die Struktur ist mit jedem Knoten , die 2 Instanzen eines Knoten rekursiv. Funktionen auf einem binären Suchbaum zu arbeiten , sind auch rekursiv.

Beantwortet am 04/05/2010 um 17:46
quelle vom benutzer

stimmen
2

Im Klartext: Angenommen, Sie 3 Dinge tun können:

  1. Nehmen Sie einen Apfel
  2. Notieren Sie Zählstriche
  3. Graf Zählstriche

Sie haben eine Menge von Äpfeln vor Ihnen auf dem Tisch, und Sie wollen wissen, wie viele Äpfel sind.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

Der Prozess der das gleiche zu wiederholen, bis Sie fertig sind, wird die Rekursion genannt.

Ich hoffe, dass dies die „einfache Englisch“ Antwort ist, dass Sie suchen!

Beantwortet am 04/05/2010 um 14:09
quelle vom benutzer

stimmen
1

Die einfachste Definition von Rekursion ist „Selbstreferenz“. Eine Funktion, die auf sich selbst bezieht, dh nennt sich rekursiv ist. Die wichtigste Sache im Auge zu halten, besteht darin, dass eine rekursive Funktion einen „Basisfall“ haben muss, also einen Zustand, wenn sie wahr verursacht es nicht selbst zu nennen, und damit die Rekursion beenden. Andernfalls werden Sie unendliche Rekursion haben:

Rekursion http://cart.kolix.de/wp-content/uploads/2009/12/infinite-recursion.jpg

Beantwortet am 04/05/2010 um 17:10
quelle vom benutzer

stimmen
1

Rekursion ist, wenn Sie eine Operation haben, die selbst verwendet. Es wird wahrscheinlich einen Haltepunkt hat, sonst wäre es ewig so weitergehen.

Angenommen, Sie haben ein Wort im Wörterbuch nachschlagen möchten. Sie haben eine Operation „look-up“ zur Verfügung genannt.

Ihr Freund sagt: „Ich könnte jetzt wirklich etwas Pudding auslöffeln!“ Sie wissen nicht, was er meint, so dass man nachschlagen „Löffel“ im Wörterbuch, und es liest etwas wie folgt aus:

Löffel: Nomen - ein Utensil mit einer runden Schaufel am Ende. Löffel: Verb - mit einem Löffel auf etwas Löffel verwenden: Verb - eng kuscheln von hinten

Jetzt ist, dass man mit Englisch nicht wirklich gut sind, diese Punkte, die Sie in die richtige Richtung, aber Sie weitere Informationen benötigen. So wählen Sie „Utensil“ und „kuscheln“ für einige weitere Informationen zu suchen.

Cuddle: - Verb Utensil zum Kuscheln: Nomen - ein Werkzeug, oft ein Eßbesteck

Hallo! Sie wissen, was Kuscheln ist, und es hat nichts mit Pudding zu tun. Sie wissen auch, dass Pudding etwas, das Sie essen, so macht es nun Sinn. Ihr Freund muss will Pudding essen mit einem Löffel.

Okay, okay, das war ein sehr lahmes Beispiel, aber es zeigt (vielleicht schlecht) die beiden Hauptteile der Rekursion. 1) Es nutzt sich. In diesem Beispiel haben nachgeschlagen Sie nicht wirklich ein Wort sinnvoll, bis Sie es verstehen, und das könnte bedeuten, mehr Wörter nachschlagen. Dies bringt uns zwei Punkt 2) Es hört irgendwo. Es hat eine Art von Basis-Fall haben. Andernfalls würden Sie gerade jedes Wort im Wörterbuch am Ende aufzublicken, die wahrscheinlich nicht zu nützlich ist. Unsere Basis-Fall war, dass Sie genügend Informationen bekam eine Verbindung zwischen dem, was du hast vorher und nicht verstand.

Das herkömmliche Beispiel, das gegeben ist, ist faktoriellen, wobei 5 faktoriellen sind 1 * 2 * 3 * 4 * 5 (das ist 120). Der Basisfall wäre 0 (oder 1, abhängig). Also, für jede ganze Zahl n, haben Sie die folgenden

n ist gleich 0? 1 zurückzukehren andernfalls zurückkehren n * (Fakultät von n-1)

Lassen Sie sich dies mit dem Beispiel von 4 (die wir im Voraus wissen, 1 * 2 * 3 * 4 = 24).

Fakultät von 4 ... ist es 0? nein, es muss also 4 * factorial von 3 sein, aber was ist faktorielles von 3? es ist 3 * factorial von 2 faktoriellen von 2 2 * factorial von 1 Fakultät von 1 1 * factorial von 0 ist, und wir wissen faktorielles von 0! :-D es 1 ist, das ist die Definition faktoriellen von 1: 1 * faktoriellen von 0, die 1 war so ... 1 * 1 = 1 faktoriellen von 2 * 2 faktoriellen von 1, die 1 war so ... 2 * 1 = 2 faktoriellen von 3 * 3 faktoriellen von 2, die 2 ... so war 3 · 2 = 6 faktoriellen von 4 (endlich !!) sind 4 * faktoriellen von 3, die 6 betrug ... 4 * 6 24

Factorial ist ein einfacher Fall von „Basisfall und verwendet selbst“.

Nun bemerken wir noch auf Fakultäts von 4 arbeitet der gesamte Weg nach unten ... Wenn wir factorial von 100 wollten, würden wir den ganzen Weg hinunter zu 0 gehen ..., die eine Menge Aufwand, um es haben könnte. In gleicher Weise, wenn wir ein obskures Wort nachzuschlagen im Wörterbuch finden, könnte es also und Scannen nach Kontext Hinweise nehmen suchen, bis wir eine Verbindung, wir sind vertraut mit finden. Rekursive Methoden können eine lange Zeit in Anspruch nehmen ihren Weg durch zu arbeiten. Allerdings, wenn sie richtig eingesetzt ist, und verstand, können sie komplizierte Arbeit überraschend einfach.

Beantwortet am 04/05/2010 um 17:04
quelle vom benutzer

stimmen
1

Sehr viele Probleme können in zwei Arten von Stücken gedacht werden:

  1. Base Fälle, die sind elementare Dinge, die Sie bei einem Blick auf sie lösen können, und
  2. Rekursive Fälle, die ein größeres Problem aus kleineren Stücken (elementar oder anderweitig) zu bauen.

Also, was ist eine rekursive Funktion? Nun, das ist, wo Sie eine Funktion haben, die in Bezug auf sich selbst definiert ist, direkt oder indirekt. OK, das klingt lächerlich, bis Sie erkennen, dass es oben für die Probleme der beschriebenen Art sinnvoll ist: Sie können die Basis Fällen direkt und befassen sich mit den rekursiven Fällen unter Verwendung von rekursiven Aufrufen lösen die kleineren Stücke des Problems innerhalb eingebettet zu lösen.

Das wirklich klassisches Beispiel, wo Sie brauchen Rekursion (oder etwas, das gefällt mir sehr gut riecht) ist, wenn man mit einem Baum zu tun hat. Die Blätter des Baums sind die Basisfall, und die Zweige sind die rekursive Fall. (In pseudo-C.)

struct Tree {
    int leaf;
    Tree *leftBranch;
    Tree *rightBranch;
};

Der einfachste Weg, dies zu drucken, um aus ist Rekursion zu verwenden:

function printTreeInOrder(Tree *tree) {
    if (tree->leftBranch) {
        printTreeInOrder(tree->leftBranch);
    }
    print(tree->leaf);
    if (tree->rightBranch) {
        printTreeInOrder(tree->rightBranch);
    }
}

Es ist tot leicht zu sehen, dass das funktionieren wird, da es kristallklar ist. (Die nicht-rekursive äquivalent ist ziemlich viel komplexer, eine Stapelstruktur erfordern intern die Liste der Dinge zu verwalten zu verarbeiten.) Nun, unter der Annahme, dass niemand eine kreisförmige Verbindung natürlich getan.

Mathematisch zu dem Trick, dass die Rekursion zeigt, gezähmt ist auf der Suche nach einer Metrik für die Größe der Argumente zu konzentrieren. Für unsere Baum Beispiel ist die einfachste Metrik die maximale Tiefe des Baumes unterhalb des aktuellen Knotens. Bei Blättern, dann ist es Null. Bei einem Zweig mit Blättern nur darunter, es ist eines, etc. Dann kann man einfach zeigen, dass es Sequenz von der Größe der Argumente streng geordneten ist, dass die Funktion aufgerufen, um auf den Baum zu verarbeiten; die Argumente der rekursiven Aufrufe sind immer „weniger“ im Sinne der Metrik als Argument für den gesamten Anruf. Mit einem streng monoton fallend Kardinal Metrik, sind Sie sortieren.

Es ist auch möglich, eine unendliche Rekursion zu haben. Das ist chaotisch und in vielen Sprachen wird nicht funktionieren, weil der Stapel sprengt. (Wo es funktioniert, muss die Sprache Motor zu bestimmen, dass die Funktion irgendwie nicht zurückkehrt und ist daher in der Lage die Führung des Stapels zu optimieren weg Tricky Sachen im Allgemeinen;. Schwanz-Rekursion ist nur die banalsten Art und Weise, dies zu tun .)

Beantwortet am 04/05/2010 um 16:29
quelle vom benutzer

stimmen
1

Rekursion ist Technik, um eine Funktion zu definieren, einen Satz oder einen Algorithmus in Bezug auf sich selbst.

Beispielsweise

n! = n(n-1)(n-2)(n-3)...........*3*2*1

Nun kann es rekursiv wie folgt definiert werden: -

n! = n(n-1)!   for n>=1

In Programmierung Begriffe, wenn eine Funktion oder Methode nennt sich wiederholt, bis einige bestimmte Bedingung erfüllt wird, wird dieser Prozess Rekursion genannt. Aber es muss ein Abschluss Zustand und Funktion oder Methode darf nicht in eine Endlosschleife eingeben.

Beantwortet am 04/05/2010 um 16:22
quelle vom benutzer

stimmen
1

Rekursion in computing ist eine Technik verwendet, um eine Folge oder Nebenwirkung nach der normalen Rückkehr von einer einzigen Funktion (Methode, Verfahren oder Block) Aufruf zu berechnen.

Die rekursive Funktion per Definition muss die Fähigkeit haben, sich selbst aufzurufen, entweder direkt oder indirekt (durch andere Funktionen) in Abhängigkeit von einer Ausgangsbedingung oder Bedingungen nicht erfüllt werden. Wenn eine Ausgangsbedingung wird auf den besonderen Aufruf zurückkehrt, um es den Anrufer erfüllt. Dies setzt sich fort, bis der anfängliche Aufruf aus, zu welcher Zeit das gewünschte Ergebnis oder Nebenwirkung verfügbar sein wird zurückgegeben.

Als Beispiel ist hier eine Funktion , um den Quicksort - Algorithmus in Scala durchzuführen ( aus dem Eintrag für Scala Wikipedia kopiert )

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

In diesem Fall ist die Ausgangsbedingung eine leere Liste.

Beantwortet am 04/05/2010 um 15:14
quelle vom benutzer

stimmen
1

Funktion aufrufen selbst oder seine eigene Definition verwenden.

Beantwortet am 04/05/2010 um 14:59
quelle vom benutzer

stimmen
1

Jeder Algorithmus zeigt strukturelle Rekursion auf einem Datentyp , wenn im Grunde besteht aus einer Schalter-Anweisung mit einem Fall , für jeden Fall des Datentypen.

zum Beispiel, wenn Sie auf einer Art arbeiten

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

ein struktureller rekursiven Algorithmus würde die Form hat

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

das ist wirklich die naheliegendste Möglichkeit, jede algorith zu schreiben, die auf einer Datenstruktur arbeitet.

jetzt, wenn Sie den ganzen Zahlen sehen (na ja, die natürlichen Zahlen) definiert die Peano Axiome mit

 integer = 0 | succ(integer)

Sie sieht, dass ein struktureller rekursiven Algorithmus auf ganze Zahlen wie folgt aussieht

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

die allzu bekannte Fakultäts-Funktion ist über die banalsten Beispiel für diese Form.

Beantwortet am 04/05/2010 um 14:53
quelle vom benutzer

stimmen
1

hey, sorry, wenn meine Meinung nach mit jemandem stimmt, ich versuche nur Rekursion in einfachem Englisch zu erklären.

Angenommen, Sie drei Manager haben - Jack, John und Morgan. Jack schafft 2 Programmierer, John - 3 und Morgan - 5. Sie jeder Manager 300 $ geben werden und wollen wissen, was es kosten würde. Die Antwort ist klar - aber was, wenn 2 von Morgan-s Mitarbeiter sind auch Manager?

Hier kommt die Rekursion. Sie gehen von der Spitze der Hierarchie. die sommerlich Kosten $ 0. Sie beginnen mit Jack, dann überprüfen Sie, ob er irgendwelche Manager wie Mitarbeiter. wenn Sie feststellen, jede von ihnen sind, überprüfen Sie, ob sie irgendwelche Manager wie Mitarbeiter und so weiter haben. In 300 $, um die sommerlich Kosten jedes Mal, wenn Sie einen Manager finden. gehen, wenn Sie mit Jack fertig sind, zu John, seinen Mitarbeitern und dann zu Morgan.

Du wirst nie wissen, wie viele Zyklen werden Sie gehen, bevor eine Antwort zu bekommen, obwohl Sie wissen, wie viele Manager Sie haben und wie viele Budgets Sie ausgeben können.

Rekursion ist ein Baum, mit Zweigen und Blättern, die so genannte Eltern und Kinder sind. Wenn Sie einen Rekursion-Algorithmus verwenden, können Sie mehr oder weniger bewusst sind, einen Baum aus den Daten zu bauen.

Beantwortet am 04/05/2010 um 13:50
quelle vom benutzer

stimmen
1

Im Klartext bedeutet Rekursion some immer wieder zu wiederholen.

Bei der Programmierung ein Beispiel ist die Funktion in sich selbst zu nennen.

Schauen Sie auf das folgende Beispiel Fakultät einer Zahl der Berechnung:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
Beantwortet am 04/05/2010 um 13:48
quelle vom benutzer

stimmen
1

Rekursion ist der Prozess, in dem ein Methodenaufruf iself der Lage sein, eine bestimmte Aufgabe auszuführen. Es reduziert Redundanzen Code. Die meisten recurssive Funktionen oder Methoden müssen eine condifiton haben den recussive ruft also aufhören, es zu brechen von selbst anrufen, wenn eine Bedingung erfüllt ist - das das Erstellen einer Endlosschleife verhindert. Nicht alle Funktionen geeignet rekursiv verwendet werden.

Beantwortet am 04/05/2010 um 13:42
quelle vom benutzer

stimmen
1

es ist eine Art, die Dinge immer und immer wieder auf unbestimmte Zeit so zu tun, dass jede Option verwendet wird.

wenn Sie zum Beispiel wollte alle Links auf einer HTML-Seite bekommen möchten Sie Rekursion haben, weil, wenn Sie alle Links auf Seite bekommen 1 werden Sie alle Links auf jeder der Links auf der ersten Seite gefunden zu erhalten. dann für jeden Link zu einer newpage werden Sie diese Links mögen, und so weiter ... in anderen Worten, es ist eine Funktion, die sich von innen selbst nennt.

wenn Sie dies tun müssen Sie einen Weg wissen, wann man aufhören muss, sonst werden Sie in einer Endlosschleife, so dass Sie eine ganze Zahl param auf die Funktion hinzufügen, die Anzahl der Zyklen zu verfolgen.

in c # werden Sie etwas wie dieses:

private void findlinks(string URL, int reccursiveCycleNumb)    {
   if (reccursiveCycleNumb == 0)
        {
            return;
        }

        //recursive action here
        foreach (LinkItem i in LinkFinder.Find(URL))
        {
            //see what links are being caught...
            lblResults.Text += i.Href + "<BR>";

            findlinks(i.Href, reccursiveCycleNumb - 1);
        }

        reccursiveCycleNumb -= reccursiveCycleNumb;
}
Beantwortet am 04/05/2010 um 13:02
quelle vom benutzer

stimmen
1

„Wenn ich einen Hammer habe, alles wie ein Nagel aussehen lassen.“

Rekursion ist eine Problemlösungsstrategie für die großen Probleme, wo nur jeder bei Schritt „2 kleine Dinge in eine größeren Sache machen“ , jedes Mal mit dem gleichen Hammer.

Beispiel

Angenommen, Ihr Schreibtisch mit einem unorganisierten Chaos von 1024 Papieren bedeckt ist. Wie Sie einen ordentlich, sauber Stapel von Papieren aus dem Chaos machen, Rekursion?

  1. Divide: Verbreiten Sie alle Blätter heraus, so dass Sie nur ein Blatt in jedem „Stack“ haben.
  2. Erobern:
    1. Gehen Sie rund um jedes Blatt einzeln nach oben auf einem anderen Blatt setzen. Sie haben jetzt Stapel 2.
    2. Gehen Sie um, setzt jeden 2-Stapel auf einem anderen 2-Stack. Sie haben jetzt Stapel von 4.
    3. Gehen Sie um, setzt jeden 4-Stapel auf einem anderen 4-Stack. Sie haben jetzt Stapel von 8.
    4. ... und weiter ...
    5. Sie haben jetzt einen riesigen Stapel von 1024 Blättern!

Beachten Sie, dass diese ziemlich intuitiv ist, abgesehen von allem zu zählen (was nicht unbedingt notwendig ist). Sie werden vielleicht nicht den ganzen Weg hinunter zu 1-Blattstapel, in Wirklichkeit gehen, aber man konnte und es würde immer noch funktionieren. Der wichtige Teil ist der Hammer: Mit den Armen, können Sie immer einen Stapel gelegt auf dem anderen einen größeren Stapel zu machen, und es spielt keine Rolle (innerhalb Grund), wie groß entweder Stapel ist.

Beantwortet am 04/05/2010 um 12:54
quelle vom benutzer

stimmen
1

Rekursion, wie es in die Programmierung gilt ruft im Grunde eine Funktion aus dem Inneren ihrer eigenen Definition (in sich selbst), mit verschiedenen Parametern, um eine Aufgabe zu erfüllen.

Beantwortet am 04/05/2010 um 12:25
quelle vom benutzer

stimmen
1

Sie wollen, es zu benutzen, wann immer Sie eine Baumstruktur haben. Es ist sehr nützlich in XML zu lesen.

Beantwortet am 21/08/2008 um 14:18
quelle vom benutzer

stimmen
1

Mario, ich verstehe nicht, warum Sie die Rekursion für das Beispiel verwendet .. Warum durch jeden Eintrag nicht einfach Schleife? Etwas wie das:

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

Das obige Verfahren wäre schneller und einfacher. Es gibt keine Notwendigkeit Rekursion anstelle einer einfachen Schleife zu verwenden. Ich denke, diese Art von Beispielen, warum Rekursion einen schlechten Ruf bekommt. Auch die kanonische Fakultäts-Funktion Beispiel wird besser mit einer Schleife implementiert.

Beantwortet am 06/08/2008 um 04:19
quelle vom benutzer

stimmen
0

Eigentlich sollte die bessere rekursive Lösung für faktorielle sein:

int factorial_accumulate(int n, int accum) {
    return (n < 2 ? accum : factorial_accumulate(n - 1, n * accum));
}

int factorial(int n) {
    return factorial_accumulate(n, 1);
}

Da diese Version Schwanz rekursive

Beantwortet am 21/08/2008 um 14:39
quelle vom benutzer

stimmen
0

Ich verwende Rekursion. Was hat das mit mit einem CS Grad zu tun ... (was ich nicht tun, übrigens)

Gemeinsame Nutzung Ich habe festgestellt:

  1. sitemaps - Rekursion durch Dateisystem auf Dokument root Ausgang
  2. Spinnen - über eine Website - Adresse zu finden , E - Mail - Crawling, Links usw.
  3. ?
Beantwortet am 06/08/2008 um 04:13
quelle vom benutzer

stimmen
0

Ich habe eine rekursive Funktion erstellt eine Liste von Strings mit einem Separator zwischen ihnen verketten. Ich benutze es meist SQL - Ausdrücke zu erstellen, indem Sie eine Liste von Feldern , wie die ‚passing Elemente ‘ und ein ‚ Komma + Raum ‘ als Trennzeichen . Hier ist die Funktion (Es verwendet einige Borland Builder nativen Datentypen, sondern kann angepasst werden , um eine andere Umgebung zu passen):

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

Ich nenne es auf diese Weise:

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

Stellen Sie sich vor Sie haben ein Array mit dem Namen ‚ Felder ‘ mit dieser Daten im Inneren: ‚ Albumname ‘, ‚ ‘, ‚ labelId ‘. Dann rufen Sie die Funktion:

ArrangeString(fields, 0, ", ");

Da die Funktion zu arbeiten beginnt, wird die Variable ‚ Ergebnis erhält‘ den Wert der Position 0 des Arrays, das ‚ist Albumname ‘.

Dann überprüft er, ob die Position mit ihm zu tun hat die letzte ist. Da dies nicht der Fall, dann verkettet sie das Ergebnis mit dem Separator und dem Ergebnis einer Funktion, die, oh Gott, das gleiche Funktion ist. Aber dieses Mal, check it out, es selbst Zugabe ruft 1 in die Position.

ArrangeString(fields, 1, ", ");

Es hält sich wiederholende, eine LIFO Stapel zu schaffen, bis es einen Punkt erreicht, wo die Position ist die letzte behandelt werden, so gibt die Funktion nur den auf dieser Position auf der Liste, nicht mehr verketten. Dann wird der Stapel rückwärts verkettet.

Ich habs? Wenn Sie dies nicht tun, habe ich eine andere Art und Weise, es zu erklären. :O)

Beantwortet am 06/08/2008 um 04:00
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more