Buone risorse per l'apprendimento della ricorsione [duplicato]

Spotting quando usare la ricorsione è in realtà abbastanza semplice - il concetto chiave sta rilevando che parte del problema è una versione ridotta dell'intero problema . Esempi:

• Le funzioni sugli elenchi possono essere scritte utilizzando la ricorsione se si vede che è possibile ottenere il risultato facendo qualcosa con il primo elemento dell'elenco e quindi chiamando la funzione in modo ricorsivo sul resto dell'elenco. Qui la "versione ridotta dell'intero problema" è il resto dell'elenco escludendo il primo elemento.
• Le funzioni che operano su alberi binari possono spesso utilizzare la ricorsione chiamando ricorsivamente la funzione nella metà sinistra dell'albero e nella metà destra dell'albero e combinando i risultati in qualche modo. Qui la "versione ridotta dell'intero problema" sono i sottoalberi sinistro e destro.
• Le funzioni matematiche definite in modo ricorsivo (ad esempio una funzione per generare i numeri di fibonacci F (n) = F (n-1) + F (n-2)) spesso hanno un'implementazione ricorsiva semplice che rispecchia la definizione matematica. Qui la "versione più piccola dell'intero problema" sono i due numeri precedenti nella sequenza di Fibonacci.

Se vuoi davvero conoscere la ricorsione, allora prendere in considerazione un linguaggio funzionale è una buona idea: la ricorsione è uno stile di programmazione naturale in linguaggi funzionali e ti allontanerai dal ricorrere a soluzioni "imperative". Suggerirei un Lisp-1 (ad esempio Scheme o Clojure) in particolare: alcune delle funzioni ricorsive definite negli elenchi sono cose di bellezza.

Non sono a conoscenza di libri specifici per la ricorsione, ma sono trattati approfonditamente in quasi tutte le introduzioni al libro degli algoritmi.

Fin quando puoi usare la ricorsione, potresti usarlo praticamente su qualsiasi algoritmo. In alcuni linguaggi di programmazione funzionale, devi usare la ricorsione per le cose per le quali altre lingue usano i cicli. Se vuoi praticare la ricorsione, l'apprendimento di una lingua funzionale è un buon passo e troverai tantissimi esempi di ricorsione nei loro tutorial.

Quando è utile usare la ricorsione è un'altra domanda. Mi vengono in mente due situazioni. Il primo è quando ti ritrovi a usare uno stack per una struttura dati. In questa situazione, l'uso della ricorsione ti dà automaticamente uno stack, quindi non devi preoccuparti di quei dettagli. L'altra situazione è quando si dispone di un numero elevato di cicli nidificati o di un livello sconosciuto di nidificazione. La ricorsione rende i loop di nidificazione molto semplici.

Il trucco per comprendere la ricorsione consiste nel non provare a trattenere l'intero stack nella tua testa. Concentrati solo su una piccola parte alla volta. Pensa al tuo stato attuale e confida che i livelli più profondi funzionino come pubblicizzati.