Una funzione ricorsiva può essere in linea?

inline int factorial(int n) { if(!n) return 1; else return n*factorial(n-1); } 

Mentre stavo leggendo questo , ho scoperto che il codice sopra avrebbe portato a “compilazione infinita” se non gestito correttamente dal compilatore.

Come fa il compilatore a decidere se integrare una funzione o no?

Innanzitutto, le specifiche in inline su una funzione sono solo un suggerimento. Il compilatore può (e spesso fa) ignorare completamente la presenza o l’assenza di un qualificatore in inline . Detto questo, un compilatore può incorporare una funzione ricorsiva, tanto quanto può srotolare un ciclo infinito. Deve semplicemente porre un limite al livello a cui “srotolerà” la funzione.

Un compilatore di ottimizzazione potrebbe trasformare questo codice:

 inline int factorial(int n) { if (n <= 1) { return 1; } else { return n * factorial(n - 1); } } int f(int x) { return factorial(x); } 

in questo codice:

 int factorial(int n) { if (n <= 1) { return 1; } else { return n * factorial(n - 1); } } int f(int x) { if (x <= 1) { return 1; } else { int x2 = x - 1; if (x2 <= 1) { return x * 1; } else { int x3 = x2 - 1; if (x3 <= 1) { return x * x2 * 1; } else { return x * x2 * x3 * factorial(x3 - 1); } } } } 

In questo caso, abbiamo praticamente sottolineato la funzione 3 volte. Alcuni compilatori eseguono questa ottimizzazione. Ricordo MSVC ++ con un'impostazione per regolare il livello di inlining che verrebbe eseguito su funzioni ricorsive (fino a 20, credo).

Infatti, se il compilatore non agisce in modo intelligente, potrebbe provare a inserire copie della funzione inline d ricorsivamente, creando un codice infinitamente grande. La maggior parte dei compilatori moderni lo riconosceranno comunque. Possono:

  1. Non in linea la funzione affatto
  2. Inline fino a una certa profondità e, se non è terminato, chiama l’istanza separata della tua funzione usando la convenzione di chiamata della funzione standard. Questo può occuparsi di molti casi comuni in un modo ad alte prestazioni, lasciando un ripiego nel caso raro con una grande profondità di chiamata. Ciò significa anche che tu mantenga entrambe le versioni inline e separate del codice di quella funzione.

Per il caso 2, molti compilatori hanno #pragma che puoi impostare per specificare la profondità massima a cui questo dovrebbe essere fatto. In gcc , puoi anche farlo passare dalla riga di comando con --max-inline-insns-recursive (vedi maggiori informazioni qui ).

AFAIK GCC effettuerà un’eliminazione di chiamata di coda su funzioni ricorsive, se ansible. La tua funzione tuttavia non è ricorsiva della coda.

Il compilatore crea un grafo delle chiamate; quando viene rilevato un ciclo chiamandosi, la funzione non è più in linea dopo una certa profondità (n = 1, 10, 100, a prescindere dal sintonizzatore del compilatore).

Alcune funzioni ricorsive possono essere trasformate in loop, che li allineano in modo efficace all’infinito. Credo che gcc possa farlo, ma non conosco altri compilatori.

Vedere le risposte già fornite per il motivo per cui in genere non funzionerà.

Come “nota a piè di pagina”, puoi ottenere l’effetto che stai cercando (almeno per il fattoriale che stai utilizzando come esempio) utilizzando la metaprogrammazione del modello . Incollare da Wikipedia:

 template  struct Factorial { enum { value = N * Factorial::value }; }; template <> struct Factorial<0> { enum { value = 1 }; }; 

Il compilatore farà un grafico delle chiamate per rilevare questo tipo di cose e prevenirle. Quindi vedrebbe che la funzione chiama se stessa e non in linea.

Ma principalmente è controllato dalla parola chiave inline e dai commutatori del compilatore (ad esempio, puoi avere funzioni automatiche inline di piccole dimensioni anche senza la parola chiave.) È importante notare che le compilation di Debug non dovrebbero mai essere integrate poiché il callstack non sarà conservato in mirror le chiamate che hai creato nel codice.

“Come fa il compilatore a decidere se integrare una funzione o no?”

Dipende dal compilatore, dalle opzioni che sono state specificate, dal numero di versione del compilatore, forse quanta memoria è disponibile, ecc.

Il codice sorgente del programma deve ancora rispettare le regole per le funzioni integrate. Indipendentemente dal fatto che la funzione venga sottolineata, è necessario prepararsi alla possibilità che sia in linea (un numero imprecisato di volte).

L’affermazione di Wikipedia secondo cui le macro ricorsive sono in genere aspetti illegali piuttosto scarsamente informate. C e C ++ impediscono le chiamate ricorsive ma un’unità di traduzione non diventa illegale contenendo il codice macro che sembra essere ricorsivo. Negli assemblatori, le macro ricorsive sono tipicamente legali.

Alcuni compilatori (Ie Borland C ++) non contengono codice inline che contiene istruzioni condizionali (se, caso, mentre ecc.) In modo che la funzione ricorsiva nell’esempio non sia inline.