Haben "induktiv" und "rekursiv" sehr ähnliche Bedeutungen?

11

Bedeuten "induktiv" und "rekursiv" sehr ähnlich?

Wenn es beispielsweise einen Algorithmus gibt, der einen n-dim-Vektor durch Bestimmen seiner ersten k + 1-Komponenten auf der Grundlage seiner ersten k-Komponenten bestimmt und mit der ersten Komponente initialisiert wird, würden Sie ihn als rekursiv oder induktiv bezeichnen? Ich habe "rekursiv" verwendet, aber heute hat es jemand "induktiv" gesagt.

Tim
quelle
Dieser Artikel über Induktion und Rekursion fasst es gut zusammen, aber das Wesentliche ist, dass sie eng miteinander verwandt sind. Ein mathematischer Induktionsbeweis kann als rekursiver Algorithmus geschrieben werden.
Merbs
Induktiv bedeutet normalerweise rekursiv von nach , also ist rekursiv das allgemeinere Adverb. nn+1
Yuval Filmus
Was für rekursiv ist nicht induktiv, @YuvalFilmus?
Tim
@ YuvalFilmus: Das ist eine sehr begrenzte Vorstellung von induktiv.
Dave Clarke
Für mich bedeuten sie dasselbe aus dem Zusammenhang heraus. In einem bestimmten Kontext können sie verschiedene Bedeutungen haben.
Gilles 'SO - hör auf böse zu sein'

Antworten:

6

Nein , aber nicht aus den Gründen, die andere Leute angegeben haben. Der Unterschied zwischen Rekursion und Induktion besteht nicht darin, dass die Rekursion "von oben nach unten" und die Induktion "von unten nach oben" ist. Die Induktion ist isomorph zu etwas, das als "primitive Rekursion" bezeichnet wird, aber im Allgemeinen ist die Rekursion streng stärker als die Induktion .

Die Unterscheidung zwischen Top-Down und Bottom-Up ist trivial - jedes primitive rekursive "Top-Down" -Programm kann mechanisch in etwas "Bottom-Up" umgewandelt werden. Tatsächlich kann jeder Beweis durch Induktion in ein rekursives Programm umgewandelt werden. Wenn Sie im Rahmen der Berechnung induktiver Konstruktionen beweisen möchten, dass jede natürliche Zahl froopulös ist, schreiben Sie sie als eine Funktion, die einen Beweis dafür konstruiert, dass n froopulös ist, indem Sie einen rekursiven Aufruf ausführen, um einen Beweis zu konstruieren, dass n- Ich bin froopulous.

Der Schlüsselfaktor der Induktion ist, dass Dinge in Form kleinerer Dinge definiert werden und nach endlich vielen Schritten "den Boden erreichen". Natürliche Zahlen sind induktiv, da jede natürliche Zahl entweder 0 oder der Nachfolger einer kleineren natürlichen Zahl ist. Listen sind induktiv, da jede Liste entweder leer ist oder in ein Element und eine kleinere Liste unterteilt ("entfaltet") werden kann.

Manchmal werden rekursive Programme jedoch nicht in Bezug auf kleinere Dinge geschrieben. Nehmen Sie zum Beispiel diese Collatz-Funktion:

fun collatz(n) 
   if n <= 1
      return 0;
   else if n % 2 == 0
     return 1 + collatz(n / 2)
   else
     return 1 + collatz(3 * n + 1)
end

Diese Funktion geht weder von oben nach unten noch von unten nach oben und ist daher über die natürlichen Zahlen nicht induktiv.

Es mag einen Befehl geben, dies induktiv zu behandeln, aber für die meisten Dinge gibt es einfach keinen Weg. Funktionen über unendliche Streams sind ein gutes Beispiel. In der Tat sind Streams das prototypische Beispiel eines "koinduktiven" Typs.

Bob Harpers "Praktische Grundlagen für Programmiersprachen", kostenlos online verfügbar, bietet eine schöne Einführung in induktive, koinduktive und rekursive Typen.

James Koppel
quelle
2

Für mich ist es meistens eine Frage des Standpunkts. Wenn ich Objekte basierend auf einem kleineren definiere, mache ich das induktiv, also von unten nach oben. Wenn ich ein Problem löse, indem ich es in kleinere Teile zerlege, die auf die gleiche Weise gelöst werden, nenne ich es Rekursion, das heißt von oben nach unten.

(bearbeiten) PS. Eine ähnliche Frage finden Sie in unserer Schwesterabteilung für Mathematik, Rekursive vs. induktive Definition . Ich zitiere aus der Antwort von Carl Mummert:

Meine beste Beschreibung ist, dass "induktive Definition" häufiger vorkommt, wenn wir eine Menge von Objekten "aus dem Nichts" definieren, während "rekursive Definition" häufiger vorkommt, wenn wir eine Funktion für eine bereits vorhandene Sammlung von Objekten definieren.

Aber noch wichtiger:

Es lohnt sich nicht, den Schlaf zu verlieren

Hendrik Jan.
quelle
also "rekursion = teilen und erobern", welche zuerst von oben nach unten und dann von unten nach oben?
Tim
1

Nein, sie sind nicht gleich. Und Sie haben Recht (ich gehe von dem Algorithmus aus, den Sie beschreiben): Er ist rekursiv.

Der Grund ist die Definition beider Wörter, die Sie in einem Wörterbuch oder in Wikipedia lesen können.

Bei der Induktion (unter der Annahme einer „mathematischen Induktion“) geht es speziell darum zu beweisen, dass alle Fälle eines Arguments wahr sind.

Bei der Rekursion geht es speziell um einen Prozess, der möglicherweise innerhalb desselben Prozesses auf irgendeine Weise wiederholt wird.

RE: Antworten anderer Leute:

Nachdem ich die Antworten anderer gesehen habe, kann ich verstehen, warum es Verwirrung gibt: Bei der Definition von Datenstrukturen, Funktionen und Sprachen scheinen einige Theoretiker verwirrend 'induktiv' und 'rekursiv' zu verwenden (siehe Kommentare zu dieser Frage). Ich denke nicht, dass Koppels Antwort (selbst bei den derzeit höchsten Stimmen) diese Verwirrung wirklich widerspiegelt. Da es sich um einen Algorithmus handelt, würde ich nicht sagen, dass es "induktive Algorithmen" gibt. Ich denke, das ist eine unnötige Kategorisierung.

Tom
quelle
Bei der Induktion geht es nicht nur um Beweise. Sie verwenden es auch die ganze Zeit, um rekursive Strukturen (Datenstrukturen, Sprachen usw.) induktiv zu definieren
Hugomg
@missingno Bitte geben Sie eine Quelle für diese Definition an.
Tom
Ein Beispiel, an das ich denken könnte, ist hier : "Die Sprache von \ mathcal {L}, auch bekannt als ihre Menge von Formeln, wohlgeformten Formeln oder wffs, wird induktiv durch die folgenden Regeln definiert:"
hugomg
@missingno, was zu dieser Wikipedia- Seite führt, auf der ich denke, dass das Wort "induktiv" redundant und verwirrend verwendet wird und im Wesentlichen als "rekursiv" verwendet wird
Tom
Bitte lassen Sie mich nicht nach weiteren Beispielen suchen. Auch wenn Sie vielleicht nicht damit einverstanden sind, ist es definitiv eine sehr verbreitete Redewendung und Sie können sie auch in vielen Büchern finden, wenn Sie danach suchen. Und es ist nicht so, dass jemand den Wikipedia-Artikel absichtlich bearbeitet hat, um meinen Standpunkt zu beweisen ...
Hugomg