5
votes

Terminaison anormale due à un débordement de pile

J'ai récemment passé mon test d'admission à l'école doctorale il y a quelques jours et la question suivante est apparue dans le test.
Lorsque la fonction ci-dessous est invoquée avec un entier positif comme argument, se termine-t-elle?

void convert (int n) 
{
  if (n < 0)
    printf ("%d", n);
  else 
  {
    convert (n/2);
    printf ("%d", n%2);
  }
}

Selon moi, rien ne sera affiché car le contrôle n'atteint jamais l'instruction if et aussi puisque l'instruction printf est placée après l'appel de fonction sous le bloc else. La valeur de n n'atteint jamais en dessous de 0 et la fonction s'appelle elle-même encore et encore jusqu'à ce que la pile déborde. Ma question est de savoir si le code se terminera anormalement en raison d'un débordement de pile?

c stack-overflow termination

2 commentaires

Le code peut être optimisé afin de ne consommer aucune pile. Mais sinon, vous avez raison.

... J'ai supposé que vous aviez été licencié pour une raison étrange liée à la publication sur ce site Web.

3 Réponses :

6
votes

Le code ne se terminera pas par un argument entier positif car la condition de base n ne sera jamais remplie.

L'appel récursif à convert l'appelle avec l'argument n / 2 , qui, en tant que division entière, va inévitablement atteindre zéro, mais jamais moins que cela.

  Par exemple, avec l'argument 10:
call convert(10)
10 < 0 is false; enter the else branch
call convert(10 / 2)
5 < 0 is false; enter the else branch
call convert(5 / 2)
2 < 0 is false; enter the else branch
call convert(2 / 2)
1 < 0 is false; enter the else branch
call convert(1 / 2)
0 < 0 is false; enter the else branch
call convert(0 / 2)
0 < 0 is false; enter the else branch
call convert(0 / 2)
0 < 0 is false; enter the else branch
call convert(0 / 2)
0 < 0 is false; enter the else branch
  Il n'entrera jamais dans le cas de base.

0 commentaires

3
votes

Le code se terminera par un stackoverflow ou non selon la sortie du compilateur.

Il n'y aura pas de sortie. car n ne sera jamais inférieur à 0 .

Avec un compilateur naïf qui compile la récursion sans optimisation, vous obtiendrez un stackoverflow sur la plupart des implémentations (sinon toutes).

0 commentaires

4
votes

Oui, à moins que l'optimiseur de votre compilateur ne fasse quelque chose d'inhabituel, ce programme se terminera anormalement à cause d'un débordement de pile.

La raison en est que la fonction convert () est appelée de manière récursive une infinité de fois. Vous le saviez déjà, mais le point est le suivant: chaque entrée récursive de convert () pousse une nouvelle image sur la pile. Chaque trame comprend une adresse de retour à la trame précédente et une valeur locale de n .

Les compilateurs ont des optimiseurs mais il faudrait un optimiseur inhabituel pour comprendre que cette fonction (a) n'a pas d'effets secondaires et (b) ne renvoie aucune valeur. Il est donc peu probable que l'optimiseur sauve ce code d'une interruption anormale.

Je pense que vous avez bien répondu à cette question.

Pendant ce temps, un commentateur nous a rappelé un cas particulier, la récursion de queue. Si l'appel récursif avait mis fin à la fonction, comme return convert (n / 2); par exemple, alors le compilateur pourrait avoir réutilisé une seule trame de pile pour tous les appels récursifs. Raison: au moment où l'appel récursif se produit, l'appel en cours ne nécessite plus son stockage; l'objet n pourrait être écrasé en toute sécurité par le nouveau n pour l'appel récursif; seule l'adresse de retour de l'appelant d'origine devrait être conservée. Si la récursivité de queue était appliquée, la pile ne croîtrait pas et, par conséquent, le programme ne se terminerait pas, ni de façon anormale ni autrement. Cependant, la récursion de queue ne s'applique pas ici.

0 commentaires