Tutte le funzioni ricorsive possono essere codificate con iterazioni? [chiuso]

Sì, puoi codificare le funzioni ricorsive come iterazioni. In pratica richiede di mantenere manualmente le informazioni che altrimenti sarebbero state prese in considerazione dal metodo di chiamata del codice generato dal compilatore.

In altre parole, è necessario uno stack in cui ogni voce è una struttura contenente i parametri passati e tutte le variabili locali. Lavorerai sempre al primo posto in cima allo stack. Se hai bisogno di chiamare te stesso, crea una nuova voce e mettila in cima allo stack. Quando hai finito, prendi la voce più in alto della pila esponendo quella in basso, e usa la voce in precedenza più in alto per estrarre i valori di ritorno e aggiornare di conseguenza la nuova voce più in alto.

Ti suggerisco di studiare un libro del compilatore per vedere come questo viene solitamente implementato nel codice macchina.

La ricorsione è spesso un modo più naturale di guardare le cose rispetto all'iterazione. Ad esempio, considera l'attraversamento inorder di un albero binario: inorder(left); process(); inorder(right); è molto più semplice rispetto al mantenimento esplicito di uno stack.

Fintanto che non vai troppo in profondità (soffia la pila), la differenza nell'uso delle risorse è solitamente banale. Non preoccuparti di questo in generale. Il codice semplice è normalmente migliore del codice ottimizzato a mano, sebbene ci siano delle eccezioni. Destra è normalmente meglio che veloce.

Qualsiasi algoritmo ricorsivo può essere espresso come un algoritmo iterativo, ma potrebbe essere necessario mantenere uno stack esplicito (corrispondente allo stack di chiamate gestito in modo implicito). Dopotutto, se si compila una funzione ricorsiva, si ottiene qualcosa che si basa sulla manipolazione di uno stack e sul looping della funzione, e questo è iterativo.

Le funzioni ricorsive di coda possono essere facilmente tradotte in loop e non richiedono uno stack, ma questo è un caso speciale.

What are the advantages of recursion?

Prova a risolvere iterativamente il problema di Towers of Hanoi. Una volta che ti arrendi, dai un'occhiata alla soluzione iterativa e confrontala con quella ricorsiva. Qual è più semplice?

Is it possible to have an iterative version of some recursive function?

Sì, in linea di principio. Tuttavia, per molti problemi, comprese attività molto comuni, come gli attraversamenti di alberi, le soluzioni ricorsive sono molto più semplici e più eleganti di quelle iterative.

What are the advantages of recursion?

Semplicità. Senza ottimizzazione tail-call, ovviamente richiede più risorse (stack), ma come implementeresti, ad esempio, deltree in Java senza ricorsione? La svolta è che delete() può eliminare le directory solo se sono vuote; eccolo con la ricorsione:

deltree(File fileOrDirectory) {
    if (fileOrDirectory.isDirectory()) {
        for (File subFileOrDirectory : fileOrDirectory.listFiles()) {
            deltree(subFileOrDirectory);
        }
    }
    fileOrDirectory.delete();
}

Credo che la ricorsione sia uno di quegli strumenti che un programmatore deve devono vivere. Con la ricorsione puoi "pensare" ai tuoi algoritmi e risolverli nel modo in cui ci hai pensato. Ma, devo avvertirti, tutti parlano di quanto sia bella la ricorsione e quanta semplicità apporti al codice, per quanto riguarda ciò ho alcune cose da dire:

1. Prima di tutto, pensare al "modo ricorsivo" di un algoritmo non è facile. Costruire una funzione come un fattoriale (n!) O qualcosa come Hanoi Towers è solo la punta dell'iceberg, e raggiungere il fondo richiede un lungo periodo di tempo.
2. Non pensare che la ricorsione porti semplicità solo nel tuo codice, a volte il modo iterativo è brutto e disordinato, ma è economicamente conveniente (guarda nella soluzione ricorsiva del problema di Fibonacci)

Avendo in mente queste cose, impara la ricorsione! è divertente, complesso e ti distruggerà il cervello !, ma ti ritroverai ad amarlo.

Buona fortuna!