Looking for recursion Keywords? Try Ask4Keywords

RecursionErste Schritte mit Rekursion


Bemerkungen

Rekursion bezieht sich auf etwas, das in sich selbst definiert ist. Im Rahmen der Programmierung werden entweder Funktionen verwendet, die sich selbst aufrufen, oder rekursive Typen.

Rekursive Funktionen

Eine rekursive Funktion besteht aus zwei Teilen:

  • Ein oder mehrere Basisfälle
  • Ein rekursiver Schritt

Da eine rekursive Funktion sich selbst aufruft, könnte die Zeichenfolge der Funktionsaufrufe für immer andauern. Um sicherzustellen, dass die Funktion beendet wird, müssen Basisfälle eingeschlossen werden. Diese geben der Funktion an, wann ein Wert zurückgegeben werden soll, anstatt einen anderen rekursiven Aufruf auszuführen. Normalerweise prüfen rekursive Funktionen ihre Eingaben anhand des Basisfalls und kehren zurück, wenn der Basisfall erreicht wurde. Wenn der Basisfall nicht erreicht wurde, geht die Funktion zum rekursiven Schritt über.

Der rekursive Schritt ist, wann eine Funktion sich selbst aufruft. Viele rekursive Funktionen geben Berechnungen für das Ergebnis des rekursiven Aufrufs zurück. Das Beispiel der Fibonacci-Sequenz zeigt dies. Diese Funktion ruft sich selbst zweimal auf und gibt dann die Summe der Ergebnisse dieser Aufrufe zurück

Eine häufige Verwendung für die Rekursion ist das Navigieren und Durchführen von Berechnungen in großen Datenstrukturen wie Bäumen und Diagrammen. Dies funktioniert gut, weil die Rekursion das Problem unterbricht, um kleinere Probleme zu lösen, und auf diesen Lösungen aufbaut, um das größere Problem zu lösen. Eine weitere häufige Verwendung für die Rekursion ist das Durchführen iterativer Operationen (Schleifen) in Sprachen (normalerweise funktionalen Sprachen), die keine eingebauten Schleifenstrukturen aufweisen.

Rekursive Typen

Ein rekursiver Typ ist ein Typ, dessen Werte sich aus Werten desselben Typs zusammensetzen oder anders formuliert: Ein rekursiver Typ wird in Bezug auf sich selbst definiert. In einem Beispiel ist eine Liste ein rekursiver Typ, da jede Untermenge der Liste selbst eine Liste ist. Bäume sind ein weiteres Beispiel. Wenn Knoten aus einem Baum entfernt werden, ist das verbleibende Konstrukt noch ein Baum.

Formal wird die Menge von Werten eines rekursiven Typs T durch eine rekursive Mengengleichung in der Form definiert:

T = ... T ...

Eine rekursive Mengengleichung kann viele Lösungen haben, aber eine solche Gleichung hat immer die kleinste Lösung, die eine Untermenge jeder anderen Lösung ist.

Als praktisches Beispiel betrachten Sie diese Haskell-Definition für einen Listentyp.

data List a = Nil | Cons a (List a)

Das bedeutet, dass eine Liste von a entweder eine leere Liste oder eine Cons-Zelle ist, die ein ' a ' (den "Kopf" der Liste) und eine andere Liste (den "Schwanz") enthält.

Überprüfung auf Palindrome mit Rekursion in C ++

// Checks a string to see if it is a palindrome
bool function IsPalindrome(string input) {
    if (input.size() <= 1) {
        return true;
    }
    else if (input[0] == input[input.size() - 1]) {
        return IsPalindrome(input.substr(1,input.size() - 2));
    }
    else {
        return false;
    }
}
 

Erstellen einer Hierarchiestruktur mit Rekursion [JavaScript]

var directories = [
  {name: 'users' , parent : null },
  {name: 'distalx' , parent : 'users' },
  {name: 'guest' , parent : 'users' },
  {name: 'shared' , parent : 'users' },
  {name: 'documents' , parent : 'distalx' },
  {name: 'music' , parent : 'distalx' },
  {name: 'desktop' , parent : 'distalx' },
  {name: 'javascript' , parent : 'documents' },
  {name: 'funjs' , parent : 'documents' },
  {name: 'functions' , parent : 'documents' }
]


var sortDirectories= function(directories, parent){
  let node = [];
  directories
  .filter(function(d){ return d.parent === parent})
  .forEach(function(d){
    var cd = d;
    cd.child = sortDirectories(directories, d.name);
    return node.push(cd);
  })
  return node;
}

var results = sortDirectories(directories, null);
JSON.stringify(results, null, ' ');

 

Ausgabe


[{
  "name": "users",
  "parent": null,
  "child": [
      { "name": "distalx",
        "parent": "users",
        "child": [
            { "name": "documents",
              "parent": "distalx",
              "child": [
                  { "name": "javascript",
                    "parent": "documents",
                    "child": []
                  },
                  { "name": "funjs",
                    "parent": "documents",
                    "child": []
                  },
                  { "name": "functions",
                    "parent": "documents",
                    "child": []
                  }
              ]
            },
            { "name": "music",
              "parent": "distalx",
              "child": []
            },
            { "name": "desktop",
              "parent": "distalx",
              "child": []
            }
        ]
      },
      {
        "name": "guest",
        "parent": "users",
        "child": []
      },
      {
        "name": "shared",
        "parent": "users",
        "child": []
      }
  ]
}]
 

Fibonacci-Sequenz Verwenden der Rekursion in Javascript

// Returns the nth number in the Fibonacci sequence
function fibonacci(n) {
    if (n === 1 || n === 0) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
 

Holen Sie sich alle Kombinationen von Elementen aus Arrays in Javascript

function getCombinations(params, combinationsResults){
    if(params.length == 0) return combinationsResults;
    var head = params[0];
    var tail = params.slice(1);
    var combinationsResultsCurrent = [];
    if(Array.isArray(head)){
        _.uniq(head).forEach(function(item){
            if(combinationsResults.length == 0){
                combinationsResultsCurrent.push(item);
            } else {
                combinationsResults.forEach(function(previousResultItem){
                    combinationsResultsCurrent.push(previousResultItem.concat([item]));
                });
            }
        });
    } else {
        if(combinationsResults.length == 0){
            combinationsResultsCurrent.push(head);
        } else {
            combinationsResults.forEach(function(previousResultItem){
                combinationsResultsCurrent.push([previousResultItem].concat([head]));
            });
        }
    }
    return getCombinations(tail, combinationsResultsCurrent);
 

Beispiel:

Angenommen, wir haben eine Abfrage mit IN-Kalibern:

SELECT * FROM custom_table WHERE user_id = 'user1' AND location IN ('home', 'work', AND date IN ('2017-01-10', '2017-01-11'))
 

AND möchte alle Kombinationen von Parametern erhalten, um Abfragen ohne IN-Bedingungen zu generieren:

SELECT * FROM custom_table WHERE user_id = [value for user_id] AND location = [value for possible location] AND date = [value for possible date]
 

Um alle möglichen Kombinationen von Parametern für äquivalente Abfragen zu erhalten, können Sie die Funktion oben ausführen:

var params = ['user1', ['home', 'work'], ['2017-01-10', '2017-01-11']];
 

Suchen nach einem Wert in einem binären Suchbaum mit Rekursion in C / C ++

Struktur für BST-Knoten (Binary Search Tree):

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

Suchalgorithmus

// Check if a value exists in the tree
bool BSTSearch(node * current, int value)
{
    if (current->data == value)
    {
        return true;
    }
    else if (current->data < value)
    {
        if (current->left == NULL)
        {
            return false;
        }
        else
        {
            return BSTSearch(current->left, value);
        }
    }
    else if (current->data > value)
    {
        if (current->right == NULL)
        {
            return false;
        }
        else
        {
            return BSTSearch(current->right, value);
        }
    }
}