Ricorsione

Ricorsione

> Tutorial LeekScript

Prerequisiti:

----

La ricorsione, in senso lato, è la capacità di un oggetto di riferirsi a se stesso. Nel mondo reale, questo è più evidente nei frattali, così come quando due specchi sono posti uno di fronte all'altro. Troviamo anche questa nozione in frasi dello stile: "Sogno che sogno che sogno." o "Penso che scrivo che sogno che penso che scrivo...", etc Nella programmazione, questo si manifesta principalmente con funzioni che si chiamano:

funzione ciclo() { loop(); }

La funzione sopra è la funzione ricorsiva più semplice che ci sia. Quando viene chiamato, non fa altro che chiamare se stesso. È lo stesso che usare un ciclo infinito (es. while(true);). Useremo questa funzione come scheletro di base per tutte le nostre future funzioni ricorsive.

Ricorsione

La ricorsione è analoga alla decostruzione. Si trova principalmente negli algoritmi di tipo ''Divide and Conquer''. Per risolvere il nostro problema, iniziamo suddividendolo in sottoproblemi più facili da risolvere, ripetiamo il processo finché non troviamo un problema che sappiamo risolvere direttamente e da lì risolviamo i problemi superiori combinando i nostri precedenti soluzioni.

Imposta Somma da 0 a n

Vogliamo definire una funzione prendendo un numero intero n come parametro e restituendo la somma di 0 a n (es. 0 + 1 + ... + n). Prendendo il nostro scheletro di base, possiamo iniziare con la seguente funzione:

funzione sommaN(n) { sommaN(?); ritorno?; }

Al momento abbiamo le seguenti informazioni:

Quando si lavora in modo ricorsivo, è sempre una buona idea iniziare con la condizione di arresto. Nel caso della ricorsione, vogliamo smettere di creare sottoproblemi quando abbiamo trovato qualcosa che possiamo risolvere. In questo caso, la somma di "0" a "0" è qualcosa che sappiamo come risolvere. 0 è quindi il nostro caso base, possiamo restituire direttamente la somma corrispondente.

funzione sommaN(n) { if (n === 0) { return 0; } altro { sommaN(?); ritorno?; } }

Ora dobbiamo capire come raggiungere il caso base. Potremmo sottrarre n da se stesso, ma in tal caso non saremmo in grado di sommare gli interi tra 0 e n, avremmo solo 0 e n disponibili. Dovremo quindi creare un sottoproblema che possa risolvere una somma con una n più vicina al nostro caso base.

funzione sommaN(n) { if (n === 0) { return 0; } altro { sommaN(n - 1); ritorno?; } }

Ora dobbiamo solo fare la somma, che ci è stata chiesta all'inizio. Qui, la somma di 0 a n è anche la somma della somma di 0 a n - 1 e n.

funzione sommaN(n) { if (n === 0) { return 0; } else { return n + sumN(n - 1); } }

Con un ternario:

funzione sommaN(n) { ritorno n === 0? 0 : n + sommaN(n - 1); }

Sentiti libero di provare il codice nel tuo editor Leekwars. Forse scoprirai il problema principale con la ricorsione. Puoi anche visualizzare l'esecuzione (in modo semplice) su questo sito.

Corecorsione

/!\ Sezione da rifare, ciò che viene mostrato è principalmente la ricorsione della coda. Non adatto a più filiali. /!\ La corecorsione è analoga alla costruzione. A differenza della ricorsione in cui cerchiamo di raggiungere un caso base dal nostro problema principale, nella co-ricorsione partiamo direttamente dal nostro caso base e ci muoviamo verso la soluzione del problema principale.

Ricorsione reciproca

Abbiamo già trattato la ricorsione reciproca con specchi e frasi. In programmazione, con le funzioni, questo si traduce in due o più funzioni che si chiamano a vicenda. Presentiamo di seguito il caso più semplice di ricorsione reciproca:

funzione mutuoLoop() { mutualHelper(); }

funzione mut