Was ist der Unterschied zwischen "Rekursion" und "Selbstreferenz"?

8

Die Wikipedia-Artikel sind zu weit fortgeschritten, als dass ich sie verstehen könnte. Könnte mir bitte jemand eine einfache Erklärung geben?

Schädelpatrol
quelle
2
Sie sind nicht wirklich vergleichbare Begriffe. recursionbezieht sich auf eine Funktion, die sich selbst aufruft, während self-referencesich auf ein Objekt bezieht, das auf sich selbst verweist.
Jakob Weisblat
2
@GerryMyerson wäre es richtig zu sagen, Rekursionsaufrufe selbst; während sich Selbstreferenz auf sich selbst bezieht?
Schädelpatrol
1
@ Skullpatrol im Wesentlichen ja, aber ich glaube, Sie vermissen einen grundlegenden Unterschied - sie können nicht auf die gleiche Art von Dingen zutreffen.
Jakob Weisblat
1
Nein. Selbstreferenz bezieht sich auf ein Objekt, das sich selbst neu definiert (siehe Wikipedia-Artikel über OOP), wobei sich die Rekursion auf eine Funktion oder Methode bezieht, nicht auf ein Objekt.
Jakob Weisblat
4
@ Jake223 Ich weiß, woher Sie kommen, aber Sie könnten auch sagen, dass eine Struktur wie eine verknüpfte Liste rekursiv definiert ist (die Definition hat einen Basisfall und einen rekursiven Schritt), und es besteht kein Zweifel daran, dass rekursive Funktionen selbstreferenziell sind .
Caleb

Antworten:

14

Der Kontext der beiden Begriffe ist im Allgemeinen unterschiedlich.

Selbstreferenzierung erfolgt im Kontext von Daten - Sie haben einen Datentyp, der einen Verweis auf etwas vom gleichen Typ enthält.

Rekursiv ist im Kontext von Code - Sie haben eine Funktion oder Prozedur, die sich selbst aufruft.

Beispiel:

def factorial(n):
if n == 1:
    return 1
else:
    return n * factorial(n-1)
jmoreno
quelle
Hier sind die beiden Tag-Definitionen zum Stapelüberlauf: Rekursion in der Informatik ist eine Methode zur Problemlösung, bei der die Lösung eines Problems von Lösungen für kleinere Instanzen desselben Problems abhängt. Selbstreferenz ist die Fähigkeit eines Programms (oder eines logischen Satzes), sich entweder direkt oder indirekt auf sich selbst zu beziehen.
Schädelpatrol
Und für Tags scheint das ungefähr richtig zu sein. Sie möchten nicht in seltsame Eckfälle für ein Tag geraten. Und es geht wahrscheinlich auch um das Level, an das Sie jetzt denken möchten.
jmoreno
10

Hier ist eine rekursive Funktion (in C):

unsigned int fibonacci(unsigned int n)
{
    unsigned int result = 1;

    if (n > 1)
        result = fibonacci(n - 1) + fibonacci(n - 2);

    return result;
}

Diese beiden Aufrufe fibonacci()innerhalb der fibonacci()Funktion sind rekursive Aufrufe.

Hier ist eine selbstreferenzielle Datenstruktur :

struct ListNode {
    char *data;
    struct ListNode *next;
}

Das erste Element dataist nur ein Zeiger auf eine Art von Daten. Das zweite Element nextist ein Zeiger auf eine andere ListNodeStruktur. Wenn Sie zwei oder mehr ListNodeStrukturen haben, können Sie den nextZeiger von einer auf die Adresse einer anderen usw. setzen, und Sie haben dann eine verknüpfte Liste . Die Struktur ist selbstreferenziell, da sich die Definition der Struktur auf sich selbst bezieht. Wenn du wirklich verrückt werden willst, kannst du das tun:

struct ListNode *node = malloc(sizeof(struct ListNode));
node->data = someString;
node->next = node;

Jetzt haben Sie eine andere Art von Selbstreferenz - es ist nicht nur die Definition struct ListNode, die sich auf sich selbst bezieht ... Sie haben den nextZeiger gesetzt node, um auf sich nodeselbst zu zeigen. Dies ist eine zirkuläre verknüpfte Liste, die nur ein Element enthält. Süß, aber nicht sehr nützlich. Ich erwähne es, weil es eine Art Selbstreferenz ist, aber es ist nicht das, was Menschen normalerweise meinen, wenn sie über selbstreferenzielle Datentypen sprechen.

Caleb
quelle
1
Ist es richtig zu sagen, dass Rekursion ein Sonderfall der Selbstreferenz ist, bei dem das Objekt, auf das verwiesen wird (oder das aufgerufen wird), eine Funktion ist?
Schädelpatrol
2
Sicher könnte man sagen, dass ein rekursiver Aufruf eine Form der Selbstreferenz ist. Manchmal sind die Begriffe fast austauschbar, wenn auch nicht in Bezug auf Code. Zum Beispiel würden die meisten Leute "GNU" als "rekursives Akronym" bezeichnen, weil es für "GNU ist nicht Unix" steht, aber niemand würde sagen, dass Sie sich geirrt haben, wenn Sie es stattdessen als "selbstreferenzielles Akronym" bezeichnen.
Caleb
@Caleb Dies ist kein besonders gutes Beispiel, da List ein rekursiver Datentyp ist . Sie zeigen also tatsächlich ein weiteres Beispiel für Rekursion!
Andres F.
@AndresF. Können Sie ein Beispiel für eine selbstreferenzielle Datenstruktur geben, die kein rekursiver Datentyp ist? Quellen wie diese und diese verwenden den Begriff "selbstreferenziell" für Strukturen wie verknüpfte Listen, während andere "rekursiv" verwenden. Wenn meine Antwort nicht klar zwischen den Begriffen unterscheidet, liegt das daran, dass die Begriffe nicht genau synonym sind, aber eine sehr enge Bedeutung haben.
Caleb
@Caleb Ups, sorry. Wenn Sie sagen, dass sie eine sehr enge Bedeutung haben, dann stimmen wir zu und ich habe Sie missverstanden!
Andres F.
6

Es wird erwartet, dass Rekursionen, meistens nützliche, nach einer bestimmten Anzahl von Prozeduren in dem Sinne beendet werden, dass es einen Anfangswert gibt. es sei denn, Sie haben eine schlechte Rekursion, die nutzlos ist.

Selbstreferenzen sind an sich keine rekursiven Rekursionen, es kann jedoch gezeigt werden, dass sie rekursiv sind. In diesem Fall werden sie im Allgemeinen nie beendet.


quelle
5
Wenn Sie Rekursion als eine Konstruktion definieren, die über eine fundierte Beziehung übertragen wird, entspricht die Tatsache, dass eine Rekursion nicht endet, einer unendlich abnehmenden Sequenz - und daher ist die selbstreferenzielle "Rekursion" überhaupt keine Rekursion. Dies ist ähnlich wie ein Algorithmus erforderlich ist, um irgendwann anzuhalten.
5
Was ist mit dieser Aussage: "Dieser Satz hat fünf Wörter." Es ist selbstreferenziell, aber ich sehe keine nicht endende Rekursion. Ich denke auch nicht, dass Rekursion im Allgemeinen Selbstreferenz beinhalten muss. Wenn Sie eine rekursive C-Funktion in binären Maschinencode kompilieren, enthält der Maschinencode keine Selbstreferenz. Ich denke, das Beste, was Sie sagen können, ist, dass eine abschließende Selbstreferenz eine Möglichkeit ist, eine Rekursion zu definieren.
2
Ja, das ist meine Erklärung keineswegs perfekt. Ich versuche nur zu vereinfachen, falls "OP versucht, einige Selbstreferenzen als Wiederholungen zu interpretieren." Ich meine keineswegs, dass Selbstreferenzen immer nicht terminierende Rekursionen sind.
Ist es richtig zu sagen, dass Rekursion ein Sonderfall der Selbstreferenz ist, bei dem das Objekt, auf das verwiesen wird (oder das aufgerufen wird), eine Funktion ist?
Schädelpatrol
5

Rekursion impliziert Aktion.

Beispiele:

  • eine Funktion, die sich selbst aufruft
  • eine Regex, die eine * oder + (dh sich wiederholende) Übereinstimmung ausführt

Technisch gesehen sollte die Rekursion einen Exit-Status haben, dies ist jedoch keine Voraussetzung.

Selbstreferenz impliziert Struktur.

Ex. Eine Instanzmethode, die auf das Objekt verweist, an das sie angehängt ist.

Evan Scholle
quelle
2

Für die Rekursion muss etwas verarbeitet werden, indem derselbe Prozess aufgerufen wird (häufig mit unterschiedlichen Parametern). Obwohl Sie häufig Funktionen verwenden und diese Funktionen sich selbst aufrufen, treten sie technisch in einen neuen Schritt ein, der zufällig wie der Ort aussieht, von dem sie gerade gekommen sind.

Selbstreferenz bedeutet, dass sich etwas auf sich selbst bezieht. Klassen können mithilfe von selbstreferenziell sein this, aber das ist nicht sinnvoll rekursiv.

Telastyn
quelle
Rekursion erfordert also einen Prozess durch Aufrufen desselben Prozesses, während Selbstreferenz das "Aufrufen von sich selbst" ist?
Schädelpatrol
@ Skullpatrol - nein. Selbstreferenz erfordert keinerlei Berufung.
Telastyn
Rekursion erfordert also einen Prozess durch Aufrufen desselben Prozesses, während Selbstreferenz die "Referenzierung von sich selbst" ist?
Schädelpatrol