Wann ist die Rekursion anzuwenden?

Wann gibt es einige (relativ) grundlegende Fälle (denken Sie an CS-Studenten im ersten Studienjahr), in denen man anstelle einer Schleife eine Rekursion verwenden würde?

Ich habe C ++ für Studenten für ungefähr zwei Jahre unterrichtet und Rekursion abgedeckt. Nach meiner Erfahrung sind Ihre Fragen und Gefühle sehr verbreitet. Im Extremfall empfinden einige Schüler die Rekursion als schwer zu verstehen, während andere sie für so ziemlich alles verwenden möchten.

Ich denke, Dave fasst es gut zusammen: Verwenden Sie es, wo es angebracht ist. Das heißt, verwenden Sie es, wenn es sich natürlich anfühlt. Wenn Sie auf ein Problem stoßen, bei dem es gut passt, werden Sie es höchstwahrscheinlich erkennen: Es scheint, als könnten Sie nicht einmal eine iterative Lösung finden. Klarheit ist auch ein wichtiger Aspekt der Programmierung. Andere Personen (und Sie auch!) Sollten in der Lage sein, den von Ihnen erstellten Code zu lesen und zu verstehen. Ich denke, es ist sicher zu sagen, dass iterative Schleifen auf den ersten Blick leichter zu verstehen sind als Rekursion.

Ich weiß nicht, wie gut Sie sich mit Programmierung oder Informatik im Allgemeinen auskennen, aber ich bin der festen Überzeugung, dass es keinen Sinn macht, hier über virtuelle Funktionen, Vererbung oder über fortgeschrittene Konzepte zu sprechen. Ich habe oft mit dem klassischen Beispiel der Berechnung von Fibonacci-Zahlen begonnen. Es passt hier gut, da Fibonacci-Zahlen rekursiv definiert sind . Dies ist leicht zu verstehen und erfordert keine ausgefallenen Funktionen der Sprache. Nachdem die Schüler ein grundlegendes Verständnis der Rekursion erlangt haben, haben wir uns einige einfache Funktionen angesehen, die wir zuvor erstellt haben. Hier ist ein Beispiel:

Enthält eine Zeichenfolge ein Zeichen $x$ ?

So haben wir es zuvor gemacht: Iterieren Sie die Zeichenfolge und prüfen Sie, ob ein Index x enthält $x$.

bool find(const std::string& s, char x)
{
   for(int i = 0; i < s.size(); ++i)
   {
      if(s[i] == x)
         return true;
   }

   return false;
}

Die Frage ist dann, können wir es rekursiv tun? Sicher können wir, hier ist ein Weg:

bool find(const std::string& s, int idx, char x)
{
   if(idx == s.size())
      return false;

   return s[idx] == x || find(s, ++idx);
}

Die nächste natürliche Frage ist dann, sollten wir es so machen? Wahrscheinlich nicht. Warum? Es ist schwieriger zu verstehen und es ist schwieriger, sich etwas auszudenken. Daher ist es auch fehleranfälliger.

Die Lösungen für einige Probleme werden natürlicher durch Rekursion ausgedrückt.

Angenommen, Sie haben eine Baumdatenstruktur mit zwei Arten von Knoten: Blätter, in denen ein ganzzahliger Wert gespeichert ist; und Zweige, die in ihren Feldern einen linken und einen rechten Teilbaum haben. Angenommen, die Blätter sind so angeordnet, dass der niedrigste Wert im äußersten linken Blatt steht.

Angenommen, die Aufgabe besteht darin, die Werte des Baums der Reihe nach auszudrucken. Ein rekursiver Algorithmus dafür ist ganz natürlich:

class Node { abstract void traverse(); }
class Leaf extends Node { 
  int val; 
  void traverse() { print(val); }
} 
class Branch extends Node {
  Node left, right;
  void traverse() { left.traverse(); right.traverse(); }
}

Das Schreiben von äquivalentem Code ohne Rekursion wäre viel schwieriger. Versuch es!

Allgemein funktioniert die Rekursion gut für Algorithmen auf rekursiven Datenstrukturen wie Bäumen oder für Probleme, die natürlich in Unterprobleme unterteilt werden können. Sehen Sie sich zum Beispiel Algorithmen zum Teilen und Erobern an .

Wenn Sie eine Rekursion in ihrer natürlichsten Umgebung sehen möchten, sollten Sie sich eine funktionierende Programmiersprache wie Haskell ansehen. In einer solchen Sprache gibt es kein Schleifenkonstrukt, daher wird alles durch Rekursion ausgedrückt (oder Funktionen höherer Ordnung, aber das ist eine andere Geschichte, von der es sich zu wissen lohnt).

Beachten Sie auch, dass funktionale Programmiersprachen eine optimierte Schwanzrekursion durchführen. Dies bedeutet, dass sie keinen Stack-Frame ablegen, es sei denn, sie müssen nicht - im Wesentlichen kann die Rekursion in eine Schleife konvertiert werden. Aus praktischer Sicht können Sie Code auf natürliche Weise schreiben, erhalten aber die Leistung von iterativem Code. Für das Protokoll scheint es, dass C ++ - Compiler auch Tail Calls optimieren , so dass es keinen zusätzlichen Aufwand für die Verwendung von Rekursion in C ++ gibt.

Von jemandem, der praktisch in Rekursion lebt, werde ich versuchen, etwas Licht in das Thema zu bringen.

Bei der ersten Einführung in die Rekursion lernen Sie, dass es sich um eine Funktion handelt, die sich selbst aufruft und im Grunde mit Algorithmen wie Tree Traversal demonstriert wird. Später werden Sie feststellen, dass es häufig in der funktionalen Programmierung für Sprachen wie LISP und F # verwendet wird. Mit dem F #, das ich schreibe, ist das meiste, was ich schreibe, rekursiv und mustergleich.

Wenn Sie mehr über funktionale Programmierung wie F # erfahren, werden Sie lernen, dass F # -Listen als einfach verknüpfte Listen implementiert sind. Dies bedeutet, dass Operationen, die nur auf den Kopf der Liste zugreifen, O (1) und Elementzugriff O (n) sind. Sobald Sie dies gelernt haben, tendieren Sie dazu, Daten als Liste zu durchlaufen, eine neue Liste in umgekehrter Reihenfolge zu erstellen und die Liste dann umzukehren, bevor Sie von der Funktion zurückkehren, die sehr effektiv ist.

Wenn Sie jetzt darüber nachdenken, werden Sie bald feststellen, dass rekursive Funktionen bei jedem Funktionsaufruf einen Stack-Frame verschieben und einen Stack-Überlauf verursachen können. Wenn Sie Ihre rekursive Funktion jedoch so konstruieren, dass sie einen Tail-Aufruf ausführen kann und der Compiler die Möglichkeit unterstützt, den Code für den Tail-Aufruf zu optimieren. dh .NET OpCodes.Tailcall Field Sie werden keinen Stapelüberlauf verursachen. An diesem Punkt schreiben Sie eine Schleife als rekursive Funktion und eine Entscheidung als Übereinstimmung. die tage von ifund whilesind nun geschichte.

Sobald Sie mit Backtracking in Sprachen wie PROLOG zu AI wechseln, ist alles rekursiv. Dies erfordert zwar ein anderes Denken als der imperative Code, aber wenn PROLOG das richtige Tool für das Problem ist, müssen Sie nicht mehr viele Codezeilen schreiben, und die Anzahl der Fehler kann sich drastisch verringern. Siehe: Amzi-Kunde eoTek

Um zu Ihrer Frage zurückzukehren, wann Sie die Rekursion verwenden sollten; Ein Weg, wie ich die Programmierung betrachte, ist mit Hardware an einem Ende und abstrakten Konzepten am anderen Ende. Je näher das Problem an der Hardware liegt, desto mehr denke ich in imperativen Sprachen mit ifund whileje abstrakter das Problem, desto mehr denke ich in Hochsprachen mit Rekursion. Wenn Sie jedoch anfangen, einfachen Systemcode und dergleichen zu schreiben und dessen Gültigkeit überprüfen möchten, sind Lösungen wie Theorembeweiser nützlich, die stark auf Rekursion beruhen.

Wenn Sie sich die Jane Street ansehen, werden Sie feststellen, dass sie die funktionale Sprache OCaml verwenden . Obwohl ich keinen ihrer Codes gesehen habe, denken sie nach dem Lesen dessen, was sie über ihren Code erwähnen, sicherlich rekursiv.

BEARBEITEN

Da Sie nach einer Liste von Verwendungszwecken suchen, gebe ich Ihnen eine grundlegende Vorstellung davon, wonach Sie im Code suchen müssen, und eine Liste von grundlegenden Verwendungszwecken, die hauptsächlich auf dem Konzept des Katamorphismus basieren, das über die Grundlagen hinausgeht.

Für C ++: Wenn Sie eine Struktur oder eine Klasse definieren, die einen Zeiger auf dieselbe Struktur oder Klasse enthält, sollte die Rekursion für Traversal-Methoden berücksichtigt werden, die die Zeiger verwenden.

Der einfache Fall ist eine unidirektionale verknüpfte Liste. Sie würden die Liste beginnend am Anfang oder Ende verarbeiten und dann die Liste mit den Zeigern rekursiv durchlaufen.

Ein Baum ist ein weiterer Fall, in dem häufig eine Rekursion verwendet wird. So sehr, dass Sie sich fragen sollten, warum, wenn Sie eine rekursionslose Durchquerung von Bäumen sehen? Es ist nicht falsch, aber etwas, das in den Kommentaren vermerkt werden sollte.

Häufige Verwendungen der Rekursion sind:

• Sortierung
• suche
• Karte
• falten
• Filter

Um Ihnen einen Anwendungsfall zu geben, der weniger geheimnisvoll ist als die in den anderen Antworten angegebenen: Die Rekursion lässt sich sehr gut mit baumartigen (objektorientierten) Klassenstrukturen kombinieren, die aus einer gemeinsamen Quelle stammen. Ein C ++ Beispiel:

class Expression {
public:
    // The "= 0" means 'I don't implement this, I let my subclasses do that'
    virtual int ComputeValue() = 0;
}

class Plus : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() + right->ComputeValue(); }
}

class Times : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() * right->ComputeValue(); }
}

class Negate : public Expression {
private:
    Expression* expr;
public:
    virtual int ComputeValue() { return -(expr->ComputeValue()); }
}

class Constant : public Expression {
private:
    int value;
public:
    virtual int ComputeValue() { return value; }
}

Im obigen Beispiel wird die Rekursion verwendet: ComputeValue wird rekursiv implementiert. Damit das Beispiel funktioniert, verwenden Sie virtuelle Funktionen und Vererbung. Sie wissen nicht genau, was der linke und der rechte Teil der Plus-Klasse sind, aber es ist Ihnen egal: Es ist etwas, das seinen eigenen Wert berechnen kann, und das ist alles, was Sie wissen müssen.

Der entscheidende Vorteil des obigen Ansatzes besteht darin, dass sich jede Klasse um ihre eigenen Berechnungen kümmert . Sie trennen die verschiedenen Implementierungen aller möglichen Unterausdrücke vollständig voneinander: Sie kennen die Funktionsweise des anderen nicht. Dies erleichtert das Nachdenken über das Programm und macht es leichter, das Programm zu verstehen, zu warten und zu erweitern.

Das erste Beispiel, mit dem ich in meinem ersten Programmierkurs die Rekursion unterrichtete, war eine Funktion, mit der alle Ziffern in einer Nummer separat in umgekehrter Reihenfolge aufgelistet wurden.

void listDigits(int x){
     if (x <= 0)
        return;
     print x % 10;
     listDigits(x/10);
}

Oder so ähnlich (ich gehe hier aus der Erinnerung und teste nicht). Wenn Sie in höhere Klassen einsteigen, verwenden Sie außerdem eine Menge Rekursion, insbesondere in Suchalgorithmen, Sortieralgorithmen usw.

So mag es jetzt in der Sprache wie eine nutzlose Funktion erscheinen, aber es ist auf lange Sicht sehr, sehr nützlich.