Was ist die Beziehung zwischen Rekursion und Beweis durch Induktion?
Sagen wir fn(n) ,
Rekursion ist fn(n) ruft sich selbst auf, bis meet base condition ;
Induktion ist, wenn base condition erfüllt ist, versuchen zu beweisen (base case + 1) ist auch korrekt.
Es scheint, Rekursion und Induktion sind in anderer Richtung. Eine beginnt von n bis base case , die andere beginnt von base case bis infinite .
Kann jemand die Idee im Detail erklären?
Rekursion und Induktion sind sehr ähnlich! Dies wird offensichtlich, wenn Sie eine Programmiersprache mit abhängigen Typen wie Agda verwenden, aber ohne sie auch etwas demonstriert werden kann.
Bedenken Sie, dass aufgrund der Curry-Howard-Korrespondenz Typen Vorschläge und Programme sind Beweise. Wenn Sie eine Funktion vom Typ Nat -> Nat schreiben (ich verwende die Haskell-Notation), versuchen Sie zu beweisen, dass Ihr Programm bei einer natürlichen Zahl endet und eine andere natürliche Zahl erzeugt. Jetzt haben wir vielleicht eine Definition wie folgt:
ist sowohl eine rekursive Definition von f als auch ein induktiver Beweis für dessen Beendigung gleichzeitig!
Sie können es als Beweis auf folgende Weise lesen:
Lassen Sie uns beweisen, dass f x für jedes x endet.
f 0 per Definition konstant, so dass es endet. f n terminiert, endet auch f (1 + n) (weil alle aufgerufenen Funktionen enden). Da die Rekursion nicht auf eine Funktion beschränkt ist, die ihren Zähler dekrementiert, ist die Induktion auch nicht auf natürliche Zahlen beschränkt. Es gibt auch strukturelle Induktion, die der strukturellen Rekursion entspricht, die beide in Mathematik / Programmierung sehr populär sind. Diese werden verwendet, wenn man versucht, Dinge zu beweisen / Funktionen auf komplexeren Datenstrukturen (Listen / Bäume / etc.) Zu definieren.
Nun, um Ihre Bedenken bezüglich der "Richtung" der Rekursion / Induktion anzugehen. Hier ist es hilfreich, "Richtung der Nachfrage" und "Richtung der Versorgung" zu betrachten, die entgegengesetzt sind.
Wenn Sie eine rekursive Funktion definieren, fließt der Bedarf (Methodenaufrufe) von größeren Werten in den Basisfall. Auf der anderen Seite fließt die Versorgung (die Rückgabewerte) vom Basisfall zu den größeren Parameterwerten. "Definiertheit" ist eine andere Art, über das Angebot nachzudenken. Es beginnt bei dem Basisfall und breitet sich über den rekursiven Fall nach unendlich aus.
Wenn Sie jetzt induktive Beweise machen, sind Theoreme Ihre Versorgung, während Ziele Ihre Forderung sind. Sie können einen Theorem T 0 aus dem Basisfall machen und dann zu einem großen T n übergehen, das Sie gerne mit dem Induktionsfall verwenden: Ihr Vorrat fließt von 0 bis unendlich. Wenn Sie nun ein Ziel G n haben, können Sie mit dem induktiven Schritt kleinere Ziele G (n-k) daraus machen, bis Sie Null erreichen. Auf diese Weise geht Ihre Anforderung von n auf 0.
Wie Sie sehen, ist die Versorgungsrichtung in beiden Fällen "nach unendlich" und die Richtung der Nachfrage ist in beiden Fällen "auf Null".
Sie können auch die scheinbare Reihenfolge in den Beschreibungen von Induktion und Rekursion umkehren, ohne ihre Bedeutung zu ändern:
Induktion ist, wenn Sie beweisen müssen, dass P n gilt, müssen Sie zunächst Ihr Ziel auf P 0 reduzieren, indem Sie wiederholt den induktiven Fall anwenden und dann das resultierende Ziel mit dem Basisfall beweisen.
Ähnlich ist die Rekursion, wenn Sie zuerst einen Basisfall definieren und dann die weiteren Werte in Bezug auf die vorherigen definieren. Sehen Sie, die Richtungen werden leicht vertauscht!
Tags und Links recursion type-theory induction