Rekursion verstehen [geschlossen]

Ich habe große Probleme, die Rekursion in der Schule zu verstehen . Immer wenn der Professor darüber spricht, scheine ich es zu verstehen, aber sobald ich es alleine versuche, bläst es mein Gehirn völlig um.

Ich habe die ganze Nacht versucht, Towers of Hanoi zu lösen und habe mich total umgehauen. Mein Lehrbuch hat nur etwa 30 Seiten in Rekursion, daher ist es nicht allzu nützlich. Kennt jemand Bücher oder Ressourcen, die zur Klärung dieses Themas beitragen können?

Wie entleert man eine Vase mit fünf Blumen?

Antwort: Wenn die Vase nicht leer ist, nehmen Sie eine Blume heraus und leeren dann eine Vase mit vier Blumen.

Wie entleert man eine Vase mit vier Blumen?

Antwort: Wenn die Vase nicht leer ist, nehmen Sie eine Blume heraus und leeren dann eine Vase mit drei Blumen.

Wie entleert man eine Vase mit drei Blumen?

Antwort: Wenn die Vase nicht leer ist, nehmen Sie eine Blume heraus und leeren dann eine Vase mit zwei Blumen.

Wie entleert man eine Vase mit zwei Blumen?

Antwort: Wenn die Vase nicht leer ist, nehmen Sie eine Blume heraus und leeren dann eine Vase mit einer Blume.

Wie entleert man eine Vase mit einer Blume?

Antwort: Wenn die Vase nicht leer ist, nehmen Sie eine Blume heraus und leeren dann eine Vase ohne Blumen.

Wie entleert man eine Vase ohne Blumen?

Antwort: Wenn die Vase nicht leer ist, nehmen Sie eine Blume heraus, aber die Vase ist leer, damit Sie fertig sind.

Das wiederholt sich. Verallgemeinern wir es:

Wie entleert man eine Vase mit N Blumen?

Antwort: Wenn die Vase nicht leer ist, nehmen Sie eine Blume heraus und leeren dann eine Vase mit N-1- Blumen.

Hmm, können wir das im Code sehen?

void emptyVase( int flowersInVase ) {
  if( flowersInVase > 0 ) {
   // take one flower and
    emptyVase( flowersInVase - 1 ) ;

  } else {
   // the vase is empty, nothing to do
  }
}

Hmm, hätten wir das nicht einfach in einer for-Schleife machen können?

Warum, ja, Rekursion kann durch Iteration ersetzt werden, aber Rekursion ist oft eleganter.

Reden wir über Bäume. In der Informatik ist ein Baum eine Struktur aus Knoten , wobei jeder Knoten eine bestimmte Anzahl von untergeordneten Knoten hat, die auch Knoten sind, oder null. Ein Binärbaum ist ein Baum aus Knoten mit genau zwei untergeordneten Elementen, die normalerweise als "links" und "rechts" bezeichnet werden. Wieder können die Kinder Knoten oder Null sein. Eine Wurzel ist ein Knoten, der keinem anderen Knoten untergeordnet ist.

Stellen Sie sich vor, ein Knoten hat zusätzlich zu seinen untergeordneten Knoten einen Wert, eine Zahl, und stellen Sie sich vor, wir möchten alle Werte in einem Baum summieren.

Um den Wert in einem Knoten zu summieren, addieren wir den Wert des Knotens selbst zum Wert seines linken Kindes, falls vorhanden, und zum Wert seines rechten Kindes, falls vorhanden. Denken Sie nun daran, dass die untergeordneten Elemente, wenn sie nicht null sind, auch Knoten sind.

Um das linke Kind zu summieren, würden wir den Wert des Kindknotens selbst zum Wert seines linken Kindes (falls vorhanden) und zum Wert seines rechten Kindes (falls vorhanden) addieren.

Um den Wert des linken Kindes des linken Kindes zu summieren, addieren wir den Wert des Kinderknotens selbst zum Wert des linken Kindes, falls vorhanden, und zum Wert des rechten Kindes, falls vorhanden.

Vielleicht haben Sie vorausgesehen, wohin ich damit gehe, und möchten einen Code sehen? OK:

struct node {
  node* left;
  node* right;
  int value;
} ;

int sumNode( node* root ) {
  // if there is no tree, its sum is zero
  if( root == null ) {
    return 0 ;

  } else { // there is a tree
    return root->value + sumNode( root->left ) + sumNode( root->right ) ;
  }
}

Beachten Sie, dass anstatt die untergeordneten Elemente explizit zu testen, um festzustellen, ob sie Null oder Knoten sind, die rekursive Funktion für einen Nullknoten nur Null zurückgibt.

Angenommen, wir haben einen Baum, der so aussieht (die Zahlen sind Werte, die Schrägstriche zeigen auf untergeordnete Elemente und @ bedeutet, dass der Zeiger auf null zeigt):

     5
    / \
   4   3
  /\   /\
 2  1 @  @
/\  /\
@@  @@

Wenn wir sumNode im Stammverzeichnis (dem Knoten mit dem Wert 5) aufrufen, geben wir Folgendes zurück:

return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

Lassen Sie uns das an Ort und Stelle erweitern. Überall, wo wir sumNode sehen, werden wir es durch die Erweiterung der return-Anweisung ersetzen:

sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + 0 + 0
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + sumNode(null ) + sumNode( null ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + 0 + 0 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 
 + 3  ;

return 5 + 4 
 + 2 
 + 1 
 + 3  ;

return 5 + 4 
 + 3
 + 3  ;

return 5 + 7
 + 3  ;

return 5 + 10 ;

return 15 ;

Sehen Sie nun, wie wir eine Struktur von beliebiger Tiefe und "Verzweigung" erobert haben, indem wir sie als wiederholte Anwendung einer zusammengesetzten Vorlage betrachteten? Jedes Mal, wenn wir unsere sumNode-Funktion verwendeten, behandelten wir nur einen einzelnen Knoten mit einem einzelnen if / then-Zweig und zwei einfachen return-Anweisungen, die sich beinahe selbst geschrieben hätten, direkt aus unserer Spezifikation?

How to sum a node:
 If a node is null 
   its sum is zero
 otherwise 
   its sum is its value 
   plus the sum of its left child node
   plus the sum of its right child node

Das ist die Kraft der Rekursion.

Das obige Vasenbeispiel ist ein Beispiel für die Schwanzrekursion . Alles, was Schwanzrekursion bedeutet, ist, dass in der rekursiven Funktion, wenn wir rekursiv waren (dh wenn wir die Funktion erneut aufriefen), dies das letzte war, was wir getan haben.

Das Baumbeispiel war nicht schwanzrekursiv, denn obwohl wir als letztes das rechte Kind rekursiv gemacht haben, haben wir vorher das linke Kind rekursiv gemacht.

Tatsächlich spielte die Reihenfolge, in der wir die Kinder aufgerufen und den Wert des aktuellen Knotens addiert haben, keine Rolle, da die Addition kommutativ ist.

Schauen wir uns nun eine Operation an, bei der die Reihenfolge eine Rolle spielt. Wir werden einen binären Baum von Knoten verwenden, aber dieses Mal ist der gehaltene Wert ein Zeichen, keine Zahl.

Unser Baum hat eine spezielle Eigenschaft, dass für jeden Knoten sein Zeichen nach (in alphabetischer Reihenfolge) dem Zeichen folgt, das von seinem linken Kind und davor gehalten wird (in alphabetischer Reihenfolge) dem Zeichen seines rechten Kindes steht.

Wir möchten den Baum in alphabetischer Reihenfolge drucken. Das ist angesichts der besonderen Eigenschaft des Baumes einfach. Wir drucken nur das linke Kind, dann das Zeichen des Knotens und dann das rechte Kind.

Wir wollen nicht nur wohl oder übel drucken, sondern geben unserer Funktion etwas zum Drucken. Dies ist ein Objekt mit einer Druckfunktion (char). Wir müssen uns keine Gedanken darüber machen, wie es funktioniert. Nur wenn print aufgerufen wird, wird irgendwo etwas gedruckt.

Lassen Sie uns das im Code sehen:

struct node {
  node* left;
  node* right;
  char value;
} ;

// don't worry about this code
class Printer {
  private ostream& out;
  Printer( ostream& o ) :out(o) {}
  void print( char c ) { out << c; }
}

// worry about this code
int printNode( node* root, Printer& printer ) {
  // if there is no tree, do nothing
  if( root == null ) {
    return ;

  } else { // there is a tree
    printNode( root->left, printer );
    printer.print( value );
    printNode( root->right, printer );
}

Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );

Zusätzlich zur jetzt wichtigen Reihenfolge der Operationen zeigt dieses Beispiel, dass wir Dinge in eine rekursive Funktion übergeben können. Das einzige, was wir tun müssen, ist sicherzustellen, dass wir es bei jedem rekursiven Aufruf weitergeben. Wir haben einen Knotenzeiger und einen Drucker an die Funktion übergeben und sie bei jedem rekursiven Aufruf "down" übergeben.

Nun, wenn unser Baum so aussieht:

         k
        / \
       h   n
      /\   /\
     a  j @  @
    /\ /\
    @@ i@
       /\
       @@

Was werden wir drucken?

From k, we go left to
  h, where we go left to
    a, where we go left to 
      null, where we do nothing and so
    we return to a, where we print 'a' and then go right to
      null, where we do nothing and so
    we return to a and are done, so
  we return to h, where we print 'h' and then go right to
    j, where we go left to
      i, where we go left to 
        null, where we do nothing and so
      we return to i, where we print 'i' and then go right to
        null, where we do nothing and so
      we return to i and are done, so
    we return to j, where we print 'j' and then go right to
      null, where we do nothing and so
    we return to j and are done, so
  we return to h and are done, so
we return to k, where we print 'k' and then go right to
  n where we go left to 
    null, where we do nothing and so
  we return to n, where we print 'n' and then go right to
    null, where we do nothing and so
  we return to n and are done, so 
we return to k and are done, so we return to the caller

Wenn wir uns also nur die Zeilen ansehen, die wir gedruckt haben:

    we return to a, where we print 'a' and then go right to
  we return to h, where we print 'h' and then go right to
      we return to i, where we print 'i' and then go right to
    we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
  we return to n, where we print 'n' and then go right to

Wir sehen, wir haben "ahijkn" gedruckt, was in der Tat in alphabetischer Reihenfolge ist.

Wir schaffen es, einen ganzen Baum in alphabetischer Reihenfolge zu drucken, indem wir wissen, wie man einen einzelnen Knoten in alphabetischer Reihenfolge druckt. Das war nur (weil unser Baum die besondere Eigenschaft hatte, Werte links von alphabetisch späteren Werten zu ordnen) zu wissen, dass das linke Kind vor dem Drucken des Knotenwerts und das rechte Kind nach dem Drucken des Knotenwerts gedruckt werden musste.

Und das ist die Kraft der Rekursion: in der Lage zu sein, ganze Dinge zu tun, indem man nur weiß, wie man einen Teil des Ganzen macht (und weiß, wann man aufhört zu rekursieren).

Daran erinnern, dass in den meisten Sprachen Operator || ("oder") Kurzschlüsse, wenn der erste Operand wahr ist, lautet die allgemeine rekursive Funktion:

void recurse() { doWeStop() || recurse(); } 

Luc M kommentiert:

SO sollte ein Abzeichen für diese Art von Antwort erstellen. Herzliche Glückwünsche!

Danke, Luc! Aber tatsächlich, weil ich diese Antwort mehr als vier Mal bearbeitet habe (um das letzte Beispiel hinzuzufügen, aber hauptsächlich, um Tippfehler zu korrigieren und zu polieren - das Tippen auf einer winzigen Netbook-Tastatur ist schwierig), kann ich keine Punkte mehr dafür bekommen . Was mich etwas davon abhält, mich in zukünftigen Antworten so viel Mühe zu geben.

Siehe meinen Kommentar hier dazu: /programming/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

Ihr Gehirn explodierte, weil es in eine unendliche Rekursion geriet. Das ist ein häufiger Anfängerfehler.

Ob Sie es glauben oder nicht, Sie verstehen bereits die Rekursion, Sie werden nur von einer gemeinsamen, aber fehlerhaften Metapher für eine Funktion heruntergezogen: einer kleinen Box mit Dingen, die rein und raus kommen.

Denken Sie statt einer Aufgabe oder Prozedur wie "Erfahren Sie mehr über Rekursion im Netz". Das ist rekursiv und Sie haben kein Problem damit. Um diese Aufgabe abzuschließen, können Sie:

a) Lesen Sie die Ergebnisseite von Google für "Rekursion".
b) Wenn Sie es gelesen haben, folgen Sie dem ersten Link darauf und ...
a.1) Lesen Sie diese neue Seite über Rekursion 
b.1) Wenn Sie es gelesen haben, folgen Sie dem ersten Link darauf und ...
a.2) Lesen Sie diese neue Seite über Rekursion 
b.2) Wenn Sie es gelesen haben, folgen Sie dem ersten Link darauf und ...

Wie Sie sehen, haben Sie lange Zeit ohne Probleme rekursive Dinge gemacht.

Wie lange würden Sie diese Aufgabe noch erledigen? Für immer, bis dein Gehirn explodiert? Natürlich nicht, Sie werden an einem bestimmten Punkt anhalten, wenn Sie glauben, die Aufgabe erledigt zu haben.

Es ist nicht erforderlich, dies anzugeben, wenn Sie aufgefordert werden, "mehr über Rekursion im Netz herauszufinden", da Sie ein Mensch sind und dies selbst ableiten können.

Der Computer kann nicht auf eine Buchse schließen, daher müssen Sie eine explizite Endung einfügen: " Erfahren Sie mehr über die Rekursion im Internet, BIS Sie sie verstehen oder maximal 10 Seiten gelesen haben ".

Sie haben auch gefolgert, dass Sie auf der Ergebnisseite von Google für "Rekursion" beginnen sollten, und auch dies kann ein Computer nicht. Die vollständige Beschreibung unserer rekursiven Aufgabe muss auch einen expliziten Ausgangspunkt enthalten:

" Erfahren Sie mehr über Rekursion im Internet , BIS Sie es verstehen oder maximal 10 Seiten gelesen haben und unter www.google.com/search?q=recursion beginnen. "

Um das Ganze zu verstehen, schlage ich vor, dass Sie eines dieser Bücher ausprobieren:

• Common Lisp: Eine sanfte Einführung in die symbolische Berechnung. Dies ist die süßeste nicht-mathematische Erklärung der Rekursion.
• Der kleine Intrigant.

Um die Rekursion zu verstehen, müssen Sie nur auf das Etikett Ihrer Shampooflasche schauen:

function repeat()
{
   rinse();
   lather();
   repeat();
}

Das Problem dabei ist, dass es keine Beendigungsbedingung gibt und die Rekursion auf unbestimmte Zeit wiederholt wird oder bis Ihnen das Shampoo oder heißes Wasser ausgeht (externe Beendigungsbedingungen, ähnlich wie beim Blasen Ihres Stapels).

Wenn Sie ein Buch suchen, das die Rekursion in einfachen Worten gut erklärt, schauen Sie sich Gödel, Escher, Bach an: Ein ewiges goldenes Geflecht von Douglas Hofstadter, insbesondere Kapitel 5. Zusätzlich zur Rekursion macht es eine gute Erklärung eine Reihe komplexer Konzepte in Informatik und Mathematik auf verständliche Weise, wobei eine Erklärung auf einer anderen aufbaut. Wenn Sie noch nie viel mit solchen Konzepten zu tun hatten, kann dies ein ziemlich umwerfendes Buch sein.

Dies ist eher eine Beschwerde als eine Frage. Haben Sie eine spezifischere Frage zur Rekursion? Wie bei der Multiplikation schreiben die Leute nicht viel darüber.

Wenn Sie von Multiplikation sprechen, denken Sie daran.

Frage:

Was ist a * b?

Antworten:

Wenn b 1 ist, ist es a. Ansonsten ist es a + a * (b-1).

Was ist ein * (b-1)? In der obigen Frage finden Sie eine Möglichkeit, dies zu klären.

Ich denke, diese sehr einfache Methode sollte Ihnen helfen, die Rekursion zu verstehen. Die Methode ruft sich selbst auf, bis eine bestimmte Bedingung erfüllt ist, und gibt dann Folgendes zurück:

function writeNumbers( aNumber ){
 write(aNumber);
 if( aNumber > 0 ){
  writeNumbers( aNumber - 1 );
 }
 else{
  return;
 }
}

Diese Funktion druckt alle Zahlen von der ersten Zahl aus, die Sie bis 0 eingeben. Also:

writeNumbers( 10 );
//This wil write: 10 9 8 7 6 5 4 3 2 1 0
//and then stop because aNumber is no longer larger then 0

Was im Bass passiert, ist, dass writeNumbers (10) 10 schreibt und dann writeNumbers (9) aufruft, die 9 schreiben und dann writeNumber (8) usw. aufrufen. Bis writeNumbers (1) 1 schreibt und dann writeNumbers (0) aufruft, die 0 schreiben butt ruft nicht writeNumbers (-1) auf;

Dieser Code ist im Wesentlichen derselbe wie:

for(i=10; i>0; i--){
 write(i);
}

Warum sollten Sie dann die Rekursion verwenden, wenn eine for-Schleife im Wesentlichen dasselbe tut? Nun, Sie verwenden meistens die Rekursion, wenn Sie für Schleifen verschachteln müssten, aber nicht wissen, wie tief sie verschachtelt sind. Zum Beispiel beim Ausdrucken von Elementen aus verschachtelten Arrays:

var nestedArray = Array('Im a string', 
                        Array('Im a string nested in an array', 'me too!'),
                        'Im a string again',
                        Array('More nesting!',
                              Array('nested even more!')
                              ),
                        'Im the last string');
function printArrayItems( stringOrArray ){
 if(typeof stringOrArray === 'Array'){
   for(i=0; i<stringOrArray.length; i++){ 
     printArrayItems( stringOrArray[i] );
   }
 }
 else{
   write( stringOrArray );
 }
}

printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'

Diese Funktion könnte ein Array annehmen, das in 100 Ebenen verschachtelt sein könnte, während Sie beim Schreiben einer for-Schleife diese 100 Mal verschachteln müssten:

for(i=0; i<nestedArray.length; i++){
 if(typeof nestedArray[i] == 'Array'){
  for(a=0; i<nestedArray[i].length; a++){
   if(typeof nestedArray[i][a] == 'Array'){
    for(b=0; b<nestedArray[i][a].length; b++){
     //This would be enough for the nestedAaray we have now, but you would have
     //to nest the for loops even more if you would nest the array another level
     write( nestedArray[i][a][b] );
    }//end for b
   }//endif typeod nestedArray[i][a] == 'Array'
   else{ write( nestedArray[i][a] ); }
  }//end for a
 }//endif typeod nestedArray[i] == 'Array'
 else{ write( nestedArray[i] ); }
}//end for i

Wie Sie sehen können, ist die rekursive Methode viel besser.

Tatsächlich verwenden Sie die Rekursion, um die Komplexität Ihres vorliegenden Problems zu verringern. Sie wenden die Rekursion an, bis Sie einen einfachen Basisfall erreichen, der leicht gelöst werden kann. Damit können Sie den letzten rekursiven Schritt lösen. Und damit alle anderen rekursiven Schritte bis zu Ihrem ursprünglichen Problem.

Ich werde versuchen, es mit einem Beispiel zu erklären.

Du weißt was n! meint? Wenn nicht: http://en.wikipedia.org/wiki/Factorial

3! = 1 * 2 * 3 = 6

Hier geht ein Pseudocode

function factorial(n) {
  if (n==0) return 1
  else return (n * factorial(n-1))
}

Probieren wir es aus:

factorial(3)

ist n 0?

Nein!

Also graben wir mit unserer Rekursion tiefer:

3 * factorial(3-1)

3-1 = 2

ist 2 == 0?

Nein!

Also gehen wir tiefer! 3 * 2 * Fakultät (2-1) 2-1 = 1

ist 1 == 0?

Nein!

Also gehen wir tiefer! 3 * 2 * 1 * Fakultät (1-1) 1-1 = 0

ist 0 == 0?

Ja!

Wir haben einen trivialen Fall

wir haben also 3 * 2 * 1 * 1 = 6

Ich hoffe das hat dir geholfen

Rekursion

Methode A ruft Methode A auf. Methode A ruft schließlich eine dieser Methoden A auf und beendet sie nicht, aber es ist eine Rekursion, weil sich etwas selbst aufruft.

Beispiel für eine Rekursion, bei der ich jeden Ordnernamen auf der Festplatte ausdrucken möchte: (in c #)

public void PrintFolderNames(DirectoryInfo directory)
{
    Console.WriteLine(directory.Name);

    DirectoryInfo[] children = directory.GetDirectories();

    foreach(var child in children)
    {
        PrintFolderNames(child); // See we call ourself here...
    }
}

Welches Buch benutzt du?

Das Standardlehrbuch über Algorithmen, das eigentlich gut ist, ist Cormen & Rivest. Meine Erfahrung ist, dass es Rekursion ziemlich gut lehrt.

Rekursion ist einer der schwierigeren Teile der Programmierung, und obwohl sie Instinkt erfordert, kann sie gelernt werden. Aber es braucht eine gute Beschreibung, gute Beispiele und gute Illustrationen.

Außerdem sind 30 Seiten im Allgemeinen viel, 30 Seiten in einer einzigen Programmiersprache sind verwirrend. Versuchen Sie nicht, die Rekursion in C oder Java zu lernen, bevor Sie die Rekursion im Allgemeinen aus einem allgemeinen Buch verstehen.

Eine rekursive Funktion ist einfach eine Funktion, die sich so oft aufruft, wie sie dazu benötigt wird. Es ist nützlich, wenn Sie etwas mehrmals verarbeiten müssen, aber nicht sicher sind, wie oft tatsächlich benötigt wird. In gewisser Weise könnte man sich eine rekursive Funktion als eine Art Schleife vorstellen. Wie bei einer Schleife müssen Sie jedoch Bedingungen angeben, unter denen der Prozess unterbrochen werden soll, da er sonst unendlich wird.

http://javabat.com ist ein lustiger und aufregender Ort, um Rekursion zu üben. Ihre Beispiele beginnen ziemlich leicht und arbeiten umfangreich durch (wenn Sie es so weit bringen wollen). Hinweis: Ihr Ansatz ist das Lernen durch Üben. Hier ist eine rekursive Funktion, die ich geschrieben habe, um einfach eine for-Schleife zu ersetzen.

Die for-Schleife:

public printBar(length)
{
  String holder = "";
  for (int index = 0; i < length; i++)
  {
    holder += "*"
  }
  return holder;
}

Hier ist die Rekursion, um dasselbe zu tun. (Beachten Sie, dass wir die erste Methode überladen, um sicherzustellen, dass sie genau wie oben verwendet wird.) Wir haben auch eine andere Methode, um unseren Index zu pflegen (ähnlich wie die for-Anweisung es oben für Sie tut). Die rekursive Funktion muss ihren eigenen Index beibehalten.

public String printBar(int Length) // Method, to call the recursive function
{
  printBar(length, 0);
}

public String printBar(int length, int index) //Overloaded recursive method
{
  // To get a better idea of how this works without a for loop
  // you can also replace this if/else with the for loop and
  // operationally, it should do the same thing.
  if (index >= length)
    return "";
  else
    return "*" + printBar(length, index + 1); // Make recursive call
}

Um es kurz zu machen: Rekursion ist eine gute Möglichkeit, weniger Code zu schreiben. In der letzteren printBar beachten Sie, dass wir eine if-Anweisung haben. Wenn unsere Bedingung erreicht ist, beenden wir die Rekursion und kehren zur vorherigen Methode zurück, die zur vorherigen Methode usw. zurückkehrt. Wenn ich eine printBar (8) einsende, erhalte ich ********. Ich hoffe, dass mit einem Beispiel einer einfachen Funktion, die das Gleiche wie eine for-Schleife tut, dies möglicherweise hilft. Sie können dies jedoch bei Java Bat besser üben.

Die wirklich mathematische Art, eine rekursive Funktion zu erstellen, wäre wie folgt:

1: Stellen Sie sich vor, Sie haben eine Funktion, die für f (n-1) korrekt ist, und bauen Sie f so, dass f (n) korrekt ist. 2: Baue f so, dass f (1) korrekt ist.

Auf diese Weise können Sie beweisen, dass die Funktion mathematisch korrekt ist und als Induktion bezeichnet wird . Es ist gleichbedeutend mit unterschiedlichen Basisfällen oder komplizierteren Funktionen für mehrere Variablen. Es ist auch äquivalent, sich vorzustellen, dass f (x) für alle x korrekt ist

Nun zu einem "einfachen" Beispiel. Erstellen Sie eine Funktion, mit der ermittelt werden kann, ob eine Münzkombination aus 5 Cent und 7 Cent für x Cent möglich ist. Zum Beispiel ist es möglich, 17 Cent mal 2x5 + 1x7 zu haben, aber unmöglich, 16 Cent zu haben.

Stellen Sie sich nun vor, Sie haben eine Funktion, die Ihnen sagt, ob es möglich ist, x Cent zu erstellen, solange x <n ist. Rufen Sie diese Funktion can_create_coins_small auf. Es sollte ziemlich einfach sein, sich vorzustellen, wie man die Funktion für n macht. Bauen Sie nun Ihre Funktion auf:

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins_small(n-7))
        return true;
    else if (n >= 5 && can_create_coins_small(n-5))
        return true;
    else
        return false;
}

Der Trick dabei ist zu erkennen, dass die Tatsache, dass can_create_coins für n funktioniert, bedeutet, dass Sie can_create_coins durch can_create_coins_small ersetzen können.

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

Eine letzte Sache, die zu tun ist, ist ein Basisfall, um die unendliche Rekursion zu stoppen. Beachten Sie, dass wenn Sie versuchen, 0 Cent zu erstellen, dies möglich ist, wenn Sie keine Münzen haben. Das Hinzufügen dieser Bedingung ergibt:

bool can_create_coins(int n)
{
    if (n == 0)
        return true;
    else if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

Es kann nachgewiesen werden, dass diese Funktion immer mit einer Methode namens Infinite Descent zurückgegeben wird , aber das ist hier nicht erforderlich. Sie können sich vorstellen, dass f (n) nur niedrigere Werte von n aufruft und schließlich immer 0 erreicht.

Um diese Informationen zur Lösung Ihres Tower of Hanoi-Problems zu verwenden, besteht der Trick meiner Meinung nach darin, dass Sie eine Funktion zum Verschieben von n-1-Tablets von a nach b (für jedes a / b) haben und versuchen, n Tabellen von a nach b zu verschieben .

Einfaches rekursives Beispiel in Common Lisp :

MYMAP wendet eine Funktion auf jedes Element in einer Liste an.

1) Eine leere Liste hat kein Element, daher geben wir die leere Liste zurück - () und NIL sind beide die leere Liste.

2) Wenden Sie die Funktion auf die erste Liste an, rufen Sie MYMAP für den Rest der Liste (den rekursiven Aufruf) auf und kombinieren Sie beide Ergebnisse zu einer neuen Liste.

(DEFUN MYMAP (FUNCTION LIST)
  (IF (NULL LIST)
      ()
      (CONS (FUNCALL FUNCTION (FIRST LIST))
            (MYMAP FUNCTION (REST LIST)))))

Sehen wir uns die verfolgte Ausführung an. Beim Eingeben einer Funktion werden die Argumente gedruckt. Beim Beenden einer Funktion wird das Ergebnis gedruckt. Bei jedem rekursiven Aufruf wird die Ausgabe auf Ebene eingerückt.

In diesem Beispiel wird die SIN-Funktion für jede Nummer in einer Liste aufgerufen (1 2 3 4).

Command: (mymap 'sin '(1 2 3 4))

1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
|   3 Enter MYMAP SIN (3 4)
|   | 4 Enter MYMAP SIN (4)
|   |   5 Enter MYMAP SIN NIL
|   |   5 Exit MYMAP NIL
|   | 4 Exit MYMAP (-0.75680256)
|   3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)

Das ist unser Ergebnis :

(0.841471 0.9092975 0.14112002 -0.75680256)

Um einem Sechsjährigen die Rekursion zu erklären, erklären Sie sie zuerst einem Fünfjährigen und warten Sie dann ein Jahr.

Tatsächlich ist dies ein nützliches Gegenbeispiel, da Ihr rekursiver Aufruf einfacher und nicht schwieriger sein sollte. Es wäre noch schwieriger, einem Fünfjährigen die Rekursion zu erklären, und obwohl Sie die Rekursion bei 0 stoppen könnten, haben Sie keine einfache Lösung, um einem Nulljährigen die Rekursion zu erklären.

Um ein Problem mithilfe der Rekursion zu lösen, unterteilen Sie es zunächst in eine oder mehrere einfachere Probleme, die Sie auf die gleiche Weise lösen können. Wenn das Problem dann einfach genug ist, um es ohne weitere Rekursion zu lösen, können Sie zu höheren Ebenen zurückkehren.

Tatsächlich war dies eine rekursive Definition, wie ein Problem mit Rekursion gelöst werden kann.

Kinder verwenden implizit die Rekursion, zum Beispiel:

Roadtrip nach Disney World

Sind wir schon da? (Nein)

Sind wir schon da? (Bald)

Sind wir schon da? (Fast ...)

Sind wir schon da? (SHHHH)

Sind wir schon da?(!!!!!)

An diesem Punkt schläft das Kind ein ...

Diese Countdown-Funktion ist ein einfaches Beispiel:

function countdown()
      {
      return (arguments[0] > 0 ?
        (
        console.log(arguments[0]),countdown(arguments[0] - 1)) : 
        "done"
        );
      }
countdown(10);

Relevant ist auch das Hofstadter-Gesetz für Softwareprojekte.

Das Wesen der menschlichen Sprache ist laut Chomsky die Fähigkeit endlicher Gehirne, das zu produzieren, was er für unendliche Grammatiken hält. Damit meint er nicht nur, dass es keine Obergrenze für das gibt, was wir sagen können, sondern dass es keine Obergrenze für die Anzahl der Sätze in unserer Sprache gibt, es gibt keine Obergrenze für die Größe eines bestimmten Satzes. Chomsky hat behauptet, dass das grundlegende Werkzeug, das all dieser Kreativität der menschlichen Sprache zugrunde liegt, die Rekursion ist: die Fähigkeit, dass eine Phrase in einer anderen Phrase des gleichen Typs wieder auftritt. Wenn ich "Johns Bruderhaus" sage, habe ich ein Substantiv, "Haus", das in einer Nominalphrase "Bruderhaus" vorkommt, und diese Substantivphrase kommt in einer anderen Nominalphrase vor, "Johns Bruderhaus". Das macht sehr viel Sinn, und es '

Verweise

• Rekursion und menschliches Denken

Bei der Arbeit mit rekursiven Lösungen versuche ich immer:

• Stellen Sie zuerst den Basisfall fest, dh wenn n = 1 in einer Lösung für Fakultät ist
• Versuchen Sie, für jeden anderen Fall eine allgemeine Regel zu finden

Es gibt auch verschiedene Arten von rekursiven Lösungen, es gibt den Divide and Conquer-Ansatz, der für Fraktale und viele andere nützlich ist.

Es wäre auch hilfreich, wenn Sie zuerst an einfacheren Problemen arbeiten könnten, um den Dreh raus zu bekommen. Einige Beispiele lösen die Fakultät und erzeugen die n-te Fibonacci-Zahl.

Als Referenz empfehle ich Algorithmen von Robert Sedgewick.

Hoffentlich hilft das. Viel Glück.

Autsch. Ich habe letztes Jahr versucht, die Türme von Hanoi herauszufinden. Das Knifflige an TOH ist, dass es kein einfaches Beispiel für eine Rekursion ist. Sie haben verschachtelte Rekursionen, die auch die Rolle der Türme bei jedem Aufruf ändern. Der einzige Weg, wie ich es sinnvoll machen konnte, bestand darin, die Bewegung der Ringe in meinem geistigen Auge buchstäblich zu visualisieren und zu verbalisieren, was der rekursive Aufruf sein würde. Ich würde mit einem einzigen Ring beginnen, dann zwei, dann drei. Ich habe das Spiel tatsächlich im Internet bestellt. Ich brauchte vielleicht zwei oder drei Tage, um mein Gehirn zu knacken.

Eine rekursive Funktion ist wie eine Feder, die Sie bei jedem Aufruf ein wenig komprimieren. Bei jedem Schritt legen Sie ein paar Informationen (aktueller Kontext) auf einen Stapel. Wenn der letzte Schritt erreicht ist, wird die Feder freigegeben und alle Werte (Kontexte) gleichzeitig gesammelt!

Ich bin mir nicht sicher, ob diese Metapher effektiv ist ... :-)

Abgesehen von den klassischen Beispielen (Fakultät, die das schlechteste Beispiel ist, da sie ineffizient und leicht zu reduzieren ist, Fibonacci, Hanoi ...), die etwas künstlich sind (ich verwende sie selten, wenn überhaupt, in realen Programmierfällen), ist dies der Fall interessant zu sehen, wo es wirklich verwendet wird.

Ein sehr häufiger Fall ist das Gehen auf einem Baum (oder einem Diagramm, aber Bäume sind im Allgemeinen häufiger).
Beispiel: Eine Ordnerhierarchie: Um die Dateien aufzulisten, iterieren Sie sie. Wenn Sie ein Unterverzeichnis finden, ruft sich die Funktion, die die Dateien auflistet, mit dem neuen Ordner als Argument auf. Wenn Sie von der Auflistung dieses neuen Ordners (und seiner Unterordner!) Zurückkommen, wird der Kontext in der nächsten Datei (oder dem nächsten Ordner) fortgesetzt.
Ein weiterer konkreter Fall ist das Zeichnen einer Hierarchie von GUI-Komponenten: Es ist üblich, Container wie Fenster zu haben, um Komponenten aufzunehmen, die auch Fenster sein können, oder zusammengesetzte Komponenten usw. Die Malroutine ruft rekursiv die Malfunktion jeder Komponente auf, die ruft die Lackierfunktion aller darin enthaltenen Komponenten usw. auf.

Ich bin mir nicht sicher, ob ich sehr klar bin, aber ich zeige gerne den realen Gebrauch von Unterrichtsmaterial, da es etwas war, über das ich in der Vergangenheit gestolpert bin.

Denken Sie an eine Arbeiterbiene. Es versucht Honig zu machen. Es macht seinen Job und erwartet, dass andere Arbeiterbienen den Rest des Honigs machen. Und wenn die Wabe voll ist, hört sie auf.

Betrachten Sie es als Magie. Sie haben eine Funktion, die denselben Namen hat wie die, die Sie implementieren möchten, und wenn Sie ihr das Teilproblem geben, löst sie es für Sie und das einzige, was Sie tun müssen, ist, die Lösung Ihres Teils in die Lösung zu integrieren gab dir.

Zum Beispiel möchten wir die Länge einer Liste berechnen. Nennen wir unsere Funktion magic_length und unseren magischen Helfer mit magic_length. Wir wissen, dass wenn wir der Unterliste geben, die nicht das erste Element enthält, wir durch Magie die Länge der Unterliste erhalten. Dann müssen wir uns nur noch überlegen, wie wir diese Informationen in unseren Job integrieren können. Die Länge des ersten Elements ist 1 und magic_counter gibt die Länge der Unterliste n-1 an, daher beträgt die Gesamtlänge (n-1) + 1 -> n

int magical_length( list )
  sublist = rest_of_the_list( list )
  sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
  return 1 + sublist_length

Diese Antwort ist jedoch unvollständig, da wir nicht berücksichtigt haben, was passiert, wenn wir eine leere Liste angeben. Wir dachten, dass die Liste, die wir haben, immer mindestens ein Element enthält. Daher müssen wir uns überlegen, was die Antwort sein soll, wenn wir eine leere Liste erhalten und die Antwort offensichtlich 0 ist. Fügen Sie diese Informationen also zu unserer Funktion hinzu, und dies wird als Basis- / Randbedingung bezeichnet.

int magical_length( list )
  if ( list is empty) then
    return 0
  else
    sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
    return 1 + sublist_length