Tutti gli algoritmi iterativi possono essere espressi in modo ricorsivo?

In caso contrario, c’è un buon esempio di contatore che mostra un algoritmo iterativo per il quale non esiste alcuna controparte ricorsiva?

Se è vero che tutti gli algoritmi iterativi possono essere espressi in modo ricorsivo, ci sono casi in cui è più difficile farlo?

Inoltre, che ruolo ha il linguaggio di programmazione in tutto questo? Posso immaginare che i programmatori di Scheme abbiano un approccio diverso per l’iterazione (= coda-ricorsione) e l’utilizzo dello stack rispetto ai programmatori solo Java.

C’è una semplice prova ad hoc per questo. Dal momento che è ansible build un linguaggio completo di Turing utilizzando strutture iterative rigorose e un linguaggio di tornitura completo utilizzando solo strutture ricorsive, i due sono quindi equivalenti.

Tutti gli algoritmi iterativi possono essere espressi in modo ricorsivo?

Sì, ma la dimostrazione non è interessante:

  1. Trasforma il programma con tutto il suo stream di controllo in un singolo ciclo contenente un’istruzione a caso singolo in cui ogni ramo è un stream di controllo in linea retta che può includere break , return , exit , raise e così via. Introduci una nuova variabile (chiamala “contatore del programma”) che l’istruzione case usa per decidere quale blocco eseguire successivamente.

    Questa costruzione fu scoperta durante le grandi “guerre di programmazione strutturata” degli anni ’60, quando le persone discutevano il potere espressivo relativo dei vari costrutti di stream di controllo.

  2. Sostituisci il loop con una funzione ricorsiva e sostituisci ogni variabile locale mutabile con un parametro per quella funzione. Ecco! Iterazione sostituita dalla ricorsione.

Questa procedura equivale a scrivere un interprete per la funzione originale. Come puoi immaginare, si traduce in codice illeggibile e non è una cosa interessante da fare. Tuttavia , alcune delle tecniche possono essere utili per una persona con background in una programmazione imperativa che sta imparando a programmare in un linguaggio funzionale per la prima volta.

Come dici tu, ogni approccio iterativo può essere trasformato in uno “ricorsivo”, e con le chiamate tail, lo stack non esploderà neanche. 🙂 In effetti, è in realtà come Scheme implementa tutte le forms comuni di loop. Esempio in Schema:

 (define (fib n) (do ((x 0 y) (y 1 (+ xy)) (i 1 (+ i 1))) ((> in) x))) 

Qui, anche se la funzione sembra iterativa, in realtà ricorre su un lambda interno che prende tre parametri, x , y i , e chiama se stesso con nuovi valori ad ogni iterazione.

Ecco un modo in cui la funzione potrebbe essere espansa in macro:

 (define (fib n) (letrec ((inner (lambda (xyi) (if (> in) x (inner y (+ xy) (+ i 1)))))) (inner 0 1 1))) 

In questo modo, la natura ricorsiva diventa visivamente più evidente.

Definire iterativo come:

 function q(vars): while X: do Y 

Può essere tradotto come:

  function q(vars): if X: do Y call q(vars) 

Nella maggior parte dei casi, Y include l’incremento di un contatore testato da X. Questa variabile dovrà essere passata in “vars” in qualche modo quando si passa alla rotta ricorsiva.

Come notato dal plinto nella loro risposta , possiamo build dimostrazioni che mostrano come la ricorsione e l’iterazione sono equivalenti e possono essere usate entrambe per risolvere lo stesso problema; tuttavia, anche se sappiamo che i due sono equivalenti, ci sono degli svantaggi nell’usare l’uno sull’altro.

Nei linguaggi che non sono ottimizzati per la ricorsione, è ansible che un algoritmo che utilizza l’iterazione sia più veloce di quello ricorsivo e, analogamente, anche in linguaggi ottimizzati, è ansible che un algoritmo che utilizza l’iterazione scritta in una lingua diversa sia più veloce di quello ricorsivo. Inoltre, potrebbe non esserci un modo ovvio di scrivere un determinato algoritmo usando la ricorsione o l’iterazione e viceversa. Questo può portare a un codice difficile da leggere che porta a problemi di manutenibilità.

Il Prolog è solo linguaggio ricorsivo e puoi fare praticamente tutto (non ti suggerisco di farlo, ma puoi :))

Le soluzioni ricorsive sono in genere relativamente inefficienti se confrontate con soluzioni iterative. Tuttavia, si nota che ci sono alcuni problemi che possono essere risolti solo attraverso la ricorsione e la soluzione iterativa equivalente potrebbe non esistere o estremamente complessa da programmare facilmente (Esempio di tale La funzione di Ackermann non può essere espressa senza ricorsione) Sebbene le ricorsioni siano eleganti, facili scrivere e capire