Cos'è la ricorsione?
Il processo in cui una funzione richiama se stessa direttamente o indirettamente è chiamato ricorsione e la funzione corrispondente è chiamata funzione ricorsiva. Utilizzando un algoritmo ricorsivo, alcuni problemi possono essere risolti abbastanza facilmente. Esempi di tali problemi sono Torri di Hanoi (TOH) , Attraversamenti dell'albero in ordine/preordine/postordine , DFS di Graph , ecc. Una funzione ricorsiva risolve un problema particolare richiamando una copia di se stessa e risolvendo sottoproblemi più piccoli dei problemi originali. È possibile generare molte altre chiamate ricorsive come e quando richiesto. È essenziale sapere che dovremmo fornire un determinato caso per terminare questo processo di ricorsione. Quindi possiamo dire che ogni volta la funzione richiama se stessa con una versione più semplice del problema originale.
Necessità di ricorsione
La ricorsione è una tecnica straordinaria con l'aiuto della quale possiamo ridurre la lunghezza del nostro codice e renderlo più facile da leggere e scrivere. Presenta alcuni vantaggi rispetto alla tecnica di iterazione che verranno discussi più avanti. Un'attività che può essere definita con la sua sottoattività simile, la ricorsione è una delle migliori soluzioni per questo. Per esempio; Il Fattoriale di un numero.
Proprietà della ricorsione:
- Eseguire le stesse operazioni più volte con input diversi.
- In ogni passaggio, proviamo input più piccoli per ridurre il problema.
- La condizione di base è necessaria per interrompere la ricorsione, altrimenti si verificherà un ciclo infinito.
Algoritmo: passaggi
The algorithmic steps for implementing recursion in a function are as follows: Step1 - Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself. Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.>
Un'interpretazione matematica
Consideriamo il problema che un programmatore deve affrontare per determinare la somma dei primi n numeri naturali, ci sono diversi modi per farlo, ma l'approccio più semplice è semplicemente quello di sommare i numeri che iniziano da 1 a n. Quindi la funzione assomiglia semplicemente a questa,
approccio(1) – Semplicemente aggiungendo uno per uno
f(n) = 1 + 2 + 3 +……..+ n
ma esiste un altro approccio matematico per rappresentarlo,
approccio(2) – Aggiunta ricorsiva
f(n) = 1n=1
f(n) = n + f(n-1) n>1
C'è una semplice differenza tra l'approccio (1) e l'approccio (2) e questo è corretto approccio(2) la funzione F( ) stesso viene chiamato all'interno della funzione, quindi questo fenomeno è chiamato ricorsione, e la funzione che contiene la ricorsione è chiamata funzione ricorsiva, alla fine, questo è un ottimo strumento nelle mani dei programmatori per codificare alcuni problemi in modo molto più semplice ed efficiente modo.
Come vengono archiviate le funzioni ricorsive in memoria?
La ricorsione utilizza più memoria, perché la funzione ricorsiva aggiunge allo stack con ogni chiamata ricorsiva e mantiene i valori lì fino al termine della chiamata. La funzione ricorsiva utilizza la struttura LIFO (LAST IN FIRST OUT) proprio come la struttura dei dati dello stack. struttura-dati-stack/
Qual è la condizione di base nella ricorsione?
Nel programma ricorsivo viene fornita la soluzione del caso base e la soluzione del problema più grande viene espressa in termini di problemi più piccoli.
int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }> Nell'esempio sopra, è definito il caso base per n <= 1 e il valore più grande di un numero può essere risolto convertendolo in uno più piccolo fino a raggiungere il caso base.
Come viene risolto un particolare problema utilizzando la ricorsione?
L'idea è di rappresentare un problema in termini di uno o più problemi più piccoli e aggiungere una o più condizioni di base che interrompono la ricorsione. Ad esempio, calcoliamo il fattoriale n se conosciamo il fattoriale di (n-1). Il caso base del fattoriale sarebbe n = 0. Restituiamo 1 quando n = 0.
Perché l'errore Stack Overflow si verifica nella ricorsione?
Se il caso base non viene raggiunto o non è definito, potrebbe verificarsi il problema di overflow dello stack. Facciamo un esempio per capirlo.
int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); }> Se viene chiamato fact(10), chiamerà fact(9), fact(8), fact(7) e così via, ma il numero non raggiungerà mai 100. Pertanto, il caso base non viene raggiunto. Se la memoria viene esaurita da queste funzioni nello stack, si verificherà un errore di overflow dello stack.
Qual è la differenza tra ricorsione diretta e indiretta?
Una funzione fun è detta ricorsiva diretta se chiama la stessa funzione fun. Una funzione fun è chiamata ricorsiva indiretta se chiama un'altra funzione, ad esempio fun_new, e fun_new chiama fun direttamente o indirettamente. La differenza tra ricorsione diretta e indiretta è stata illustrata nella Tabella 1.
// An example of direct recursion void directRecFun() { // Some code.... directRecFun(); // Some code... } // An example of indirect recursion void indirectRecFun1() { // Some code... indirectRecFun2(); // Some code... } void indirectRecFun2() { // Some code... indirectRecFun1(); // Some code... }> Qual è la differenza tra ricorsione a coda e senza coda?
Una funzione ricorsiva è ricorsiva in coda quando una chiamata ricorsiva è l'ultima cosa eseguita dalla funzione. Per favore, riferisci articolo di ricorsione della coda per dettagli.
Come viene allocata la memoria alle diverse chiamate di funzione in ricorsione?
Quando una funzione viene chiamata da main(), la memoria le viene allocata nello stack. Una funzione ricorsiva chiama se stessa, la memoria per una funzione chiamata viene allocata sopra la memoria allocata alla funzione chiamante e viene creata una copia diversa delle variabili locali per ogni chiamata di funzione. Quando viene raggiunto il caso base, la funzione restituisce il suo valore alla funzione da cui è stata chiamata, la memoria viene deallocata e il processo continua.
Prendiamo l'esempio di come funziona la ricorsione prendendo una semplice funzione.
CPP
// A C++ program to demonstrate working of> // recursion> #include> using> namespace> std;> > void> printFun(>int> test)> {> >if> (test <1)> >return>;> >else> {> >cout << test <<>' '>;> >printFun(test - 1);>// statement 2> >cout << test <<>' '>;> >return>;> >}> }> > // Driver Code> int> main()> {> >int> test = 3;> >printFun(test);> }> |
>
>
Giava
shweta tiwari
// A Java program to demonstrate working of> // recursion> class> GFG {> >static> void> printFun(>int> test)> >{> >if> (test <>1>)> >return>;> >else> {> >System.out.printf(>'%d '>, test);> >printFun(test ->1>);>// statement 2> >System.out.printf(>'%d '>, test);> >return>;> >}> >}> > >// Driver Code> >public> static> void> main(String[] args)> >{> >int> test =>3>;> >printFun(test);> >}> }> > // This code is contributed by> // Smitha Dinesh Semwal> |
>
>
Python3
# A Python 3 program to> # demonstrate working of> # recursion> > > def> printFun(test):> > >if> (test <>1>):> >return> >else>:> > >print>(test, end>=>' '>)> >printFun(test>->1>)># statement 2> >print>(test, end>=>' '>)> >return> > # Driver Code> test>=> 3> printFun(test)> > # This code is contributed by> # Smitha Dinesh Semwal> |
>
>
C#
// A C# program to demonstrate> // working of recursion> using> System;> > class> GFG {> > >// function to demonstrate> >// working of recursion> >static> void> printFun(>int> test)> >{> >if> (test <1)> >return>;> >else> {> >Console.Write(test +>' '>);> > >// statement 2> >printFun(test - 1);> > >Console.Write(test +>' '>);> >return>;> >}> >}> > >// Driver Code> >public> static> void> Main(String[] args)> >{> >int> test = 3;> >printFun(test);> >}> }> > // This code is contributed by Anshul Aggarwal.> |
>
>
PHP
// PHP program to demonstrate // working of recursion // function to demonstrate // working of recursion function printFun($test) { if ($test <1) return; else { echo('$test '); // statement 2 printFun($test-1); echo('$test '); return; } } // Driver Code $test = 3; printFun($test); // This code is contributed by // Smitha Dinesh Semwal. ?>> |
>
>
Javascript
> > // JavaScript program to demonstrate working of> // recursion> > function> printFun(test)> >{> >if> (test <1)> >return>;> >else> {> >document.write(test +>' '>);> >printFun(test - 1);>// statement 2> >document.write(test +>' '>);> >return>;> >}> >}> > // Driver code> >let test = 3;> >printFun(test);> > > |
>
>Produzione
3 2 1 1 2 3>
Complessità temporale: O(1)
Spazio ausiliario: O(1)
Quando stampaDivertimento(3) viene chiamato da main(), a cui viene allocata la memoria stampaDivertimento(3) e un test della variabile locale viene inizializzato su 3 e le istruzioni da 1 a 4 vengono inserite nello stack come mostrato nel diagramma seguente. Per prima cosa stampa '3'. Nella dichiarazione 2, stampaDivertimento(2) viene chiamato e viene allocata la memoria stampaDivertimento(2) e una variabile locale test viene inizializzata su 2 e le istruzioni da 1 a 4 vengono inserite nello stack. Allo stesso modo, stampaDivertimento(2) chiamate stampaDivertimento(1) E stampaDivertimento(1) chiamate stampaDivertimento(0) . stampaDivertimento(0) va all'istruzione if e ritorna a stampaDivertimento(1) . Le restanti dichiarazioni di stampaDivertimento(1) vengono eseguiti e ritorna a stampaDivertimento(2) e così via. Nell'output vengono stampati i valori da 3 a 1 e poi da 1 a 3. Lo stack di memoria è stato mostrato nel diagramma seguente.
Ricorsione VS Iterazione
| RS n. | Ricorsione | Iterazione |
| 1) | Termina quando il caso base diventa vero. | Termina quando la condizione diventa falsa. |
| 2) | Utilizzato con le funzioni. | Utilizzato con i loop. |
| 3) | Ogni chiamata ricorsiva necessita di spazio aggiuntivo nella memoria dello stack. | Ogni iterazione non richiede spazio aggiuntivo. |
| 4) | Dimensione del codice più piccola. | Dimensione del codice maggiore. |
Ora discutiamo alcuni problemi pratici che possono essere risolti utilizzando la ricorsione e comprendiamone il funzionamento di base. Per una comprensione di base, leggere i seguenti articoli.
Conoscenza di base della ricorsione.
Problema 1: Scrivi un programma e una relazione di ricorrenza per trovare la serie di Fibonacci di n dove n>2 .
Equazione matematica:
n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>
Relazione di ricorrenza:
T(n) = T(n-1) + T(n-2) + O(1)>
Programma ricorsivo:
Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>
Implementazione:
C++
// C++ code to implement Fibonacci series> #include> using> namespace> std;> > // Function for fibonacci> > int> fib(>int> n)> > > // Driver Code> int> main()> {> >// Initialize variable n.> >int> n = 5;> >cout<<>'Fibonacci series of 5 numbers is: '>;> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i { cout<' '; } return 0; }> |
>
>
C
// C code to implement Fibonacci series> #include> > // Function for fibonacci> int> fib(>int> n)> > >// Stop condition> >if> (n == 0)> >return> 0;> > >// Stop condition> >if> (n == 1> > // Driver Code> int> main()> {> >// Initialize variable n.> >int> n = 5;> >printf>(>'Fibonacci series '> >'of %d numbers is: '>,> >n);> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i printf('%d ', fib(i)); } return 0; }> |
>
>
Giava
// Java code to implement Fibonacci series> import> java.util.*;> > class> GFG> {> > // Function for fibonacci> static> int> fib(>int> n)> > > // Driver Code> public> static> void> main(String []args)> {> > >// Initialize variable n.> >int> n =>5>;> >System.out.print(>'Fibonacci series of 5 numbers is: '>);> > >// for loop to print the fibonacci series.> >for> (>int> i =>0>; i { System.out.print(fib(i)+' '); } } } // This code is contributed by rutvik_56.> |
>
età rekha
>
Python3
# Python code to implement Fibonacci series> > # Function for fibonacci> def> fib(n):> > ># Stop condition> >if> (n>=>=> 0>):> >return> 0> > ># Stop condition> >if> (n>=>=> 1> or> n>=>=> 2>):> >return> 1> > ># Recursion function> >else>:> >return> (fib(n>-> 1>)>+> fib(n>-> 2>))> > > # Driver Code> > # Initialize variable n.> n>=> 5>;> print>(>'Fibonacci series of 5 numbers is :'>,end>=>' '>)> > # for loop to print the fibonacci series.> for> i>in> range>(>0>,n):> >print>(fib(i),end>=>' '>)> |
>
>
C#
using> System;> > public> class> GFG> {> > >// Function for fibonacci> >static> int> fib(>int> n)> > n == 2)> >return> 1;> > >// Recursion function> >else> >return> (fib(n - 1) + fib(n - 2));> >> > >// Driver Code> >static> public> void> Main ()> >{> > >// Initialize variable n.> >int> n = 5;> >Console.Write(>'Fibonacci series of 5 numbers is: '>);> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i { Console.Write(fib(i) + ' '); } } } // This code is contributed by avanitrachhadiya2155> |
>
>
Javascript
> // JavaScript code to implement Fibonacci series> > // Function for fibonacci> function> fib(n)> n == 2)> >return> 1;> >// Recursion function> >else> >return> fib(n-1) + fib(n-2);> > > // Initialize variable n.> let n = 5;> > document.write(>'Fibonacci series of 5 numbers is: '>);> > // for loop to print the fibonacci series.> for>(let i = 0; i { document.write(fib(i) + ' '); }> |
>
>Produzione
Fibonacci series of 5 numbers is: 0 1 1 2 3>
Complessità temporale: O(2N)
Spazio ausiliario: SU)
Ecco l'albero ricorsivo per l'input 5 che mostra un quadro chiaro di come un grosso problema possa essere risolto in problemi più piccoli.
fib(n) è una funzione di Fibonacci. La complessità temporale del programma può dipendere dalla chiamata della funzione.
fib(n) -> livello CBT (UB) -> 2^n-1 nodi -> 2^n chiamata di funzione -> 2^n*O(1) -> T(n) = O(2^n)
rispetto a Java
Per il caso migliore.
T(n) = ?(2^n2)>
Lavorando:
Problema 2: Scrivi un programma e una relazione di ricorrenza per trovare il Fattoriale di n dove n>2 .
Equazione matematica:
1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>
Relazione di ricorrenza:
T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>
Programma ricorsivo:
Ingresso: n = 5
Produzione:
fattoriale di 5 è: 120
Implementazione:
C++
// C++ code to implement factorial> #include> using> namespace> std;> > // Factorial function> int> f(>int> n)> n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n * f(n - 1);> > > // Driver code> int> main()> {> >int> n = 5;> >cout<<>'factorial of '><' is: '< return 0; }> |
>
>
C
// C code to implement factorial> #include> > // Factorial function> int> f(>int> n)> > >// Stop condition> >if> (n == 0> > // Driver code> int> main()> {> >int> n = 5;> >printf>(>'factorial of %d is: %d'>, n, f(n));> >return> 0;> }> |
>
>
Giava
// Java code to implement factorial> public> class> GFG> {> > >// Factorial function> >static> int> f(>int> n)> >> > >// Driver code> >public> static> void> main(String[] args)> >{> >int> n =>5>;> >System.out.println(>'factorial of '> + n +>' is: '> + f(n));> >}> }> > // This code is contributed by divyesh072019.> |
>
>
Python3
# Python3 code to implement factorial> > # Factorial function> def> f(n):> > ># Stop condition> >if> (n>=>=> 0> or> n>=>=> 1>):> >return> 1>;> > ># Recursive condition> >else>:> >return> n>*> f(n>-> 1>);> > > # Driver code> if> __name__>=>=>'__main__'>:> > >n>=> 5>;> >print>(>'factorial of'>,n,>'is:'>,f(n))> > ># This code is contributed by pratham76.> |
>
>
C#
// C# code to implement factorial> using> System;> class> GFG {> > >// Factorial function> >static> int> f(>int> n)> > n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n * f(n - 1);> >> > >// Driver code> >static> void> Main()> >{> >int> n = 5;> >Console.WriteLine(>'factorial of '> + n +>' is: '> + f(n));> >}> }> > // This code is contributed by divyeshrabadiya07.> |
>
>
Javascript
> // JavaScript code to implement factorial> > // Factorial function> function> f(n)> n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n*f(n-1);> > > // Initialize variable n.> let n = 5;> document.write(>'factorial of '>+ n +>' is: '> + f(n));> > // This code is contributed by probinsah.> > |
>
>Produzione
factorial of 5 is: 120>
Complessità temporale: SU)
Spazio ausiliario: SU)
Lavorando:
Diagramma della funzione di ricorsione fattoriale per l'input dell'utente 5.
Esempio: applicazioni reali della ricorsione in problemi reali
La ricorsione è una tecnica potente che ha molte applicazioni nell'informatica e nella programmazione. Ecco alcune delle applicazioni più comuni della ricorsione:
- Attraversamento di alberi e grafici: la ricorsione viene spesso utilizzata per attraversare e cercare strutture di dati come alberi e grafici. Gli algoritmi ricorsivi possono essere utilizzati per esplorare in modo sistematico tutti i nodi o vertici di un albero o di un grafico. Algoritmi di ordinamento: gli algoritmi ricorsivi vengono utilizzati anche negli algoritmi di ordinamento come Quicksort e Merge sort. Questi algoritmi utilizzano la ricorsione per dividere i dati in sottoarray o sottoelenchi più piccoli, ordinarli e quindi unirli nuovamente insieme. Algoritmi divide et impera: molti algoritmi che utilizzano un approccio divide et impera, come l'algoritmo di ricerca binaria, utilizzano la ricorsione per suddividere il problema in sottoproblemi più piccoli. Generazione frattale: forme e modelli frattali possono essere generati utilizzando algoritmi ricorsivi. Ad esempio, l'insieme di Mandelbrot viene generato applicando ripetutamente una formula ricorsiva a numeri complessi. Algoritmi di backtracking: gli algoritmi di backtracking vengono utilizzati per risolvere problemi che implicano l'assunzione di una sequenza di decisioni, in cui ciascuna decisione dipende da quelle precedenti. Questi algoritmi possono essere implementati utilizzando la ricorsione per esplorare tutti i possibili percorsi e tornare indietro quando non viene trovata una soluzione. Memoizzazione: la memoizzazione è una tecnica che prevede la memorizzazione dei risultati di chiamate di funzioni costose e la restituzione del risultato memorizzato nella cache quando si verificano nuovamente gli stessi input. La memorizzazione può essere implementata utilizzando funzioni ricorsive per calcolare e memorizzare nella cache i risultati dei sottoproblemi.
Questi sono solo alcuni esempi delle numerose applicazioni della ricorsione nell'informatica e nella programmazione. La ricorsione è uno strumento versatile e potente che può essere utilizzato per risolvere molti tipi diversi di problemi.
Spiegazione: un vero esempio di ricorsione:
La ricorsione è una tecnica di programmazione che coinvolge una funzione che chiama se stessa. Può essere uno strumento potente per risolvere problemi complessi, ma richiede anche un'attenta implementazione per evitare cicli infiniti e stack overflow.
Ecco un esempio di implementazione della ricorsione in Python:
C++
#include> using> namespace> std;> int> factorial(>int> n)> {> > >// Base case: if n is 0 or 1, return 1> >if> (n == 0 || n == 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> }> > int> main()> {> > >// Call the factorial function and print the result> >int> result = factorial(5);> >cout << result |
>
>
Giava
import> java.util.*;> > class> Main {> >public> static> int> factorial(>int> n)> >{> >// Base case: if n is 0 or 1, return 1> >if> (n ==>0> || n ==>1>) {> >return> 1>;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n ->1>);> >}> >}> > >public> static> void> main(String[] args)> >{> >// Call the factorial function and print the result> >int> result = factorial(>5>);> >System.out.println(result);>// Output: 120> >}> }> |
>
>
Python3
def> factorial(n):> ># Base case: if n is 0 or 1, return 1> >if> n>=>=> 0> or> n>=>=> 1>:> >return> 1> > ># Recursive case: if n is greater than 1, call the function with n-1 and multiply by n> >else>:> >return> n>*> factorial(n>->1>)> > # Call the factorial function and print the result> result>=> factorial(>5>)> print>(result)># Output: 120> |
>
>
C#
using> System;> > class> MainClass {> >public> static> int> factorial(>int> n)> >{> >// Base case: if n is 0 or 1, return 1> >if> (n == 0 || n == 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> >}> > >public> static> void> Main (>string>[] args) {> >// Call the factorial function and print the result> >int> result = factorial(5);> >Console.WriteLine(result);>// Output: 120> >}> }> |
>
>
Javascript
interfaccia vs classe astratta
function> factorial(n) {> >// Base case: if n is 0 or 1, return 1> >if> (n === 0 || n === 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1, call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> }> > // Call the factorial function and print the result> const result = factorial(5);> console.log(result);>// Output: 120> |
>
>Produzione
120>
In questo esempio definiamo una funzione chiamata fattoriale che accetta un intero n come input. La funzione utilizza la ricorsione per calcolare il fattoriale di n (ovvero il prodotto di tutti gli interi positivi fino a n).
La funzione fattoriale controlla innanzitutto se n è 0 o 1, che sono i casi base. Se n è 0 o 1, la funzione restituisce 1, poiché 0! e 1! sono entrambi 1.
Se n è maggiore di 1, la funzione entra nel caso ricorsivo. Si richiama con n-1 come argomento e moltiplica il risultato per n. Questo calcola n! calcolando ricorsivamente (n-1)!.
È importante notare che la ricorsione può essere inefficiente e portare a stack overflow se non utilizzata con attenzione. Ogni chiamata di funzione aggiunge un nuovo frame allo stack di chiamate, il che può far sì che lo stack diventi troppo grande se la ricorsione è troppo profonda. Inoltre, la ricorsione può rendere il codice più difficile da comprendere ed eseguire il debug, poiché richiede di pensare a più livelli di chiamate di funzione.
Tuttavia, la ricorsione può anche essere un potente strumento per risolvere problemi complessi, in particolare quelli che implicano la suddivisione di un problema in sottoproblemi più piccoli. Se utilizzata correttamente, la ricorsione può rendere il codice più elegante e più facile da leggere.
Quali sono gli svantaggi della programmazione ricorsiva rispetto alla programmazione iterativa?
Si noti che sia i programmi ricorsivi che quelli iterativi hanno gli stessi poteri di risoluzione dei problemi, ovvero ogni programma ricorsivo può essere scritto in modo iterativo ed è vero anche il viceversa. Il programma ricorsivo ha requisiti di spazio maggiori rispetto al programma iterativo poiché tutte le funzioni rimarranno nello stack fino al raggiungimento del caso base. Ha anche maggiori requisiti di tempo a causa delle chiamate di funzione e del sovraccarico dei resi.
Inoltre, a causa della minore lunghezza del codice, i codici sono difficili da comprendere e quindi è necessario prestare particolare attenzione durante la scrittura del codice. Il computer potrebbe esaurire la memoria se le chiamate ricorsive non vengono controllate correttamente.
Quali sono i vantaggi della programmazione ricorsiva rispetto alla programmazione iterativa?
La ricorsione fornisce un modo pulito e semplice per scrivere codice. Alcuni problemi sono intrinsecamente ricorsivi come gli attraversamenti degli alberi, Torre di Hanoi , ecc. Per tali problemi, si preferisce scrivere codice ricorsivo. Possiamo scrivere tali codici anche in modo iterativo con l'aiuto di una struttura dati stack. Ad esempio, fare riferimento a Inorder Tree Traversal without Recursion, Iterative Tower of Hanoi.
Riepilogo della ricorsione:
- Esistono due tipi di casi in ricorsione, ovvero caso ricorsivo e caso base.
- Il caso base viene utilizzato per terminare la funzione ricorsiva quando il caso risulta essere vero.
- Ogni chiamata ricorsiva crea una nuova copia di quel metodo nella memoria dello stack.
- La ricorsione infinita può portare all'esaurimento della memoria dello stack.
- Esempi di algoritmi ricorsivi: Merge Sort, Quick Sort, Torre di Hanoi, Serie di Fibonacci, Problema fattoriale, ecc.
Problemi pratici basati sull'output per principianti:
Domande pratiche per la ricorsione | Insieme 1
Domande pratiche per la ricorsione | Insieme 2
Domande pratiche per la ricorsione | Insieme 3
Domande pratiche per la ricorsione | Insieme 4
Domande pratiche per la ricorsione | Insieme 5
Domande pratiche per la ricorsione | Insieme 6
Domande pratiche per la ricorsione | Insieme 7
Quiz sulla ricorsione
Pratica di codifica sulla ricorsione:
Tutti gli articoli sulla ricorsione
Problemi pratici ricorsivi con soluzioni