Fare ricorsione in coda in C++

Question

La mia funzione può essere scritta molto più semplicemente, se faccio una ricorsione chiamata coda (al contrario di un ciclo for (;;)...break). Tuttavia temo di avere problemi di prestazioni se il compilatore non riesce a ottimizzarlo, soprattutto perché verrà compilato dall'utente finale.

1. C'è un modo per dire al compilatore "Assicurarsi di ottimizzare questa chiamata coda, oppure mi dai un errore" (ad esempio, Scala supporta questo)

2. Se il compilatore non può ottimizzare di distanza, quali sono i limiti delle prestazioni? Su quante chiamate di coda posso aspettarmi di essere in grado di correre senza rompere lo stack?

---

UPDATE:

compilatori gcc e sono MSVC.

In genere, mi aspetto circa una dozzina di chiamate di coda. Ma il caso estremo potrebbe avere migliaia. La piattaforma è un tipico laptop di fascia bassa (ad es. Core i3 o i5).

Answer 1

No, non c'è alcun modo per dire un compilatore che è necessaria la ricorsione in coda. Alcuni compilatori (nessuno dei quali sono a conoscenza) potrebbero supportare annotazioni specifiche dell'implementazione, ma questo richiede all'utente di utilizzare quel compilatore specifico. Alcuni altri compilatori, in alcune modalità, non supportano mai intenzionalmente le chiamate tail, perché possono fornire una migliore esperienza di debug non supportando le chiamate tail. L'utente potrebbe utilizzare un compilatore di questo tipo.

La profondità di ricorsione ammesso è altamente programmata, e della funzione dipendente dall'implementazione, e nessun numero sensibili può essere dato per esso. Data una piattaforma specifica, puoi probabilmente determinare la dimensione dello stack di default, investigare le dimensioni del frame per un particolare compilatore su quella piattaforma e fare una semplice divisione per ottenere una stima approssimativa di quante chiamate nidificate puoi avere.

Consiglieresti riscrittura in un modo che rende chiaro al lettore ciò che accade, ma non si basa su un compilatore ottimizzare chiamate coda. Sebbene sia odiato, l'istruzione goto può essere molto utile per questo.

prendere un semplice coda ricorsiva funzione bit conteggio:

int bitcount(unsigned int n, int acc = 0) { 
    if (n == 0) 
    return acc; 

    return bitcount(n >> 1, acc + (n & 1)); 
} 

Può essere banalmente riscritta come

int bitcount(unsigned int n, int acc = 0) { 
tail_recurse: 
    if (n == 0) 
    return acc; 

    // tail return bitcount(n >> 1, acc + (n & 1)); 
    acc += n & 1; 
    n = n >> 1; 
    goto tail_recurse; 
} 

Naturalmente questa è una versione semplice che è banalmente riscritto per evitare ricorsione interamente , e probabilmente dovrebbe nemmeno essere implementato manualmente, ma la trasformazione speciali io ho usato qui è uno che si può applicare a qualsiasi funzione dove la ricorsione in coda è possibile e dove si ha bisogno di ricorsione in coda. Il commento dovrebbe assicurarsi che il lettore possa ancora facilmente individuare cosa sta succedendo.

Answer 2

Con GCC è possibile aggiungere un controllo runtime utilizzando la funzione backtrace():

#include <cassert> 
#include <iostream> 
#include <execinfo.h> 

size_t start; 

size_t stack_frames() 
{ 
    void *array[16]; 
    size_t size = backtrace(array, 16); 

    // std::cout << "Obtained " << size << " stack frames.\n"; 
    return size; 
} 

bool missing_tail() 
{ 
    return stack_frames() > start + 2; 
} 

int bitcount(unsigned int n, int acc = 0) 
{ 
    assert(!missing_tail()); 

    if (n == 0) 
    return acc; 

    return bitcount(n >> 1, acc + (n & 1)); 
} 

int main() 
{ 
    start = stack_frames(); 

    std::cout << bitcount(10) << '\n'; 

    return 0; 
} 

quando si compila con un livello di ottimizzazione inferiore -O2 (senza ottimizzazione ricorsione in coda) si ottiene un errore di asserzione.