Ci sono momenti in cui l'utilizzo della ricorsione è migliore rispetto all'utilizzo di un ciclo e tempi in cui l'utilizzo di un ciclo è migliore rispetto all'utilizzo della ricorsione. Scegliendo il "giusto" si possono risparmiare risorse e / o risultare meno linee di codice.
Ci sono casi in cui un'attività può essere eseguita solo utilizzando la ricorsione, piuttosto che un ciclo?
Sì e no. In definitiva, non c'è nulla che la ricorsione possa calcolare che il ciclo non possa, ma il ciclo richiede molto più impianto idraulico. Pertanto, l'unica cosa che la ricorsione può fare è che i loop non possono rendere le attività molto facili.
Fai camminare un albero. Camminare su un albero con la ricorsione è semplicissimo. È la cosa più naturale del mondo. Camminare su un albero con anelli è molto meno semplice. Devi mantenere uno stack o qualche altra struttura dati per tenere traccia di ciò che hai fatto.
Spesso, la soluzione ricorsiva di un problema è più carina. Questo è un termine tecnico e conta.
No.
Scendendo alle basi molto dei minimi necessari per il calcolo, devi solo essere in grado di eseguire il ciclo (questo da solo non è sufficiente, ma piuttosto è un componente necessario). Non importa come .
Qualsiasi linguaggio di programmazione che possa implementare una Macchina di Turing, è chiamato Turing completo . E ci sono molte lingue che sono complete.
La mia lingua preferita nel modo in cui "funziona davvero?" La completezza di Turing è quella di FRACTRAN , che è Turing completo . Ha una struttura ad anello ed è possibile implementare una macchina di Turing. Pertanto, tutto ciò che è computabile, può essere implementato in una lingua che non ha ricorsione. Pertanto, c'è niente che la ricorsione può darti in termini di computabilità a cui il semplice looping non può fare.
Questo in realtà si riduce a pochi punti:
Questo non vuol dire che ci siano alcune classi di problemi che possono essere più facilmente pensate con ricorsione piuttosto che con cicli, o con cicli piuttosto che con ricorsione. Tuttavia, anche questi strumenti sono ugualmente potenti.
E mentre lo portavo all'estremo "esolang" (soprattutto perché puoi trovare le cose che sono complete e implementate da Turing in modi piuttosto strani), ciò non significa che gli esolang siano assolutamente facoltativi. C'è un intero elenco di cose che Turing è completato accidentalmente inclusi i modelli Magic the Gathering, Sendmail, MediaWiki e Sistema di tipo Scala. Molti di questi sono tutt'altro che ottimali quando si tratta di fare qualcosa di concreto, è solo che puoi calcolare tutto ciò che è computabile usando questi strumenti.
Questa equivalenza può essere particolarmente interessante quando si entra in un particolare tipo di ricorsione noto come chiamata a coda .
Se hai, diciamo, un metodo fattoriale scritto come:
int fact(int n) {
return fact(n, 1);
}
int fact(int n, int accum) {
if(n == 0) { return 1; }
if(n == 1) { return accum; }
return fact(n-1, n * accum);
}
Questo tipo di ricorsione verrà riscritto come un loop - nessuna pila utilizzata. Tali approcci sono infatti spesso più eleganti e più facili da capire rispetto al ciclo equivalente che viene scritto, ma ancora una volta, per ogni chiamata ricorsiva può esserci un ciclo equivalente scritto e per ogni ciclo può essere scritta una chiamata ricorsiva.
Ci sono anche momenti in cui la conversione del ciclo semplice in una chiamata ricorsiva chiamata coda può essere complicata e più difficile da comprendere.
Se vuoi approfondire la teoria, vedi la tesi di Church Turing . Puoi anche trovare utile la chiesa-tesi di dottorato su CS.SE.
Are there any cases where a task can only be done using recursion, rather than a loop?
È sempre possibile trasformare l'algoritmo ricorsivo in un ciclo, che utilizza una struttura dati Last-In-First-Out (stack AKA) per memorizzare lo stato temporaneo, perché la chiamata ricorsiva è esattamente quella, memorizzando lo stato corrente in uno stack, procedendo con l'algoritmo, quindi ripristinando in seguito lo stato. La risposta così breve è: No, non ci sono casi simili .
Tuttavia, un argomento può essere fatto per "sì". Facciamo un esempio concreto e semplice: unire l'ordinamento. È necessario dividere i dati in due parti, unire le parti e quindi unirle. Anche se non si esegue una chiamata di funzione del linguaggio di programmazione effettivo per unire l'ordinamento in modo da eseguire l'unire l'ordinamento sulle parti, è necessario implementare funzionalità identiche a quelle che effettivamente fanno una chiamata di funzione (push state al proprio stack, passare a inizio del ciclo con diversi parametri di partenza, quindi in seguito far uscire lo stato dallo stack).
È una ricorsione, se implementi la chiamata di ricorsione, come passi separati "push state" e "jump to beginning" e "pop state"? E la risposta è: No, non è ancora chiamato ricorsione, si chiama iterazione con stack esplicito (se si desidera utilizzare la terminologia stabilita).
Nota, questo dipende anche dalla definizione di "task". Se il compito è di ordinare, allora puoi farlo con molti algoritmi, molti dei quali non hanno bisogno di alcun tipo di ricorsione. Se l'attività consiste nell'implementare algoritmi specifici, come merge sort, allora si applica l'ambiguità di cui sopra.
Quindi consideriamo la domanda, ci sono compiti generali, per i quali esistono solo algoritmi ricorsivi. Dal commento di @WizardOfMenlo alla domanda, la funzione Ackermann è un semplice esempio di ciò. Quindi il concetto di ricorsione sta da solo, anche se può essere implementato con un diverso costrutto di programma per computer (iterazione con stack esplicito).
Dipende da quanto rigorosamente definisci "ricorsione".
Se lo richiediamo rigorosamente per coinvolgere lo stack delle chiamate (o qualunque meccanismo per mantenere lo stato del programma), possiamo sempre sostituirlo con qualcosa che non lo è. Infatti, i linguaggi che portano naturalmente ad un uso intensivo della ricorsione tendono ad avere compilatori che fanno un uso pesante dell'ottimizzazione di coda, quindi ciò che scrivi è ricorsivo, ma ciò che viene eseguito è iterativo.
Ma consideriamo un caso in cui facciamo una chiamata ricorsiva e usiamo il risultato di una chiamata ricorsiva per quella chiamata ricorsiva.
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
if (m == 0)
return n+1;
if (n == 0)
return Ackermann(m - 1, 1);
else
return Ackermann(m - 1, Ackermann(m, n - 1));
}
Rendere semplice la prima chiamata ricorsiva è semplice:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
if (m == 0)
return n+1;
if (n == 0)
{
m--;
n = 1;
goto restart;
}
else
return Ackermann(m - 1, Ackermann(m, n - 1));
}
Possiamo quindi ripulire rimuovendo goto per respingere velociraptors e l'ombra di Dijkstra:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
while(m != 0)
{
if (n == 0)
{
m--;
n = 1;
}
else
return Ackermann(m - 1, Ackermann(m, n - 1));
}
return n+1;
}
Ma per rimuovere le altre chiamate ricorsive dovremo memorizzare i valori di alcune chiamate in uno stack:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
Stack<BigInteger> stack = new Stack<BigInteger>();
stack.Push(m);
while(stack.Count != 0)
{
m = stack.Pop();
if(m == 0)
n = n + 1;
else if(n == 0)
{
stack.Push(m - 1);
n = 1;
}
else
{
stack.Push(m - 1);
stack.Push(m);
--n;
}
}
return n;
}
Ora, quando consideriamo il codice sorgente, abbiamo sicuramente trasformato il nostro metodo ricorsivo in un iterativo.
Considerando ciò che è stato compilato, abbiamo trasformato il codice che utilizza lo stack di chiamate per implementare la ricorsione in codice che non lo fa (e così facendo trasforma il codice che genererà un'eccezione di overflow dello stack per valori anche piuttosto piccoli in codice ciò richiederà semplicemente un lungo periodo di tempo estremamente lungo da restituire [vedi Come posso evitare che la funzione Ackerman trabocchi dallo stack? per ulteriori ottimizzazioni che lo fanno effettivamente tornare per molti più ingressi possibili]).
Considerando il modo in cui la ricorsione viene implementata in generale, abbiamo trasformato il codice che utilizza lo stack di chiamate in codice che utilizza uno stack diverso per contenere le operazioni in sospeso. Potremmo quindi sostenere che è ancora ricorsivo, se considerato a quel livello basso.
E a quel livello, non ci sono davvero altri modi per aggirarlo. Quindi se consideri tale metodo come ricorsivo, allora ci sono davvero cose che non possiamo fare senza di esso. Generalmente però non etichettiamo tale codice ricorsivo. Il termine ricorsione è utile perché copre un certo insieme di approcci e ci dà modo di parlarne, e non ne usiamo più uno.
Naturalmente, tutto questo presuppone che tu abbia una scelta. Ci sono due lingue che proibiscono le chiamate ricorsive e le lingue che non hanno le strutture di loop necessarie per iterare.
La risposta classica è "no", ma permettimi di approfondire perché penso che "sì" sia una risposta migliore.
Prima di andare, prendiamo qualcosa di fuori mano: da una computability & punto di vista della complessità:
Ok, ora, mettiamo un piede in terra pratica, mantenendo l'altro piede in teoria-terra.
Lo stack di chiamate è una struttura controllo , mentre uno stack manuale è una struttura dati . Controllo e dati sono non concetti uguali, ma sono equivalenti nel senso che possono essere ridotti l'un l'altro (o "emulati" l'uno con l'altro) dal punto di vista della computabilità o della complessità.
Quando potrebbe essere importante questa distinzione? Quando lavori con strumenti del mondo reale. Ecco un esempio:
Supponiamo che stai implementando N-way mergesort . Potresti avere un ciclo for che attraversa ciascuno dei segmenti N , chiama mergesort su di essi separatamente, quindi unisce i risultati.
Come potresti parallelizzare questo con OpenMP?
Nel regno ricorsivo, è estremamente semplice:
basta mettere #pragma omp parallel for attorno al tuo loop che va da 1 a N, e il gioco è fatto.
Nel regno iterativo, non puoi farlo. Devi generare manualmente le discussioni e passare manualmente i dati appropriati in modo che sappiano cosa fare.
D'altra parte, ci sono altri strumenti (come i vettori automatici, ad esempio #pragma vector ) che funzionano con i loop ma sono completamente inutili con la ricorsione.
Essere punto, solo perché puoi dimostrare che i due paradigmi sono equivalenti matematicamente, ciò non significa che siano uguali nella pratica. Un problema che potrebbe essere banale automatizzare in un paradigma (ad esempio, la parallelizzazione del ciclo) potrebbe essere molto più difficile da risolvere nell'altro paradigma.
Di conseguenza, se hai bisogno di uno strumento per risolvere un problema, è probabile che lo strumento funzioni solo con un particolare tipo di approccio, e di conseguenza non riuscirai a risolvere il problema con un approccio diverso, anche se puoi dimostrare matematicamente il problema può essere risolto in entrambi i modi.
Mettendo da parte il ragionamento teorico, diamo un'occhiata a quale sia la ricorsione e i loop dal punto di vista della macchina (hardware o virtuale). La ricorsione è una combinazione di flusso di controllo che consente di avviare l'esecuzione di alcuni codici e di tornare al completamento (in una vista semplicistica quando i segnali e le eccezioni vengono ignorati) e dei dati passati a quell'altro codice (argomenti) e che viene restituito da (risultato). Di solito non è implicata alcuna gestione esplicita della memoria, tuttavia esiste un'allocazione implicita della memoria stack per salvare indirizzi di ritorno, argomenti, risultati e dati locali intermedi.
Un ciclo è una combinazione di flusso di controllo e dati locali. Confrontando questo con la ricorsione possiamo vedere che la quantità di dati in questo caso è fissa. L'unico modo per superare questa limitazione è utilizzare la memoria dinamica (anche conosciuta come heap ) che può essere allocata (e liberata) ogni volta che è necessario.
Per riassumere:
Supponendo che la parte controllo flusso sia ragionevolmente potente, l'unica differenza è nei tipi di memoria disponibili. Quindi, ci rimangono 4 casi (il potere espressivo è elencato tra parentesi):
Se le regole del gioco sono un po 'più rigide e l'implementazione ricorsiva non è consentita per utilizzare i loop, otteniamo invece questo:
La differenza chiave con lo scenario precedente è che la mancanza di memoria dello stack non consente la ricorsione senza cicli per fare più passaggi durante l'esecuzione rispetto a linee di codice.
Sì. Ci sono diversi compiti comuni che sono facili da realizzare usando la ricorsione ma impossibile con i loop:
C'è una differenza tra le funzioni ricorsive e le funzioni ricorsive primitive. Le funzioni ricorsive primitive sono quelle che vengono calcolate utilizzando cicli, in cui viene calcolato il numero massimo di iterazioni di ciascun ciclo prima che inizi l'esecuzione del ciclo. (E "ricorsivo" qui non ha nulla a che fare con l'uso della ricorsione).
Le funzioni ricorsive primitive sono strettamente meno potenti delle funzioni ricorsive. Otterresti lo stesso risultato se hai assunto funzioni che utilizzano la ricorsione, in cui la profondità massima della ricorsione deve essere calcolata in anticipo.
Se stai programmando in c ++ e usi c ++ 11, allora c'è una cosa che deve essere fatta usando le ricorsioni: le funzioni di constexpr. Ma lo standard limita questo a 512, come spiegato in questa risposta . L'uso di loop in questo caso non è possibile, poiché in tal caso la funzione non può essere constexpr, ma questa viene modificata in c ++ 14.
Sono d'accordo con le altre domande. Non c'è niente che puoi fare con la ricorsione che non puoi fare con un loop.
MA , secondo me la ricorsione può essere molto pericolosa. Innanzitutto, per alcuni è più difficile capire cosa stia realmente accadendo nel codice. In secondo luogo, almeno per C ++ (Java non sono sicuro) ogni passaggio di ricorsione ha un impatto sulla memoria perché ogni chiamata al metodo causa l'accumulo di memoria e l'inizializzazione dell'intestazione dei metodi. In questo modo puoi far esplodere il tuo stack. Basta provare la ricorsione dei numeri di Fibonacci con un alto valore di input.