Introduzione alla Ricorsione
La ricorsione è uno strumento brillante per la programmazione. Vi fornisce una soluzione semplice ma potente per affrontare vari problemi. Detto questo, la ricorsione a volte può essere un po’ complicata, soprattutto per i principianti. Spesso le persone hanno difficoltà a pensare in modo ricorsivo per vedere come possono affrontarla. Inoltre, le persone hanno anche difficoltà a scrivere un programma ricorsivo che non richieda un tempo di esecuzione eccessivo. In questo articolo discuteremo i fondamenti della ricorsione, aiutandovi ad affinare o sviluppare questa essenziale abilità di programmazione.
La ricorsione spiegata
La ricorsione è un metodo per risolvere i problemi attraverso categorie più piccole dello stesso problema. Risolviamo i problemi attraverso i sotto-problemi fino ad arrivare alla sua versione più piccola, nota anche come caso base. Spesso le persone hanno difficoltà a capire la ricorsione per vari motivi. Una funzione ricorsiva continua a chiamarsi da sola fino a quando l’esecuzione si ferma, e una condizione di base diventa vera. Ci sono due parti due una funzione ricorsiva:
- Il caso di base
- La struttura ricorsiva
Caso base
La base è la parte più piccola del problema. Sorprendentemente, conosciamo la condizione o la soluzione finale in cui la funzione potrebbe restituire immediatamente i risultati.
La struttura ricorsiva
Trovare la risposta ad un problema attraverso la soluzione del suo sotto-problema è una struttura ricorsiva. Ancora una volta, le cose si fanno confuse perché la funzione si chiama a rompere la sfida attuale ad un livello diretto.
Capire la ricorsione attraverso il problema del conto alla rovescia
È necessario stampare i numeri che iniziano da N a uno in ordine decrescente. Dobbiamo rompere la soluzione del problema per trovare versioni più piccole del problema. Pertanto, sarebbe meglio stampare prima N e poi chiamare la funzione per stampare il resto della N a un numero.
Stampa di cifre da N a uno uguale a stampa (N) + Stampa da N-uno a uno
In questo esempio, il primo è il problema originale, e il secondo (N-uno a uno è il sottoproblema.) Dovete pensare, la catena di chiamata funzionale deve fermarsi da qualche parte, e quale potrebbe essere il caso di base?
Caso base
Il conto alla rovescia deve concludersi dopo la stampa di uno. Ora, dobbiamo inserire una condizione di base per terminare l’esecuzione del programma. Ora dobbiamo fondere il caso di base e la struttura ricorsiva per scrivere l’intera implementazione ricorsiva del problema discusso in precedenza.
Qual è il punto di utilizzo della ricorsione?
La ricorsione spesso brilla in situazioni con problemi complessi. Sarebbe anche giusto dire che si innalza alle occasioni in cui il problema è più complicato del solito. Inoltre, è possibile applicare la ricorsione con quasi tutti i problemi. Tuttavia, ci sono scenari particolari in cui la ricorsione è particolarmente utile. Ecco una situazione in cui la ricorsione brilla di più.
Grafici, reti, gerarchie
Quando parliamo di algoritmi e parliamo di grafici, di solito non parliamo del grafico che evidenzia la relazione tra variabili come il grafico di valutazione Top Coder (si concentra sulla relazione tra la valutazione e il tempo), ma parliamo per lo più di una rete di persone, cose e concetti collegati in diversi modi.
Per esempio, si potrebbe immaginare una mappa stradale come un grafico che mostra le città e le loro connessioni con le strade. I grafici possono essere massicci, complicati e difficili da gestire, programmaticamente parlando. Inoltre, sono abbastanza simili nelle competizioni di algoritmi e nella teoria degli algoritmi. Fortunatamente, è possibile utilizzare la ricorsione quando si lavora con elementi complicati come reti e grafici.
Come risolvere i problemi utilizzando la ricorsione?
Sareste sorpresi di sapere quanto sia necessario utilizzare il vostro processo di pensiero per risolvere i problemi in modo ricorsivo. Ecco un metodo efficace che dovreste considerare perché vi aiuterà a decidere i casi di base e la struttura ricorsiva con facilità:
- Come posso risolvere una soluzione trovando i sotto-problemi di un problema più significativo?
- Non c’è motivo di preoccuparsi del problema del sotto-problema, perché la ricorsione lo risolverà
- Annotare una struttura ricorsiva con le corrette condizioni al contorno e il parametro di funzione
- Determinare i casi di base. Come detto in precedenza, sono la versione più piccola del problema più grande. Siete già a conoscenza delle soluzioni. Inoltre, pensate alle conseguenze di non scrivere una base o di scegliere la base sbagliata.
La comprensione dei sottoproblemi e la loro natura sono essenziali nelle soluzioni ricorsive. Ecco un paio di esempi:
Programmazione dinamica
Risolvere i problemi attraverso molteplici sotto-problemi, ma i sotto-problemi sono dipendenti.
Dividere e conquistare
Utilizzando altri elementi oltre ai sottoproblemi, dove ci sono sottoproblemi indipendenti.
Dove si applica la ricorsione
- Progettazione di algoritmi di approssimazione correlati
- Algoritmi di ordinamento ben riconosciuti come Merge Sort o Quick Sort
- Risoluzione dei problemi attraverso il backtracking e una ricerca esaustiva
- Risoluzione dei problemi con l’aiuto della programmazione dinamica
- Usare un approccio “divide et impera” per risolvere i problemi
- Trovare soluzioni ai problemi dei grafici
- Alla ricerca di risposte ai problemi degli alberi
- Risolvere i problemi relativi ai collegamenti e alle liste di array
Perché la ricorsione è essenziale
Ecco alcune ottime ragioni per cui la ricorsione è vantaggiosa per i programmatori e gli sviluppatori:
- Le soluzioni ricorsive sono per lo più più più pulite rispetto ad una soluzione iterativa. Ci sono casi in cui è possibile ridurre da
50 linee a5 a 10 linee di ricorsione. - In alcuni casi il pensiero ricorsivo è più naturale. La ricorsione è probabilmente il modo più semplice e trasparente per risolvere i problemi di struttura dei dati, ad esempio, alberi con strutture ricorsive semplici.
- Alcuni problemi sono abbastanza complicati e, in alcuni casi, impossibili da risolvere usando l’iterazione.
- La ricorsione è un’opzione eccellente in quanto divide i problemi in sottoproblemi indipendenti e più piccoli, rendendo più semplice la parallelizzazione.
Concetti vitali della ricorsione da esplorare
- Confronto tra ricorsione e iterazione
- Diversi tipi di ricorsione e le loro proprietà
- Usare il metodo dell’albero di ricorsione per analizzare la ricorsione
- Utilizzare il Teorema del Maestro per analizzare la ricorsione
- Pro e contro della programmazione ricorsiva
- Capire come convertire il conde iterativo in codice ricorsivo e viceversa
Perché si verifica una ricorsione con errori di overflow dello stack?
Dobbiamo avere una comprensione completa di ogni funzione per trarre vantaggio dalla ricorsione. Altrimenti, potremmo avere tonnellate di errori di debug complicati. Naturalmente, il tempo può essere poco tempo a volte, ma è meglio iniziare a scrivere esattamente quale sia il ruolo di una particolare funzione.
La ricorsione sarà immensamente utile nel mondo reale e nella programmazione di Top Coder. Sareste sorpresi di vedere quanti programmatori esperti trovano la ricorsione minacciosa. Praticarla vi aiuterà a pensare in modo ricorsivo e alla fine risolverà i problemi di programmazione più complessi.