Zitat von
Eichhoernchen:
also ich bin eigentlich auch der Meinung, dass nicht jedes rekursive iterativ lösbar ist.
Must du auch nicht, ist aber so
: Erstens (laut BlackJack) wg. der CPU, die ja nur einen Zähler verwaltet (program counter). Zweitens kannst du ja den Stack mit einer Liste und den rekursiven Aufruf mit einem Goto (
) simulieren und drittens kann man das beweisen. Wie, weiss ich aber nicht. Die ersten beiden Punkte dürften aber ausreichen.
Mein Beweis:
Behauptung: Jeder rekursive Algorithmus lässt sich in einen iterativen Algorithmus überführen.
Beweis durch Widerspruch: Angenommen, es gäbe einen rekursiven Algorithmus, der *nicht* in einen Iterativen überführt werden kann. Den könntest Du dann auch nicht in einer Programmiersprache codieren, weil ja ein Compiler jede rekursive Routine in eine Iterative überführt (nämlich Maschinencode).
Da nun aber jeder Algorithmus in einer Programmiersprache kodiert werden kann, ist die Annahme ('Es gibt einen ...') falsch, also die Behauptung richtig.
Die Frage ist nun verlagert: "Kann JEDER Algorithmus in einer Programmiersprache kodiert werden?" Meine Antwort: Hängt vom Programmierer ab.
