spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Moin!
Gibt es nicht divergierende, rekursive Funktionen, die man nicht endrekursiv darstellen kann?
Wie könnte man entsprechend beweisen? Für den einen Fall ist klar, so eine Funktion finden (die will erst mal gefunden sein), der andere wird schwerer...

MfG
Check

Ich nenne eine rekursive Funktion, die nicht für alle Eingaben terminiert, divergierend. Meistens nenne ich dazu noch den entsprechenden Wertebereich, für den die Funktion divergiert, aber ich glaub das wird zur Beantwortung meiner Frage weniger relevant sein.

Eine Funktion §f'§ ist endrekursiv, wenn sie sich wie folgt definieren lässt: §f(x)=\left\{\begin{array}{ll}z(x)&\mbox{, falls }B(x)\\f(y(x))&\mbox{, falls }\neg B(x)\end{array}\right.§, wobei §z, y§ beliebige Funktionen sind und §B§ die Funktion beschreibt, die die Abbruchbedingung für §f§ sein soll. Mit anderen Worten sollen §f§ und §f'§ dann in einer idealisierten Umgebung semantisch gleich sein.

Jetzt alles klar?

MfG
Check

Also es existiert eine nicht divergierende, rekursive Funktion, die nicht endrekursiv beschreibbar ist?
Wäre echt cool, wenn du das erläutern könntest.

MfG
Check

Zitat von »dot«

Wie genau würde eine "nicht terminierende Funktion" in deiner obigen Darstellung aussehen?

§g(x)=g(x)§

@David: Wenn ich Zwiswchenzustände in die Knoten schreibe, kann ich die sicherlich auch endrekursiv darstellen...

@GreenPepper: Die Fibonacci-Folge ist endrekursiv darstellbar:


Wenn du natürlich die Fibonacci-Folge an sich erzeugen willst, dann divergiert die nach meiner Definition, damit interessiert sie mich auch nicht, da mich nur nicht divergierende Funktionen hierbei interessieren!

Vielleicht nochmal in anderen Worten: Ich bezeichne etwas als endrekursiv, wenn es nach einem rekursiven Aufruf keine weiteren Vorgänge gibt. Also int a(int b){return (b>0) ? 1+a(b-1) : 0;} ist zum Beispiel nicht endrekursiv, dafür aber int a(int b, int akk=0){return (b>0) ? a(b, akk+1) : akk;}

MfG
Check