I compilatori possono e fanno convertire la logica ricorsiva in una logica equivalente non ricorsiva?

Sì, alcuni linguaggi e compilatori di complenze convertiranno la logica ricorsiva in logica non ricorsiva. Questo è noto come ottimizzazione delle chiamate tail - si noti che non tutte le chiamate ricorsive sono ottimizzate per la coda. In questa situazione, il compilatore riconosce una funzione del modulo:

int foo(n) {
  ...
  return bar(n);
}

Qui, la lingua è in grado di riconoscere che il risultato che viene restituito è il risultato di un'altra funzione e di modificare una chiamata di funzione con un nuovo stack frame in un salto.

Renditi conto che il classico metodo fattoriale:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

è non chiamata di coda ottimizzabile a causa dell'ispezione necessaria al reso.

Per rendere questa chiamata di coda ottimizzata,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Compilare questo codice con gcc -O2 -S fact.c (il -O2 è necessario per abilitare l'ottimizzazione nel compilatore, ma con più ottimizzazioni di -O3 diventa difficile per un essere umano leggere ...)

_fact:
.LFB0:
        .cfi_startproc
        cmpl    $1, %edi
        movl    %esi, %eax
        je      .L2
        .p2align 4,,10
        .p2align 3
.L4:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L4
.L2:
        rep
        ret
        .cfi_endproc

Si può vedere nel segmento .L4 , il jne piuttosto che un call (che fa una chiamata di subroutine con un nuovo frame dello stack).

Si noti che questo è stato fatto con l'ottimizzazione della chiamata di C. Tail in java è difficile e dipende dall'implementazione JVM - tail-recursion + java e tail-ricorsione + ottimizzazione sono buoni set di tag per navigare. Potresti trovare altre lingue JVM in grado di ottimizzare meglio la ricorsione della coda (prova clojure (che richiede ricorrere per ottimizzare le chiamate tail), o scala).

Calpesta attentamente.

La risposta è sì, ma non sempre, e non tutti. Questa è una tecnica con nomi diversi, ma puoi trovare alcune informazioni piuttosto definitive qui e wikipedia .

Preferisco il nome "Tail Call Optimization" ma ci sono altri e alcune persone confonderanno il termine.

Detto questo ci sono un paio di cose importanti da realizzare:

• Per ottimizzare una chiamata di coda, la chiamata di coda richiede parametri noti al momento della chiamata. Ciò significa che se uno dei parametri è una chiamata alla funzione stessa, allora non può essere convertito in un ciclo, poiché ciò richiederebbe una nidificazione arbitraria di detto ciclo che non può essere espansa in fase di compilazione.

• C # non non ottimizza in modo affidabile le chiamate tail. L'IL ha l'istruzione di fare ciò che il compilatore F # emetterà, ma il compilatore C # lo emetterà in modo incoerente e, a seconda della situazione JIT, il JIT potrebbe o meno non farlo affatto. Tutte le indicazioni sono che non dovresti fare affidamento sulle chiamate di coda ottimizzate in C #, il rischio di overflow nel farlo è significativo e reale