rekursiv -> iterativ

[xroads42]

Hallo,

such einen satz, der aussagt, dass man jede linear-rekursive funktion in eine iterative form umwandeln kann.
Hat da wer ein "schlag"-wort wonach ich suche könnte?

[desert pinguin]

stack

[Bashar]

Ich wette, mit linear-rekursiv sind solche Programme gemeint, die man ohne Stack in iterative Programme umwandeln kann.

[xroads42]

ich will nicht wissen wie das geht, sondern einen beweiß/satz/lemma, dass es für alle linear rekursiven funktionen geht. Mir ist egal wie, ich will nur wissen, dass es geht. und den namen dieses satzes hätte ich gerne gewußt, damit ich mich darauf beziehen kann.

[xroads42]

Bashar schrieb:

Ich wette, mit linear-rekursiv sind solche Programme gemeint, die man ohne Stack in iterative Programme umwandeln kann.

genau, bei den geht es auch ohne stack.

[desert pinguin]

Uppss. I habe es übersehen.
Tail recursion?

[xroads42]

desert pinguin schrieb:

Uppss. I habe es übersehen.
Tail recursion?

Hm, ja, soweit war ich auch schon. Eine Lineare rekursion kann man in eine repetitve Rekursion umwandeln. und diese kann man in ein iteratvies programm umschreiben. Schön und gut. Aber mir fehlt der wissentschaftliche beweiß.

(geht darum das ich eine (uni) hausaufgabe für die ein bis zwei lösungsseiten gedacht sind in einen kleinen absatz erschlagen möchte, und da sollte das ganze schon hieb und stichfest sein..)

[desert pinguin]

xroads42 schrieb:

Bashar schrieb:

Ich wette, mit linear-rekursiv sind solche Programme gemeint, die man ohne Stack in iterative Programme umwandeln kann.

genau, bei den geht es auch ohne stack.

Bist du sicher?