Recursion Vs Iteration

Question

Credo che tutti i problemi che hanno una logica iterativa possano essere risolti usando le iterazioni, ma possiamo risolvere qualsiasi problema usando la ricorsione? La ricorsione può sempre sostituire l'iterazione? Per favore fornisci una prova alla tua risposta se puoi. Supponiamo anche di avere uno stack infinito o di eseguire il programma su una macchina di Turing. Non mi interessa se questa prova è una prova teorica. (è per questo che ho menzionato la Turing Machine)

Answer 1

Sì, la ricorsione può sempre sostituire l'iterazione, questo è stato discusso before. Citando dal post collegato:

Poiché è possibile creare un linguaggio completo di Turing utilizzando strutture iterative rigorose e un linguaggio di tornitura completo utilizzando solo strutture ricorsive, quindi i due sono quindi equivalenti.

Spiegando un po ': sappiamo che qualsiasi problema computabile può essere risolto da una macchina di Turing. Ed è possibile costruire un linguaggio di programmazione A senza ricorsione, che è equivalente a una macchina di Turing. Allo stesso modo, è possibile creare un linguaggio di programmazione B senza iterazione, uguale in potenza di calcolo a una macchina di Turing.

Pertanto, se entrambi A e B sono Turing-complete, possiamo concludere che per ogni programma iterativo deve esistere un programma ricorsivo equivalente e viceversa. Questo è un risultato teorico, nel senso che non fornisce alcun suggerimento su come derivare un programma ricorsivo da un programma iterativo arbitrario, o viceversa.

Answer 2

Sì. Esiste un tipo di ricorsione chiamato tail recursion, che è direttamente traducibile in iterazione. Uno può essere convertito all'altro senza alcun problema. Pertanto, tutte le soluzioni iterative possono essere convertite in soluzioni ricorsive.

In effetti, molti compilatori possono rilevare che si sta eseguendo la ricorsione in coda e quindi convertirlo in codice di tipo ciclo per efficienza.

Answer 3

Una ricorsione deve essere utilizzata quando un ciclo non è necessario, ma il metodo deve ripetersi in un determinato caso. Ad esempio, zippare una cartella. Se c'è una sottocartella, dovrebbe chiamarsi (ricorsiva). La ricorsione potrebbe sostituire le iterazioni se lo si desidera, ma non è raccomandato. Molte persone usano solo le iterazioni e usano le ricorsioni solo quando sono necessarie.