Cette queue est-elle récursive et pourrait-elle provoquer un débordement de pile? C# .Net

Question

Je me demande pourquoi la première fois que je reçois un VS/Resharper note que la récursion de la queue pourrait être remplacée par une boucle, et j'ai effectivement réussi à obtenir quelque chose de similaire pour provoquer un débordement de pile alors je lis comment les récursions de queue fonctionnent et comment il développe la pile, etc.

Ce premier génère la note de récurrence de queue.

private static string GetLine() 
    { 
     string s = Console.ReadLine(); 

     if (s == null) 
     { 
      return GetLine(); 
     } 
     return s; 
    } 

Mais le faire comme cela ne:

private static string GetLine() 
    { 
     string s = Console.ReadLine(); 

     if (s == null) 
     { 
      s = GetLine(); 
     } 
     return s; 
    } 

Alors ma question est; le second n'est-il pas considéré comme récursif, c'est-à-dire qu'il ne peut pas créer un débordement de pile car il ne génère pas tous les appels de pile?

Answer 1

Comme l'explique usr dans his answer, ReSharper essaie de trouver des modèles connus dans votre code pour lesquels il peut offrir des refactorings. Mais jetons un coup d'œil au code généré pour les deux cas.

---

La première fonction:

private static string GetLineA() 
{ 
    string s = Console.ReadLine(); 

    if (s == null) 
    { 
     return GetLineA(); 
    } 
    return s; 
} 

donne cette (x64, Release):

00007FFB34AC43EE add   byte ptr [rax],al 
00007FFB34AC43F0 sub   rsp,28h 
00007FFB34AC43F4 call  00007FFB8E56F530 // <-- Console.ReadLine 
00007FFB34AC43F9 test  rax,rax 
00007FFB34AC43FC jne   00007FFB34AC440F 
00007FFB34AC43FE mov   rax,7FFB34AC0F60h 
00007FFB34AC4408 add   rsp,28h 
00007FFB34AC440C jmp   rax 
00007FFB34AC440F add   rsp,28h 
00007FFB34AC4413 ret 

puisque la seule instruction call est pour Console.ReadLine Vous pouvez voir clairement qu'il est récursive de la queue,.

---

La deuxième version:

private static string GetLineB() 
{ 
    string s = Console.ReadLine(); 

    if (s == null) 
    { 
     s = GetLineB(); 
    } 
    return s; 
} 

donne ceci:

00007FFB34AC44CE add   byte ptr [rax],al 
00007FFB34AC44D0 sub   rsp,28h 
00007FFB34AC44D4 call  00007FFB8E56F530 // <-- Console.ReadLine 
00007FFB34AC44D9 test  rax,rax 
00007FFB34AC44DC jne   00007FFB34AC44E3 
00007FFB34AC44DE call  00007FFB34AC0F68 // <-- Not good. 
00007FFB34AC44E3 nop 
00007FFB34AC44E4 add   rsp,28h 
00007FFB34AC44E8 ret 

Il y a une seconde il call, afin de ne pas récursion queue, et la pile grandirez , entraînant eventuellement un débordement de pile s'il grandit suffisamment. Eh bien, il semble que le JIT n'a pas optimisé le code dans un appel récursif de la queue.

---

De toute façon, méfiez-vous, puisque vous êtes à la merci du JAT.

est ici GetLineA en x86:

00F32DCA in   al,dx 
00F32DCB call  72A209DC // <-- Console.ReadLine 
00F32DD0 test  eax,eax 
00F32DD2 jne   00F32DDC 
00F32DD4 call  dword ptr ds:[12B8E94h] // <-- Ouch 
00F32DDA pop   ebp 
00F32DDB ret 
00F32DDC pop   ebp 
00F32DDD ret 

Voir? Vous ne pouvez pas vraiment en dépendre, et la langue ne fournit aucune garantie.

Answer 2

Resharper ne détecte tout simplement pas la seconde forme. Cela n'essaie pas dur. L'analyse de programme est difficile et impossible en général (voir le problème d'arrêt). Resharper a surtout quelques heuristiques heureuses et utiles.

Si vous remplacez ReadLine par null, vous verrez qu'un débordement de pile est très possible ici.