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

14

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?

prakhar londhe
la source
8
Il ne se termine pas pour n = -1. Dans la plupart des cas, des limites théoriques sont envisagées.
Deep Joshi
9
Si le débordement de pile doit être considéré comme une fin, alors tous les programmes se termineront et cela
ira à l'encontre
10
@ xuq01 while (true);ne se terminera pas et ne provoquera pas de débordement de pile.
TripeHound
3
@leftaroundabout Je n'aurais probablement pas dû utiliser " sur quelque chose de sensible " car c'est un niveau complètement différent de " sensible " ... repérer et implémenter la récursivité de la queue est bien (ou même sensible ), mais ne pas le faire n'est que légèrement " pas sensible" ". Tout ce qui est implémenté while(true);d'une manière qui utilise n'importe quelle pile ne serait certainement pas raisonnable . Le fait est que, à moins que vous n'ayez délibérément fait tout votre possible pour être maladroit, while(true);cela ne terminera ni ne déclenchera de débordement de pile.
TripeHound
14
@ xuq01 Je ne pense pas que la "destruction de l'univers" compte comme une solution au problème de l'arrêt.
TripeHound

Réponses:

49

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.

Gilles 'SO- arrête d'être méchant'
la source
3
Haskell est un exemple où le code traduit en langage de programmation n'entraîne aucun débordement de pile. Il boucle juste indéfiniment:let f :: Int -> Int; f n = if even n then n `div` 2 else f (f (n - 1)) in f (-1)
JoL
5

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.

gnasher729
la source
Je pense, en C, que l'invocation f(-1)est un comportement indéfini (l'implémentation peut supposer que chaque thread se termine ou fait autre chose dans une courte liste d'activités que cette fonction ne fait pas), donc le compilateur peut réellement faire tout ce qu'il veut dans ce Cas!