Share
Alcuni problemi sono più naturalmente risolti usando la ricorsione. Ad esempio, una sequenza come la sequenza di Fibonacci ha una definizione ricorsiva. Ogni numero nella sequenza è la somma dei due numeri precedenti nella sequenza. Anche i problemi che richiedono di costruire o attraversare una struttura dati ad albero possono essere risolti con la ricorsione. Allenarti a pensare in modo ricorsivo ti darà una potente abilità per attaccare tali problemi.
In questo tutorial, passo passo attraverso diverse funzioni ricorsive per vedere come funzionano e mostrare tecniche che puoi usare per definire sistematicamente le funzioni ricorsive.
Una funzione ricorsivamente definita è 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 la ricorsione concettualmente, vedremo un esempio che non ha nulla a che fare con il codice. Immagina di essere responsabile della risposta alle telefonate al lavoro. Poiché questa è una società impegnata, il telefono ha più linee telefoniche in modo da poter destreggiarsi tra più chiamate contemporaneamente. Ogni linea telefonica è un pulsante sul ricevitore e quando c'è una chiamata in arrivo, il pulsante lampeggia. Oggi, quando si arriva al lavoro e si accende il telefono, ci sono quattro linee lampeggianti contemporaneamente. Quindi vai al lavoro per rispondere a tutte le chiamate.
Prendi la prima linea e dì loro "per favore". Quindi prendi la linea due e mettili in attesa. Quindi, prendi la linea tre e mettili in attesa. Alla fine, la quarta riga rispondi e parla con il chiamante. Al termine del quarto chiamante, si riaggancia e si riprende la terza chiamata. Al termine della terza chiamata, si riaggancia e si riprende la seconda chiamata. Al termine della seconda chiamata, si riaggancia e si riprende la prima chiamata. Quando finisci quella chiamata, puoi finalmente mettere giù il telefono.
Ciascuna telefonata in questo esempio è come una chiamata ricorsiva in una funzione. Quando ricevi una chiamata, questa viene messa nella pila delle chiamate (in codice parla). Se non è possibile completare una chiamata subito, si mette in attesa la chiamata. Se si dispone di una chiamata di funzione che non può essere valutata immediatamente, rimane nello stack di chiamate. Quando sei in grado di rispondere a una chiamata, questa viene ripresa. Quando il tuo codice è in grado di valutare una chiamata di funzione, viene prelevato dallo stack. Tieni a mente questa analogia mentre osservi i seguenti esempi di codice.
Tutte le funzioni ricorsive necessitano di un caso base in modo che terminino. Tuttavia, l'aggiunta di un caso base alla nostra funzione non impedisce l'esecuzione infinita. La funzione deve avere un passo per avvicinarci al caso base. L'ultimo è il passo ricorsivo. Nel passaggio ricorsivo, il problema si riduce a una versione ridotta del problema.
Supponiamo di avere una funzione che somma i numeri da 1 a n. Ad esempio, se n = 4, somma 1 + 2 + 3 + 4.
In primo luogo, determiniamo il caso base. Trovare il caso base può anche essere pensato come trovare il caso in cui il problema può essere risolto senza ricorsione. In questo caso, è quando n è uguale a zero. Zero non ha parti, quindi la nostra ricorsione può fermarsi quando raggiungiamo 0.
Ad ogni passo, si sottrarrà uno dal numero corrente. Qual è il caso ricorsivo? Il caso ricorsivo è la somma della funzione chiamata con il numero ridotto.
function sum (num) if (num === 0) return 0; else return num + sum (- num) sum (4); // 10
Questo è ciò che sta accadendo ad ogni passo:
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 dovrebbe cambiare nel caso ricorsivo e portarti più vicino al caso base. Questo argomento dovrebbe essere testato nel caso base. Nell'esempio precedente, poiché stiamo sottraendo uno nel caso ricorsivo, testiamo se l'argomento è uguale a zero nel nostro caso base.
Accentsconagua
moltiplicare (2,4) restituirà 8. Scrivi cosa succede ad ogni passaggio per moltiplicare (2,4).Il ricorrere in un elenco è simile a ricorrendo a un numero, tranne per il fatto che anziché ridurre il numero ad ogni passaggio, stiamo riducendo l'elenco ad ogni passaggio finché non arriviamo a una lista vuota.
Considera la funzione somma che prende un elenco come input e restituisce la somma di tutti gli elementi nell'elenco. Questa è un'implementazione per la funzione sum:
function sum (l) if (vuoto (l)) restituisce 0; else return car (l) + sum (cdr (l));
Il vuoto la funzione restituisce true se la lista non ha elementi. Il auto la funzione restituisce il primo elemento nell'elenco. Per esempio, auto ([1,2,3,4]) restituisce 1. Il cdr la funzione restituisce la lista senza il primo elemento. Per esempio, cdr ([1,2,3,4]) ritorna [2,3,4]. Cosa succede quando eseguiamo sum ([1,2,3,4])?
somma ([1,2,3,4]) 1 + somma ([2,3,4]) 1 + (2 + somma ([3,4])) 1 + (2 + (3 + somma ([4 ]))) 1 + (2 + (3 + (4 + sum ([])))) 1 + (2 + (3 + (4 + 0))) 1 + (2 + (3 + 4)) 1 + (2 + 7) 1 + 9 10
Quando si ricorre in una lista, controlla se è vuota. Altrimenti, fai il passo ricorsivo su una versione ridotta della lista.
lunghezza (['a', 'b', 'c', 'd']) dovrebbe tornare 4. Scrivi cosa succede ad ogni passaggio.Nell'ultimo esempio, stavamo restituendo un numero. Ma supponiamo di voler restituire una lista. Ciò significherebbe che invece di aggiungere un numero al nostro passo ricorsivo, avremmo bisogno di aggiungere una lista. Considera la funzione rimuovere, che prende un oggetto ed elenca come input e restituisce la lista con l'oggetto rimosso. Solo il primo oggetto trovato verrà rimosso.
function remove (item, l) if (vuoto (l)) return []; else if (eq (car (l), item)) return cdr (l); else return cons (car (l), remove (item, cdr (l))); remove ('c', ['a', 'b', 'c', 'd']) // ['a', 'b', 'd']Qui, il eq la funzione restituisce true se entrambi gli input sono uguali. Il cons la funzione accetta un elemento e un elenco come input e restituisce una nuova lista con l'elemento aggiunto all'inizio di esso.
Controlleremo se il primo elemento nell'elenco è uguale all'elemento che vogliamo rimuovere. In tal caso, rimuovere il primo elemento dall'elenco e restituire il nuovo elenco. Se il primo elemento non è uguale all'elemento che vogliamo rimuovere, prendiamo il primo elemento nell'elenco e lo aggiungiamo al passaggio ricorsivo. Il passo ricorsivo conterrà la lista con il primo elemento rimosso.
Continueremo a rimuovere elementi fino a raggiungere il nostro caso base, che è una lista vuota. Una lista vuota significa che abbiamo attraversato tutti gli elementi nella nostra lista. Cosa fa remove ('c', ['a', 'b', 'c', 'd']) fare?
remove ('c', ['a', 'b', 'c', 'd']) contro ('a', remove ('c', ['b', 'c', 'd']) ) contro ('a', cons ('b', remove ('c', ['c', 'd']))) contro ('a', contro ('b', ['d']) contro ('a', ['b', 'd']) ['a', 'b', 'd']In una situazione in cui abbiamo bisogno di costruire una lista, prendiamo il primo elemento e lo aggiungiamo alla parte ricorsiva della nostra lista.
remove ('c', ['a', 'b', 'c', 'd', 'c'] restituisce ['a', 'b', 'd']. Scrivi cosa succede passo dopo passo.Ci sono tre parti per una funzione ricorsiva. Il primo è il caso base, che è la condizione di chiusura. Il secondo è il passo per avvicinarci al nostro caso base. Il terzo è il passo ricorsivo, in cui la funzione si chiama con l'input ridotto.
La ricorsione è come l'iterazione. Qualsiasi funzione che è possibile definire in modo ricorsivo può anche essere definita utilizzando i loop. Altre cose da considerare quando si usa la ricorsione sono ricorrenti negli elenchi annidati e nell'ottimizzazione delle chiamate ricorsive.
Una grande risorsa per continuare ad apprendere sulla ricorsione è il libro The Little Schemer. Ti insegna come pensare in modo ricorsivo usando un formato di domande e risposte.
