1. Se n == 1, allora tutto è banale. È chiamata la base della ricorsione, perché produce immediatamente il risultato ovvio:pow(x, 1) uguale ax.
2. Altrimenti, possiamo rappresentare pow(x, n)comex * pow(x, n - 1)., In matematica, si scriverebbe xn = x * xn-1. Questo è chiamato passo ricorsivo: trasformiamo l’attività in un’azione più semplice (moltiplicazione per x) e una chiamata più semplice dello stesso compito (pow con inferiore n). I passaggi successivi lo semplificano sempre di più fino a quando n raggiunge 1.

Possiamo anche dire che powsi chiama ricorsivamente till n == 1.,

Per esempio, per calcolare pow(2, 4) ricorsiva variante fa questi passaggi:

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

Così, la ricorsione riduce la chiamata di una funzione di una più semplice, e quindi – per ancora più semplici, e così via, fino a quando il risultato diventa evidente.,

Il numero massimo di chiamate nidificate (inclusa la prima) è chiamato profondità di ricorsione. Nel nostro caso, sarà esattamente n.

La profondità massima di ricorsione è limitata dal motore JavaScript. Possiamo contare sul fatto che sia 10000, alcuni motori consentono di più, ma 100000 è probabilmente fuori limite per la maggior parte di essi. Esistono ottimizzazioni automatiche che aiutano ad alleviare questo (“tail calls optimizations”), ma non sono ancora supportate ovunque e funzionano solo in casi semplici.

Che limita l’applicazione della ricorsione, ma rimane ancora molto ampia., Ci sono molte attività in cui il modo di pensare ricorsivo fornisce un codice più semplice, più facile da mantenere.

Il contesto di esecuzione e lo stack

Ora esaminiamo come funzionano le chiamate ricorsive. Per questo guarderemo sotto il cofano delle funzioni.

Le informazioni sul processo di esecuzione di una funzione in esecuzione sono memorizzate nel suo contesto di esecuzione.,

Il contesto di esecuzione è una struttura dati interna che contiene dettagli sull’esecuzione di una funzione: dove è ora il flusso di controllo, le variabili correnti, il valore dithis (non lo usiamo qui) e pochi altri dettagli interni.

Una chiamata di funzione ha esattamente un contesto di esecuzione associato ad essa.

Quando una funzione effettua una chiamata nidificata, si verifica quanto segue:

• La funzione corrente è in pausa.
• Il contesto di esecuzione ad esso associato viene ricordato in una speciale struttura dati chiamata execution context stack.,
• La chiamata nidificata viene eseguita.
• Al termine, il vecchio contesto di esecuzione viene recuperato dallo stack e la funzione esterna viene ripresa da dove si è interrotta.

Vediamo cosa succede durante la chiamatapow(2, 3).

pow(2, 3)

all’inizio della chiamata pow(2, 3) il contesto di esecuzione saranno variabili di archivio: x = 2, n = 3, il flusso di esecuzione è alla riga 1 della funzione.,

Possiamo abbozzarlo come:

• Contesto: { x: 2, n: 3, alla riga 1 } pow(2, 3)

Questo è quando la funzione inizia ad essere eseguita., La condizione n == 1 è falsy, in modo che il flusso continua nel secondo ramo del if:

function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); }}alert( pow(2, 3) );

Le variabili sono le stesse, ma i cambi di linea, in modo che il contesto è ora di:

• Contesto: { x: 2 n: 3, alla riga 5 } pow(2, 3)

calcolare x * pow(x, n - 1), abbiamo bisogno di fare un subcall di pow con nuovi argomenti pow(2, 2).,

pow(2, 2)

Per eseguire una chiamata nidificata, JavaScript ricorda il contesto di esecuzione corrente nello stack del contesto di esecuzione.

Qui chiamiamo la stessa funzionepow, ma assolutamente non importa. Il processo è lo stesso per tutte le funzioni:

1. Il contesto corrente viene “ricordato” in cima allo stack.
2. Il nuovo contesto viene creato per la chiamata secondaria.
3. Quando la chiamata secondaria è terminata, il contesto precedente viene visualizzato dallo stack e la sua esecuzione continua.,

Ecco il contesto stack quando siamo entrati in subcall pow(2, 2):

• Contesto: { x: 2, n: 2, alla riga 1 } pow(2, 2)
• Contesto: { x: 2, n. 3, linea 5 } pow(2, 3)

Il nuovo contesto di esecuzione corrente è superiore (e audace), e precedente ricordato contesti sono al di sotto.

Quando finiamo la chiamata secondaria – è facile riprendere il contesto precedente, perché mantiene entrambe le variabili e il posto esatto del codice in cui si è fermato.,

pow(2, 1)

Il processo si ripete: una nuova chiamata secondaria viene eseguita alla riga5, ora con argomentix=2,n=1.,

Un nuovo contesto di esecuzione è creato il precedente è spinto in cima alla pila:

• Contesto: { x: 2, n: 1, alla riga 1 } pow(2, 1)
• Contesto: { x: 2, n: 2, alla riga 5 } pow(2, 2)
• Contesto: { x: 2, n: 3, linea 5 } pow(2, 3)

Ci sono 2 vecchi contesti ora e 1 ora in lizza per pow(2, 1).,

uscita

Durante l’esecuzione del pow(2, 1), a differenza di prima, la condizione n == 1 è truthy, in modo che il primo ramo di if funziona:

function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); }}

non Ci sono più chiamate nidificate, in modo che la funzione termina, di ritorno 2.

Al termine della funzione, il suo contesto di esecuzione non è più necessario, quindi viene rimosso dalla memoria., Il precedente è restaurata la parte superiore della pila:

• Contesto: { x: 2, n: 2, alla riga 5 } pow(2, 2)
• Contesto: { x: 2, n. 3, linea 5 } pow(2, 3)

Poi il contesto precedente, viene ripristinato:

• Contesto: { x: 2, n. 3, linea 5 } pow(2, 3)

Quando finisce, abbiamo un risultato di pow(2, 3) = 8.

La profondità di ricorsione in questo caso era: 3.

Come possiamo vedere dalle illustrazioni sopra, la profondità di ricorsione è uguale al numero massimo di contesto nello stack.

Nota i requisiti di memoria. I contesti prendono memoria., Nel nostro caso, elevare alla potenza din richiede in realtà la memoria pern contesti, per tutti i valori inferiori din.

Un ciclo basato su algoritmo è più memoria di risparmio:

function pow(x, n) { let result = 1; for (let i = 0; i < n; i++) { result *= x; } return result;}

Il processo iterativo pow utilizza un singolo cambiamento di contesto i e result nel processo. I suoi requisiti di memoria sono piccoli, fissi e non dipendono da n.,

Qualsiasi ricorsione può essere riscritta come un ciclo. La variante del ciclo di solito può essere resa più efficace.

But Ma a volte la riscrittura non è banale, specialmente quando la funzione utilizza sottocall ricorsive diverse a seconda delle condizioni e unisce i loro risultati o quando la ramificazione è più intricata. E l’ottimizzazione potrebbe non essere necessaria e totalmente non vale gli sforzi.

La ricorsione può dare un codice più breve, più facile da capire e supportare. Le ottimizzazioni non sono richieste in ogni luogo, per lo più abbiamo bisogno di un buon codice, ecco perché viene utilizzato.,

Attraversamenti ricorsivi

Un’altra grande applicazione della ricorsione è un attraversamento ricorsivo.

Immagina, abbiamo una società. La struttura del personale può essere presentata come un oggetto:

In altre parole, un’azienda ha dipartimenti.

• Un reparto può avere una serie di personale. Ad esempio, il repartosales ha 2 dipendenti: John e Alice.

• O un dipartimento può dividersi in sottodipartimenti, comedevelopmentha due rami:siteseinternals. Ognuno di loro ha il proprio personale.,

• È anche possibile che quando un sottodipartimento cresce, si divide in sottodipartimenti (o squadre).

  Ad esempio, il reparto sites in futuro potrebbe essere diviso in team per siteA e siteB. E loro, potenzialmente, possono dividere ancora di più. Questo non è sulla foto, solo qualcosa da avere in mente.

Ora diciamo che vogliamo una funzione per ottenere la somma di tutti gli stipendi. Come possiamo farlo?

Un approccio iterativo non è facile, perché la struttura non è semplice., La prima idea potrebbe essere quella di creare un ciclofor su company con subloop nidificato su reparti di 1 ° livello. Ma poi abbiamo bisogno di più subloop nidificati per iterare lo staff nei dipartimenti di 2 ° livello come sites then E poi un altro subloop all’interno di quelli per i dipartimenti di 3 ° livello che potrebbero apparire in futuro? Se mettiamo 3-4 subloop nidificati nel codice per attraversare un singolo oggetto, diventa piuttosto brutto.

Proviamo la ricorsione.,

Come possiamo vedere, quando la nostra funzione ottiene un dipartimento da sommare, ci sono due casi possibili:

1. O è un dipartimento “semplice” con una serie di persone – quindi possiamo sommare gli stipendi in un semplice ciclo.
2. O è un oggetto conN sottodipartimenti – allora possiamo fareN chiamate ricorsive per ottenere la somma per ciascuno dei sottodipedi e combinare i risultati.

Il 1 ° caso è la base della ricorsione, il caso banale, quando otteniamo un array.

Il 2 ° caso quando otteniamo un oggetto è il passo ricorsivo., Un’attività complessa è suddivisa in attività secondarie per reparti più piccoli. Possono a loro volta dividere di nuovo, ma prima o poi la divisione finirà a (1).

L’algoritmo è probabilmente ancora più facile da leggere dal codice:

Il codice è breve e facile da capire (si spera?). Questo è il potere della ricorsione. Funziona anche per qualsiasi livello di nidificazione sottodipartimento.,

di seguito il diagramma di chiamate:

si noti che il codice utilizza funzioni intelligenti che abbiamo trattato prima:

• Metodo arr.reduce spiegato nel capitolo Array i metodi per ottenere la somma di un array.
• Loopfor(val of Object.values(obj)) per iterare sui valori dell’oggetto:Object.values restituisce un array di essi.,

Strutture ricorsive

Una struttura di dati ricorsiva (definita ricorsivamente) è una struttura che si replica in parti.

L’abbiamo appena visto nell’esempio di una struttura aziendale sopra.

Un reparto aziendale è:

• O una matrice di persone.
• O un oggetto con reparti.

Per gli sviluppatori web ci sono esempi molto più noti: documenti HTML e XML.

Nel documento HTML, un tag HTML può contenere un elenco di:

• Pezzi di testo.
• HTML-commenti.,
• Altri tag HTML (che a loro volta possono contenere pezzi di testo / commenti o altri tag ecc.).

Questa è ancora una volta una definizione ricorsiva.

Per una migliore comprensione, copriremo un’altra struttura ricorsiva denominata “Elenco collegato” che potrebbe essere un’alternativa migliore per gli array in alcuni casi.

Elenco collegato

Immagina, vogliamo memorizzare un elenco ordinato di oggetti.

La scelta naturale sarebbe un array:

let arr = ;

…Ma c’è un problema con gli array., Le operazioni” elimina elemento “e” inserisci elemento” sono costose. Ad esempio, l’operazionearr.unshift(obj) deve rinumerare tutti gli elementi per fare spazio a un nuovoobj, e se l’array è grande, ci vuole tempo. Lo stesso con arr.shift().

Le uniche modifiche strutturali che non richiedono la rinumerazione di massa sono quelle che operano con la fine dell’array: arr.push/pop. Quindi un array può essere piuttosto lento per le grandi code, quando dobbiamo lavorare con l’inizio.,

In alternativa, se abbiamo davvero bisogno di inserimento / cancellazione veloce, possiamo scegliere un’altra struttura di dati chiamata elenco collegato.

L’elemento della lista collegata è ricorsivamente definito come un oggetto con:

• value.
• next proprietà che fa riferimento al prossimo elemento della lista collegata onull se questa è la fine.,

For instance:

let list = { value: 1, next: { value: 2, next: { value: 3, next: { value: 4, next: null } } }};

Graphical representation of the list:

An alternative code for creation:

let list = { value: 1 };list.next = { value: 2 };list.next.next = { value: 3 };list.next.next.next = { value: 4 };list.next.next.next.next = null;

Here we can even more clearly see that there are multiple objects, each one has the value and next pointing to the neighbour., La variabilelist è il primo oggetto della catena, quindi seguendo i puntatorinext da esso possiamo raggiungere qualsiasi elemento.

L’elenco può essere facilmente diviso in più parti e più tardi si unì indietro:

let secondList = list.next.next;list.next.next = null;

Per partecipare:

list.next.next = secondList;

E sicuramente siamo in grado di inserire o rimuovere elementi in qualsiasi luogo.,head of the list:

To remove a value from the middle, change next of the previous one:

list.next = list.next.next;

We made list.next jump over 1 to value 2., Il valore 1 è ora escluso dalla catena. Se non è memorizzato da nessun’altra parte, verrà automaticamente rimosso dalla memoria.

A differenza degli array, non c’è una rinumerazione di massa, possiamo facilmente riorganizzare gli elementi.

Naturalmente, gli elenchi non sono sempre migliori degli array. Altrimenti tutti userebbero solo elenchi.

Lo svantaggio principale è che non possiamo accedere facilmente a un elemento dal suo numero. In un array che è facile: arr è un riferimento diretto., Ma nella lista dobbiamo iniziare dal primo elemento e andare next N volte per ottenere l’ennesimo elemento.

But Ma non abbiamo sempre bisogno di tali operazioni. Ad esempio, quando abbiamo bisogno di una coda o anche di un deque – la struttura ordinata che deve consentire l’aggiunta/rimozione molto veloce di elementi da entrambe le estremità, ma l’accesso al suo centro non è necessario.

Gli elenchi possono essere migliorati:

• Possiamo aggiungere proprietà prevoltre a next per fare riferimento all’elemento precedente, per tornare indietro facilmente.,
• Possiamo anche aggiungere una variabile chiamata tail facendo riferimento all’ultimo elemento dell’elenco (e aggiornarlo quando si aggiungono/rimuovono elementi dalla fine).
• …La struttura dei dati può variare in base alle nostre esigenze.

Sommario

Termini:

• La ricorsione è un termine di programmazione che significa chiamare una funzione da se stessa. Le funzioni ricorsive possono essere utilizzate per risolvere compiti in modo elegante.

  Quando una funzione si chiama, viene chiamato un passo di ricorsione., La base della ricorsione sono gli argomenti della funzione che rendono l’attività così semplice che la funzione non effettua ulteriori chiamate.

• Una struttura dati definita ricorsivamente è una struttura dati che può essere definita utilizzando se stessa.

  Ad esempio, l’elenco collegato può essere definito come una struttura dati costituita da un oggetto che fa riferimento a un elenco (o null).

  list = { value, next -> list }

  Anche gli alberi come HTML elements tree o department tree di questo capitolo sono naturalmente ricorsivi: si diramano e ogni ramo può avere altri rami.,

  Le funzioni ricorsive possono essere utilizzate per camminarle come abbiamo visto nell’esempiosumSalary.

Qualsiasi funzione ricorsiva può essere riscritta in una iterativa. E questo a volte è necessario per ottimizzare le cose. Ma per molte attività una soluzione ricorsiva è abbastanza veloce e più facile da scrivere e supportare.