Risorse per migliorare la comprensione della ricorsione? [chiuso]

Inizia con qualcosa di semplice e traccia con carta e matita. Seriosuly. Un buon punto di partenza sono gli algoritmi di attraversamento degli alberi, dal momento che sono molto più facili da gestire con la ricorsione rispetto alla normale iterazione. Non deve essere un esempio complicato, ma qualcosa di semplice e con cui puoi lavorare.

Sì, è strano ea volte contro-intuitivo, ma quando fa clic, una volta che dici "Eureka!" ti chiederai come non l'hai capito prima! ;) Ho suggerito gli alberi perché sono (IMO) la struttura più semplice da capire in ricorsione, e sono facili da usare con carta e matita. ;)

Raccomando strongmente Scheme, usando il libro The Little Lisper. Una volta che hai finito, capirà la ricorsione, in fondo. Quasi garantito.

Suggerisco senz'altro SICP. Inoltre, dovresti dare un'occhiata ai video del corso introduttivo degli autori qui ; sono incredibilmente aperti alla mente.

Un'altra strada, non strettamente legata alla programmazione, sta leggendo Gödel, Escher, Bach: una trina eterna dorata di Hofstadter. Una volta ottenuto il risultato, la ricorsione apparirà naturale come l'aritmetica. Inoltre, sarai convinto che P = nP e vorresti costruire macchine pensanti, ma è un effetto collaterale così piccolo rispetto ai benefici.

In pratica si tratta solo di esercitarsi ... Prendere problemi generali (ordinamento, ricerca, problemi matematici, ecc.) e vedere se è possibile vedere un modo in cui questi problemi possono essere risolti se si applica una singola funzione più volte .

Ad esempio, l'ordinamento rapido opera nel senso che sposta l'elemento in una lista in due parti e poi si applica nuovamente a ciascuna di quelle metà. Quando si verifica l'ordinamento iniziale, non è preoccupato di ottenere le due metà ordinate in quel punto. Piuttosto sta prendendo l'elemento pivot e mettendo tutti gli elementi più piccoli di quell'elemento da un lato e tutti gli elementi più grandi o uguali dall'altro. Ha senso come possa chiamarsi ricorsivamente a quel punto per ordinare le due nuove liste più piccole? Sono anche liste. Semplicemente più piccolo. Ma devono ancora essere ordinati.

Il potere dietro la ricorsione è la nozione di divide et impera. Rompere un problema ripetutamente in problemi più piccoli che sono di natura identica ma solo più piccoli. Se lo fai abbastanza alla fine arrivi ad un punto in cui l'unico pezzo rimanente è già stato risolto, allora ti ritrovi fuori dal giro e il problema è risolto. Studia quegli esempi che hai menzionato finché non li capisci . Potrebbe volerci un po ', ma alla fine diventerà più facile. Quindi prova a prendere altri problemi e crea una funzione ricorsiva per risolverli! Buona fortuna!

EDIT: Devo anche aggiungere che un elemento chiave per la ricorsione è la capacità garantita della funzione di essere in grado di fermarsi. Ciò significa che l'interruzione del problema originale deve continuamente ottenere minori e alla fine ci deve essere un punto di arresto garantito (un punto in cui il nuovo sottotema è risolvibile o già risolto).

Personalmente ritengo che la tua migliore scommessa sia attraverso la pratica.

Ho imparato la ricorsione con LOGO. Potresti usare LISP. La ricorsione è naturale in quelle lingue. Altrimenti puoi paragonarlo allo studio di serie e serie matematiche in cui esprimi ciò che è successivo in base a ciò che è venuto prima, cioè u (n + 1) = f (u (n)), o serie più complesse in cui hai più variabili e dipendenze multiple, ad es u (n) = g (u (n-1), u (n-2), v (n), v (n-1)); v (n) = h (u (n-1), u (n-2), v (n), v (n-1)) ...

Quindi il mio suggerimento sarebbe che trovi semplici (nella loro espressione) "problemi" di ricorsione standard e cerchi di implementarli nella tua lingua preferita. La pratica ti aiuterà a imparare a pensare, leggere ed esprimere quei "problemi". Nota che spesso alcuni di questi problemi possono essere espressi attraverso l'iterazione, ma la ricorsione potrebbe essere un modo più elegante per risolverli. Uno di questi è il calcolo dei numeri fattoriali.

I "problemi" grafici che trovo rendono più facile vedere. Quindi cerca i fiocchi di Koch, Fibonacci, la curva del drago e i frattali in generale. Ma guarda anche l'algoritmo di ordinamento rapido ...

È necessario arrestare alcuni programmi (cicli infiniti, uso provvisorio di risorse infinite) e gestire in modo errato le condizioni finali (per ottenere risultati imprevisti) prima di riuscire a capirlo. E anche quando lo prendi farai ancora quegli errori, solo meno spesso.

Struttura e interpretazione dei programmi per computer

È il il libro utilizzato per l'apprendimento, non solo la ricorsione, ma la programmazione in generale in varie università. È uno di quei libri fondamentali che fornisce più informazioni, più esperienza guadagni e più leggi.

Per quanto mi piaccia SICP e Gödel, Escher, Bach: un'eterna treccia d'oro , LISP di Touretzky: una delicata introduzione al calcolo simbolico fa anche un buon lavoro nell'introdurre la ricorsione.

Il concetto di base è questo: in primo luogo, devi sapere quando la tua funzione ricorsiva è finita, in modo che possa restituire un risultato. Quindi, devi sapere come prendere il caso incompleto e ridurlo a qualcosa su cui puoi ricorrere. Per l'esempio fattoriale tradizionale (N), hai finito quando N < = 1, e il caso non finito è N * fattoriale (N-1).

Per un esempio molto più brutto, c'è la funzione di Ackermann A (m, n).

A(0,n) = n+1.                                   This is the terminal case.
A(m,0) = A(m-1,1) if m > 0.                     This is a simple recursion.
A(m,n) = A(m-1, A(m, n-1)) if m > 0 and n > 0.  This one is ugly.

Suggerisco di giocare con alcuni linguaggi funzionali in stile ML come OCaml o Haskell. Ho trovato che la sintassi per la corrispondenza dei modelli veramente mi ha aiutato a comprendere anche funzioni ricorsive relativamente complicate, sicuramente molto meglio delle istruzioni if e cond di Scheme. (Ho imparato Haskell e Scheme allo stesso tempo.)

Ecco un esempio banale di contrasto:

(define (fib n)
   (cond [(= n 0) 0]
         [(= n 1) 1]
         [else (+ (fib (- n 1)) (fib (- n 2)))]))

e con la corrispondenza del modello:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Questo esempio non rende giustizia alla differenza - non ho mai avuto problemi con entrambe le versioni della funzione. È solo per illustrare come sono le due opzioni. Una volta che arrivi a funzioni molto più complesse, usando cose come elenchi e alberi, la differenza diventa molto più pronunciata.

Raccomando particolarmente Haskell perché è un linguaggio semplice con una sintassi molto bella. Rende anche molto più facile lavorare con idee più avanzate come corecursion :

fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)
fib n = fibs !! n

(Non comprenderete il codice sopra finché non giocherete un po 'con Haskell, ma state certi che è fondamentalmente magico: P.) Certo, potreste fare lo stesso con i flussi in Scheme, ma è molto più naturale in Haskell.

È esaurito, ma se riesci a trovarlo, "Algoritmi ricorsivi" di Richard Lorentz non è altro che ricorsione. Copre le basi della ricorsione, oltre a specifici algoritmi ricorsivi.

Gli esempi sono in Pascal, ma non sono così grandi che la scelta della lingua è fastidiosa.