Rekursion in sortierter doppelter verketteter Listeneinfügung

Question

Ich bin zu den Datenstrukturen und zum Rekursionskonzept neu. Ich habe Mühe zu verstehen, warum und wer die Rekursion in diesem Konzept verwenden konnte. Ich habe diesen Code in den Foren gefunden und konnte das Konzept nicht wirklich verstehen. Für einen einfachen Fall von 2 1 3 4, wenn jemand die Iterationsschritte erklären kann, wird dies in meinem Interesse sehr geschätzt werden. Hier

ist der Link für Hacker Rang: https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list

Node SortedInsert(Node head,int data) { 
    Node n = new Node(); 
    n.data = data; 
    if (head == null) { 
     return n; 
    } 
    else if (data <= head.data) { 
     n.next = head; 
     head.prev = n; 
     return n; 
    } 
    else { 
     Node rest = SortedInsert(head.next, data); 
     head.next = rest; 
     rest.prev = head; 
     return head; 
    } 
} 

Answer 1

Rekursion: Rekursion bedeutet eine Funktion sich selbst aufruft. Es wird als einfache Methode zum Speichern von Statusinformationen für Algorithmen verwendet, die das Speichern mehrerer Zustände (normalerweise eine große Anzahl von Zuständen) und das Abrufen in umgekehrter Reihenfolge erfordern. (Es gibt alternative Techniken, die professioneller und weniger anfällig für Speicherprobleme sind, z. B. die Verwendung eines Stack-Objekts zum Speichern des Programmstatus).

Dieses Beispiel ist schlecht, aber typisch für die Rekursion. Ja, Sie können eine verknüpfte Liste mit Rekursion durchlaufen, aber es gibt absolut keinen Grund dafür. Eine Schleife wäre angemessener. Dies dient nur dazu, zu demonstrieren, wie Rekursion funktioniert. Also, um Ihre Frage zu beantworten "Warum?" Es ist einfach so, dass Sie das Konzept lernen und es später in anderen Algorithmen verwenden können, die es tatsächlich sinnvoll macht.

Rekursion ist nützlich, wenn Sie anstelle einer verketteten Liste einen Baum haben, in dem jeder Knoten auf mehrere andere Knoten zeigt. In diesem Fall müssen Sie Ihren Status speichern (auf welchem ​​Knoten Sie sich befinden und welchen Unterknoten Sie zuletzt aufgerufen haben), so dass Sie einen der verknüpften Knoten durchlaufen können, dann zurückkehren und zum nächsten Knoten wechseln können.

Sie fragte auch "wie". Wenn sich eine Funktion selbst aufruft, werden alle ihre Variablen gespeichert (auf dem Programmstapel) und neue werden für die nächste Iteration ihrer selbst erstellt. Wenn dieser Aufruf dann zurückkehrt, kehrt er zu der Stelle zurück, von der er aufgerufen wurde, und die vorherige Gruppe von Variablen wird geladen. Dies unterscheidet sich sehr von einem "Sprung" oder einer Schleife irgendeiner Art, bei der jedes Mal die gleichen Kopien der Variablen verwendet werden. Durch Rekursion gibt es bei jedem Aufruf eine neue Kopie jeder lokalen Variablen. Dies gilt selbst für die Variable "data" im Beispiel, die sich niemals ändert (daher eine Ineffizienz).