Tool das Iteration in Rekursion (oder umgekehrt) umwandelt

Was meint ihr?

Ist es möglich ein Tool zu programmieren, das als Eingabe eine iterative Lösung eines Algorithmuses (C++) nimmt und daraus eine rekursive Lösung generiert? (oder umgekehrt, Rekursion -> Iteration)

Christoph

Ich bin mir nicht sicher:
Irgendwie erinnert mich das an das Problem des Algorithmus, der mir von einem anderen Algorithmus sagt, ob dieser in endlicher Zeit terminiert.

Kommt wahrscheinlich drauf an.
Wenn du z.B. diesen rekursiven Algorithmus hast:

int Summe(int s)
{
  return s ? Summe(s - 1) + s : 0;
}

Soll das Programm folgendes ausspucken, also die Rekursion komplett beseitigen:

int Summe(int s)
{
  return (s * (s + 1)) / 2;
}

Oder folgendes?

int Summe(int s)
{
  for(int x = 0; s > 0; x += s--);
  return x;
}

Oder was ganz anderes? Man könnte sich auch eine iterative Lösung vorstellen, die einen simulierten Stack benutzt auf der Basis einer Stack-Klasse. Aber ob das besser ist als der echte Stack? Zählt das dann überhaupt schon als "beseitigte Rekursion"?

Probier doch einfach mal sowas zu schreiben!

Nein das ist nicht möglich.

Es ist nichtmal möglich ein Tool zu schreiben, das einen Algorithmus (in welcher Algorithmendarstellung und Kodierung auch immer) aufnimmt und für diesen entscheidet ob er eine rekursive oder iterative Funktion implementiert.
Bildet man nämlich die Menge aller rekursiven Funktionen folgt direkt aus dem "Satz von Rice", dass nicht entscheidbar ist ob ein beliebiger gegebener Algorithmus in dieser Menge ist.

Für ein Tool, welches einen rekursiven Algorithmus in einen Iterativen umwandelt wäre es aber notwendig die Stellen zu finden, an denen die rekursiven Aufrufe stattfinden. Könnte man diese Stellen finden, wäre aber auch die Fragestellung Rekursiv-oder-Iterativ entscheidbar. -> Widerspruch zu oben.

Umgekehrt kann ein Tool für die Abbildung Iterativ->Rekursiv auch nicht existieren. Selbige Argumentation: Könnte man den für die eigentliche Iteration verantwortliche Teil des Algorithmus ausfindig machen, was für die Umwandlung direkte Voraussetzung ist, wäre wieder entscheidbar ob Rekursiv oder Iterativ. -> Widerspruch

In direktem Bezug auf C++ mag es etwas seltsam klingen, dass es unmöglich ist zu entscheiden, ob ein darin implementierter beliebiger Algorithmus rekursiv ist. Schließlich müsste man nur den Code nach dem Namen der Funktion parsen und schon hätte man die Eintrittsstellen in die Rekursion.

Nur kann zum einen eine Rekursion indirekt über mehrere andere Funktionen hinweg geschehen und zum anderen kann eine Rekursion bestimmt auch mit wilden Speicherhacks ausgelöst werden. Somit wird die Sache beliebig kompliziert und sogar teilweise unmöglich.

Gruß, space

Gerard

klar ist das möglich, alles was ein mensch kann kann theoretsich auch ein pc es ist nur eine frage des aufwands.
der aufwand wird nicht klein sein bei den ganzen irrwegen in der c++ syntax und das ergebnis wird nicht so schön wie vom menschen

peterchen

Prinzipiell kannst du mit der Hilfe eines Stacks einen rekursiven Algorithmus in einen iterativen umwandeln - z.B. wenn du auf einer Architektur arbeitest, die Rekursion nicht unterstützt. Andererseits ist das noch keine "echte iterative alternative", sondern die "Fortsetzung von Rekursion mit anderen Mitteln".

Jester

Gerard schrieb:

klar ist das möglich, alles was ein mensch kann kann theoretsich auch ein pc es ist nur eine frage des aufwands.
der aufwand wird nicht klein sein bei den ganzen irrwegen in der c++ syntax und das ergebnis wird nicht so schön wie vom menschen

Das mag zwar so sein... wobei man darüber auch diskutieren könnte. Aber es gibt Probleme, die sind auch für Menschen nicht entscheidbar, und zwar mathematische/algorithmische Probleme bei denen nachgewiesen ist, daß sie nicht entscheidbar sind.

Bashar

Die Erkenntnis, dass man nicht für beliebige Programme entscheiden kann, ob sie rekursiv oder iterativ ablaufen, bringt uns doch an der Stelle überhaupt nichts. Real existierende Programme bilden schließlich nur eine verschwindende Teilmenge aller prinzipiell möglichen Programme. Wobei, das unterstelle ich hier mal, nur ein noch viel verschwindend kleinerer Anteil realer Programme in einem Stil geschrieben ist, der es unmöglich macht, diese Entscheidung zu treffen.

klar ist das möglich, alles was ein mensch kann kann theoretsich auch ein pc es ist nur eine frage des aufwands.

Ein Mensch kann es für beliebige Algorithmen und Funktionen auch nicht. Und das sind nicht nur exotische Ausnahmefälle.

Die Erkenntnis, dass man nicht für beliebige Programme entscheiden kann, ob sie rekursiv oder iterativ ablaufen, bringt uns doch an der Stelle überhaupt nichts.

Doch die bringt uns weiter. Aus ihr folgt direkt, dass ein solches allgemeines Tool unmöglich ist. Allgemeine Frage, allgemeine Antwort.

So könntest du auch die ganze Theoretische Informatik und Berechenbarkeitstheorie bis hin zum Unvollständigkeitssatz anzweifeln. Das sind bzw. da werden nur solch allgemeine (unentscheidbarkeits) Aussagen gemacht.

Oder bist du vielleicht auch der Meinung, dass das Halteproblem prinzipiell lösbar ist und man die Ausnahmen einfach ignorieren sollte weil sie angeblich sowieso nie bis selten vorkommen ?

Wundert mich eigentlich, dass grade von dir (Bashar) ein solcher Einwand kommt.

Jester

Naja, ganz unbegründet ist Bashars Einwurf auch nicht. Wenn wir uns auf eine geeignete Teilmenge einigen, dann wird es schon deutlich leichter das zu entscheiden.

Und zwar auf Funktionen die, wenn sie rekursiv sind sich selbst direkt aufrufen. Das ist zwar immer noch nicht 100% entscheidbar, aber wenn wir unsere Definition noch soweit anpassen, daß wir sagen, wenn in einer Funktion ein Aufruf ihrer selbst steht, dann ist die Funktion rekursiv, dann wird es mit einem mal sehr leicht entscheidbar.
Man muß ja nur den Text durchlesen und nachschauen, ob die Funktion aufgerufen wird.

Gut, warum diese Einschränkung? Und warum so?

Also, den direkten Rekursionsaufruf, weil man es durch durchlesen der Funtkion ganz einfach nachschauen kann. Man müßte halt noch prüfen, daß keine andere überladene Funktion aufgerufen wird, aber das kann der Compiler auch. Also ist es möglich.

Warum die Definition, daß es rekursiv ist, wenn der Aufruf im Text vorkommt?

void CallMe()
{
bool DoIt = // Code

if(DoIt) CallMe()
}

Es ist nicht sicher, ob DoIt jemals wahr wird (es ist nicht entscheidbar). Aber in den meisten Fällen wird so eine Rekursion, die keine ist nicht auftreten, das wäre dann ja ein Programmierfehler... und die Programme verifizieren wäre vielleicht doch ein noch größerer Aufwand.

Auf diese Art und Weise erhalten wir jedenfalls mal eine Definition von Rekursion, bei der entscheidbar ist, ob die Funktion rekursiv ist oder nicht.

Aber wie man die jetzt auflösen könnte... ist mir ein Rätsel. Aber das ist wenn ich mich recht entsinne auf jeden Fall berechenbar.

MfG Jester

Bashar

space:

Doch die bringt uns weiter. Aus ihr folgt direkt, dass ein solches allgemeines Tool unmöglich ist. Allgemeine Frage, allgemeine Antwort.

Wie wärs mit Allgemeine Frage - Spezielle Antwort? Wenn ein Problem sich im Allgemeinen als unlösbar herausstellt, ist das kein Grund, die Arme zu verschränken und sich zurückzulehnen. Es kann ja im speziellen Fall immer noch zu lösen sein. Beispielsweise ist Tail Call Elimination eine Form, Rekursion in Iteration umzuwandeln.

Die Wortwahl "Tool" impliziert dabei, dass es um praktisch vorkommende Probleme geht, die auch mal zulassen, dass keine Lösung gefunden wird. Wissenschaftlich würde man dagegen vielleicht "allgemeingültiges Verfahren" sagen.

Oder bist du vielleicht auch der Meinung, dass das Halteproblem prinzipiell lösbar ist und man die Ausnahmen einfach ignorieren sollte weil sie angeblich sowieso nie bis selten vorkommen ?

Kommt drauf an wie man Lösung definiert. Das Halteproblem ist unlösbar, wenn man für jedes mögliche Eingabeprogramm eine eindeutige Entscheidung fordert. Was, wenn ich diese Forderung fallenlasse und sage, dass die drei Antworten Ja, Nein und "Weiß nicht" zugelassen sind?

Jester

Das kann man so nicht beantworten...
Du müßtest erst definieren, wann welche Antwort kommt.
Je nachdem kann es entscheidbar sein oder auch nicht.

Bashar

Jester schrieb:

Du müßtest erst definieren, wann welche Antwort kommt.

Ich dachte da sei offensichtlich. JA und NEIN, wenn das Programm aufgrund was für Berechnungen auch immer zu einem eindeutigen Schluss kommt, und WEISS NICHT, wenn es das -- aus was für Gründen auch immer -- nicht tut.

Jester

Das Problem ist doch, ab wann soll das Programm denn jetzt sagen weiß nicht?

Man könnte ja das Programm einfach laufen lassen, wenn es terminiert geben wir ja aus. Problem, was wenn es lange dauert. Ist das dann ein weiß nicht, oder ein nein?

Wie entscheidet das Programm, ob es was rauskriegt oder nicht?
Und nein, die Ausgabe ist auch nicht offensichtlich:
return WEISS_NICHT;
wäre wohl eine korrekte Implementierung, so wie Du das beschrieben hast.

Genau da hängt es nämlich, wie entscheidet das Programm, ob es was weiß oder nicht?

Bashar

Vielleicht genauso wie ein Mensch das machen würde. Oder hast du noch nie eine Endlosschleife gesehen? Ein Aufgeben kann aus verschiedensten Gründen passieren. Vielleicht hat es eine bestimmte Schwelle an eigenem Resourcenverbrauch (Speicher oder Rechenzeit) überschritten.

Wenn man das zu überprüfende Programm einfach simulativ ablaufen lassen würde, könnte man natürlich immer nur JA oder WEISS NICHT als Ergebnis erhalten.

Pauschal WEISS NICHT zurückzugeben wär natürlich eine korrekte Implementierung. Aber keine besonders gute oder nützliche.