INTRODUZIONE
Alcuni problemi vengono risolti più naturalmente usando la ricorsione. Ad esempio, una sequenza come Fibonacci ha una definizione ricorsiva. Ogni numero in esso è la somma dei due numeri precedenti della sequenza. I problemi che richiedono di costruire o tagliare una struttura dati simile ad albero possono anche essere risolti con la ricorsione. Il treno per pensare ricorsivamente ti darà una potente capacità di affrontare questi problemi.
In questo tutorial farò una revisione dettagliata di diverse funzioni ricorsive per vedere come funzionano e mostrano le tecniche che è possibile utilizzare per definire funzioni ricorsive sistematicamente.
Contenuto:
- Qual è la ricorsione?
- Recursion con numeri
- Recursion con elenchi
- Elenchi di costruzione
- Review
Qual è la ricorsione?
Una funzione definita in modo ricorsivo è una funzione definita in termini di una versione più semplice di se stessa. Questo è un esempio semplificato:
function doA(n) { ... doA(n-1);}
per capire come funziona il retrouring concettualmente, vedremo un esempio che non ha nulla a che fare con il codice. Immagina di essere responsabile della risposta telefonate nel tuo lavoro. Poiché questa è una compagnia trafficata, il telefono ha più righe in modo da poter frequentare più chiamate contemporaneamente. Ogni linea telefonica è un pulsante sul ricevitore e quando c’è una chiamata in arrivo il pulsante lampeggerà. Oggi, quando arrivi al lavoro e accendi il telefono, ci sono quattro linee lampeggianti allo stesso tempo. Pertanto inizi a lavorare rispondere a tutte le chiamate.
Rispondi alla linea uno e dire “per favore aspetta”. Quindi rispondi alla linea due e mettilo in attesa. Sotto rispondi alle tre linee e mettilo in attesa. Infine, rispondi alla quarta linea e parla con la persona che stai chiamando. Quando rifinito con la quarta persona si blocchi e rispondi alla terza chiamata. Al termine con la terza chiamata, si riaggancia e rispondi al secondo. Al termine con la seconda chiamata, si riaggancia e rispondi al primo. Quando finisci con quella chiamata, puoi finalmente appendere il telefono.
Ciascuna delle telefonate di questo esempio è come una chiamata ricorsiva in una funzione. Quando si riceve una chiamata, viene posizionato sullo stack di chiamata (in termini di codice). Se non riesci a completare immediatamente una chiamata, lo stai in attesa. Se si ha una chiamata a una funzione che non può essere valutata immediatamente, rimane nello stack di chiamata. Quando puoi rispondere a una chiamata, questo è servito. Quando il tuo codice è in grado di valutare la chiamata a una funzione, viene rimosso dalla pila. Avere questa analogia in mente mentre si controlla i seguenti esempi di codice.
Recursion con numeri
Tutte le funzioni ricorsive necessitano di una custodia di base per poter finire. Tuttavia, il semplice fatto di aggiungere un caso di base alla nostra funzione non impedirà di eseguire infinitamente. La funzione deve fare un passo per avvicinarsi al caso di base. Infine, c’è il passo ricorsivo. Nel passaggio ricorsivo, il problema è ridotto a una versione più piccola del problema.
Supponiamo di avere una funzione che aggiungerà i numeri da 1 a n. Ad esempio, se n = 4, la funzione aggiungerà 1 + 2 + 3 + 4.
Prima determiniamo il caso di base. Trovare il caso base è come trovare il caso in cui il problema può essere risolto senza ricorsione. In questo esempio è quando n è uguale a zero. Zero non ha parti, quindi la nostra ricorsione può interrompere quando si arriva a 0.
In ogni passaggio si sottrai il valore al numero corrente. Qual è il caso ricorsivo? La custodia ricorsiva è la funzione Suma invocata con il numero ridotto.
function sum(num){ if (num === 0) { return 0; } else { return num + sum(--num) }}sum(4); //10
Questo è ciò che accade in ogni passaggio:
- Vai a somma (4).
- 4 è uguale a 0? No. Place Sum (4) in attesa e vai su Sum (3).
- 3 è uguale a 0? No. Place Sum (3) in attesa e andare su Sum (2).
- 2 è uguale a 0? No. Place Sum (2) in attesa e andare su Sum (1).
- 1 è uguale a 0? No. Place Sum (1) in attesa e andare su Sum (0).
- 0 è uguale a 0? Sì. Valuta la somma (0).
- RETA SUM (1).
- RETA SUM (2).
- RETA SUM (3).
- RETA SUM (4).
Questo è un altro modo per vedere come la funzione sta elaborando ogni chiamata:
sum(4)4 + sum(3)4 + ( 3 + sum(2) )4 + ( 3 + ( 2 + sum(1) ))4 + ( 3 + ( 2 + ( 1 + sum(0) )))4 + ( 3 + ( 2 + ( 1 + 0 ) ))4 + ( 3 + ( 2 + 1 ) )4 + ( 3 + 3 ) 4 + 6 10
L’argomento deve cambiare nel caso ricorsivo e avvicinarsi al caso di base. Questo argomento deve essere verificato nel caso base. Nell’esempio precedente, dal momento che stiamo ripristinando il valore uno nel caso ricorsivo dobbiamo verificare se l’argomento è uguale a zero nel nostro caso di base.
Task
- Implementa La funzione sui sumi usando un ciclo invece di ricorsione.
- crea una funzione che moltiplica in modo ricorsiva a due numeri. Ad esempio, comporterà 8. Scrivi ciò che accade durante ogni fase per .
. > Recuperi con elenchi
La ricorsione su un elenco è simile alla ricorsione in un numero, ma invece di ridurre il numero ad ogni passaggio riduriamo l’elenco ad ogni passaggio fino a quando non avremo una lista vuota.
Considera la funzione della somma che riceve una lista come voce e restituisce la somma di tutti gli elementi di quell’elenco. Questa è un’implementazione per la funzione della somma:
function sum(l){ if (empty(l)) { return 0; } else { return car(l) + sum(cdr(l)); }}
La funzione empty restituisce il valore true (true) se L’elenco non ha elementi. La funzione car restituisce il primo elemento nell’elenco. Ad esempio, car() restituisce il valore 1. restituisce l’elenco senza il primo elemento. Ad esempio, cdr() ritorna. Cosa succede quando eseguiamo sum()?
sum()1 + sum()1 + ( 2 + sum() )1 + ( 2 + ( 3 + sum() ))1 + ( 2 + ( 3 + ( 4 + sum() )))1 + ( 2 + ( 3 + ( 4 + 0 ) ))1 + ( 2 + ( 3 + 4 ) )1 + ( 2 + 7 ) 1 + 910
Quando si esegue la ricorsione su un elenco viene rivisto se vuoto. In caso contrario, il passaggio ricorsivo viene eseguito in una versione ridotta dell’elenco.
Task
- rettib su questa funzione somma in modo da utilizzare un ciclo per aggiungere ciascun elemento da ogni elemento da L’elenco anziché usare la ricorsione.
- Definisce una funzione chiamata lunghezza (lunghezza) che riceve un elenco come ingresso e restituisce il numero di elementi in tale elenco. Non è necessario utilizzare la funzione Lunghezza integrata in JavaScript. Ad esempio,
length()deve restituire il valore 4. Scrivi ciò che accade ad ogni passaggio.
Elenchi di costruzione
in L’ultimo esempio stavamo restituendo un numero. Ma supponiamo che vogliamo restituire una lista. Ciò significa che invece di aggiungere un numero al nostro passaggio ricorsivo, dobbiamo aggiungere un elenco. Considera la funzione remove (Elimina), che riceve un elemento e un elenco come voce e restituisce l’elenco senza l’elemento che vogliamo rimuovere. Solo il primo elemento che troviamo verrà eliminato.
Qui, la funzione eq restituisce un valore True (true) se entrambe le voci sono uguali. cons riceve un elemento e un elenco come ingressi e restituisce un nuovo elenco con l’articolo aggiunto all’inizio di esso.
Controlleriamo se il primo elemento nell’elenco è uguale all’elemento che vogliamo cancellare. In tal caso, elimina il primo elemento dall’elenco e restituisce il nuovo elenco. Se il primo elemento non è uguale all’elemento che vogliamo eliminare, prendiamo il primo elemento dall’elenco e aggiungiamolo al passaggio ricorsivo. Il passaggio ricorsivo conterrà la lista con il primo elemento eliminato.
Continueremo ad eliminare gli elementi fino a raggiungere il nostro caso base, che è una lista vuota. Una lista vuota significa che abbiamo viaggiato tutti i suoi elementi. Che cosa fa la funzione remove('c', )?
remove('c', )cons( ‘a’, remove(‘c’, ) )cons( ‘a’ , cons( ‘b’, remove(‘c’, ) ))cons( ‘a’, cons( ‘b’, )cons( ‘a’, )
In una situazione in cui abbiamo bisogno di costruire un elenco, prendiamo il primo elemento e lo aggiungiamo alla parte ricorsiva della nostra lista.
Task
- ripeti la funzione Rimuovi in modo da utilizzare cicli invece di ricorsione per eliminare un elemento da Un elenco.
- Modifica la funzione Rimuovi per rimuovere tutte le occorrenze da un elemento su un elenco. Ad esempio,
remove(‘c’,restituisce. Scrivi cosa succede passo dopo passo.
Review
Una funzione ricorsiva ha tre parti. Il primo è il caso base, che è la condizione terminale. Il secondo è il passo che arriva al nostro caso base. Il terzo è il passaggio ricorsivo, in cui la funzione viene invocata a se stessa con una voce ridotta.
La ricorsione è come iterazione. Qualsiasi funzione che è possibile definire ricorsivamente può anche essere definita utilizzando i cicli. Altri aspetti da considerare quando si utilizza questa tecnica è la ricorsione in elenchi nidificati e l’ottimizzazione delle chiamate ricorsive.
Una grande risorsa per continuare ad imparare sulla recupero è il libro il piccolo schemer. Questo ti insegna a pensare in modo ricorsivo utilizzando un formato di domande e risposte.