Wird dieses Programm für jede Ganzzahl beendet?

In einem Teiltest für die GATE-Vorbereitung gab es eine Frage:

f(n):
     if n is even: f(n) = n/2
     else f(n) = f(f(n-1))

Ich antwortete "Es wird für alle Ganzzahlen beendet", da es selbst für einige negative Ganzzahlen als Stapelüberlauffehler beendet wird .

Aber mein Freund widersprach der Aussage, dass es sich bei einigen negativen ganzen Zahlen um eine unendliche Rekursion handelt, da es sich nicht um implementierten Code und nur um Pseudocode handelt.

Welche Antwort ist richtig und warum?

Die richtige Antwort lautet, dass diese Funktion nicht für alle Ganzzahlen beendet wird (insbesondere endet sie nicht bei -1). Ihr Freund hat Recht, wenn er angibt, dass dies Pseudocode ist und Pseudocode nicht bei einem Stapelüberlauf endet. Pseudocode ist formal nicht definiert, aber die Idee ist, dass es das tut, was auf dem Zinn steht. Wenn der Code nicht "Beenden mit einem Stapelüberlauffehler" sagt, liegt kein Stapelüberlauffehler vor.

Selbst wenn dies eine echte Programmiersprache wäre, wäre die richtige Antwort immer noch "nicht terminieren", es sei denn, die Verwendung eines Stacks ist Teil der Definition der Sprache. Die meisten Sprachen spezifizieren nicht das Verhalten von Programmen, die den Stapel überlaufen könnten, da es schwierig ist, genau zu wissen, wie viel Stapel ein Programm verwenden wird.

Wenn das Ausführen des Codes auf einem tatsächlichen Interpreter oder Compiler in vielen Sprachen einen Stapelüberlauf verursacht, ist dies eine Diskrepanz zwischen der formalen Semantik der Sprache und der Implementierung. Es ist allgemein bekannt, dass Implementierungen einer Sprache nur das tun, was auf einem konkreten Computer mit endlichem Speicher möglich ist. Wenn das Programm mit einem Stapelüberlauf abstürzt, sollten Sie einen größeren Computer kaufen, das System bei Bedarf neu kompilieren, um den gesamten Speicher zu unterstützen, und es erneut versuchen. Wenn das Programm nicht beendet wird, müssen Sie dies möglicherweise für immer tun.

Sogar die Tatsache, dass ein Programm den Stapel überläuft oder nicht überläuft, ist nicht genau definiert, da einige Optimierungen, wie die Optimierung von Tail Calls und das Merken , eine unendliche Kette von Funktionsaufrufen in einem konstant gebundenen Stapelraum ermöglichen können. Einige Sprachspezifikationen verlangen sogar, dass Implementierungen, wenn möglich, eine Tail-Call-Optimierung durchführen (dies ist in funktionalen Programmiersprachen üblich). Erweitert für diese Funktion f(-1)auf f(f(-2)); Der äußere Aufruf von fist ein Tail-Aufruf, sodass nichts auf den Stapel geschoben wird, sondern nur f(-2)auf den Stapel verschoben -1wird. Das Ergebnis ist, dass der Stapel wieder in dem Zustand ist, in dem er zu Beginn war. Somit bleibt bei der Tail-Call-Optimierung die f(-1)Schleife für immer im Dauerspeicher.

Wenn wir dies in Bezug auf die C-Sprache betrachten, kann eine Implementierung Code durch Code ersetzen, der in allen Fällen, in denen das Original kein undefiniertes Verhalten hervorruft, dasselbe Ergebnis liefert. So kann es ersetzen

f(n):
   if n is even: f(n) = n/2
   else f(n) = f(f(n-1))

mit

f(n):
   if n is even: f(n) = n/2
   else f(n) = f((n-1) / 2)

Jetzt darf die Implementierung die Schwanzrekursion anwenden:

f(n):
   while n is not even do n = (n-1) / 2
   f(n) = n/2

Und dies ist genau dann eine Endlosschleife, wenn n = -1 ist.