Ce programme prendra-t-il fin pour chaque entier?

Dans un test de pièce pour la préparation de GATE, il y avait une question:

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

J'ai répondu "Il se terminera pour tous les entiers", car même pour certains entiers négatifs, il se terminera par une erreur de dépassement de pile .

Mais mon ami n'était pas d'accord en disant que puisque ce n'est pas du code implémenté et juste du pseudocode, ce sera une récursion infinie dans le cas de certains entiers négatifs.

Quelle réponse est correcte et pourquoi?

La bonne réponse est que cette fonction ne se termine pas pour tous les entiers (en particulier, elle ne se termine pas sur -1). Votre ami a raison de dire qu'il s'agit d'un pseudocode et que le pseudocode ne se termine pas lors d'un débordement de pile. Le pseudocode n'est pas formellement défini, mais l'idée est qu'il fait ce qui est dit sur l'étain. Si le code ne dit pas "terminer avec une erreur de débordement de pile", il n'y a pas d'erreur de débordement de pile.

Même s'il s'agissait d'un véritable langage de programmation, la bonne réponse serait toujours "ne se termine pas", à moins que l'utilisation d'une pile ne fasse partie de la définition du langage. La plupart des langues ne spécifient pas le comportement des programmes susceptibles de déborder la pile, car il est difficile de savoir précisément la quantité de pile qu'un programme utilisera.

Si l'exécution du code sur un interpréteur ou un compilateur réel provoque un débordement de pile, dans de nombreuses langues, il s'agit d'une différence entre la sémantique formelle de la langue et l'implémentation. Il est généralement admis que les implémentations d'un langage ne feront que ce qui peut être fait sur un ordinateur concret à mémoire finie. Si le programme meurt avec un débordement de pile, vous êtes censé acheter un ordinateur plus gros, recompiler le système si nécessaire pour prendre en charge toute cette mémoire et réessayer. Si le programme ne se termine pas, vous devrez peut-être continuer à le faire pour toujours.

Même le fait qu'un programme déborde ou ne dépasse pas la pile n'est pas bien défini, car certaines optimisations telles que l' optimisation des appels de queue et la mémorisation peuvent permettre une chaîne infinie d'appels de fonctions dans un espace de pile à constante constante. Certaines spécifications de langage exigent même que les implémentations effectuent une optimisation des appels de queue lorsque cela est possible (cela est courant dans les langages de programmation fonctionnels). Pour cette fonction, se f(-1)développe en f(f(-2)); l'appel externe à fest un appel de queue donc il ne pousse rien sur la pile, donc ne f(-2)va que sur la pile, et cela revient -1, donc la pile est de retour au même état où elle était au début. Ainsi, avec l'optimisation des appels de queue, des f(-1)boucles pour toujours en mémoire constante.

Si nous regardons cela en termes de langage C, une implémentation est libre de remplacer le code par du code qui produit le même résultat dans tous les cas où l'original n'invoque pas un comportement non défini. Il peut donc remplacer

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

avec

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

Maintenant, l'implémentation est autorisée à appliquer la récursivité de queue:

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

Et cela boucle pour toujours si et seulement si n = -1.