Il termine Ricorsione può essere definito come il processo di definizione di qualcosa in termini di se stesso. In parole semplici, è un processo in cui una funzione richiama se stessa direttamente o indirettamente.
Vantaggi dell'utilizzo della ricorsione
- Una funzione complicata può essere suddivisa in sottoproblemi più piccoli utilizzando la ricorsione.
- La creazione di sequenze è più semplice tramite la ricorsione rispetto all'utilizzo di qualsiasi iterazione annidata.
- Le funzioni ricorsive rendono il codice semplice ed efficace.
Svantaggi dell'utilizzo della ricorsione
- Molta memoria e tempo vengono utilizzati tramite chiamate ricorsive, il che ne rende costoso l'utilizzo.
- Le funzioni ricorsive sono difficili da eseguire il debug.
- Il ragionamento alla base della ricorsione a volte può essere difficile da comprendere.
Sintassi:
def func(): <-- | | (recursive call) | func() ---->
Esempio 1: Una sequenza di Fibonacci è la sequenza intera di 0, 1, 1, 2, 3, 5, 8….
Python3
# Program to print the fibonacci series upto n_terms> # Recursive function> def> recursive_fibonacci(n):> >if> n <>=> 1>:> >return> n> >else>:> >return>(recursive_fibonacci(n>->1>)>+> recursive_fibonacci(n>->2>))> n_terms>=> 10> # check if the number of terms is valid> if> n_terms <>=> 0>:> >print>(>'Invalid input ! Please input a positive value'>)> else>:> >print>(>'Fibonacci series:'>)> for> i>in> range>(n_terms):> >print>(recursive_fibonacci(i))> |
>
eseguire lo script shell
>Produzione
Fibonacci series: 0 1 1 2 3 5 8 13 21 34>
Esempio 2: Il fattoriale di 6 è indicato come 6! = 1*2*3*4*5*6 = 720.
Python3
# Program to print factorial of a number> # recursively.> # Recursive function> def> recursive_factorial(n):> >if> n>=>=> 1>:> >return> n> >else>:> >return> n>*> recursive_factorial(n>->1>)> # user input> num>=> 6> # check if the input is valid or not> if> num <>0>:> >print>(>'Invalid input ! Please enter a positive number.'>)> elif> num>=>=> 0>:> >print>(>'Factorial of number 0 is 1'>)> else>:> >print>(>'Factorial of number'>, num,>'='>, recursive_factorial(num))> |
>
>Produzione
Factorial of number 6 = 720>
Cos'è la ricorsione in coda?
Un tipo unico di ricorsione in cui l'ultima procedura di una funzione è una chiamata ricorsiva. La ricorsione può essere automatizzata eseguendo la richiesta nello stack frame corrente e restituendo l'output invece di generare un nuovo stack frame. La ricorsione in coda può essere ottimizzata dal compilatore, rendendola migliore rispetto alle funzioni ricorsive non in coda.
È possibile ottimizzare un programma utilizzando una funzione ricorsiva in coda anziché una funzione ricorsiva non in coda?
Considerando la funzione indicata di seguito per calcolare il fattoriale di n, possiamo osservare che la funzione inizialmente sembra una ricorsiva in coda ma è una funzione non ricorsiva in coda. Se osserviamo da vicino, possiamo vedere che il valore restituito da Recur_facto(n-1) viene utilizzato in Recur_facto(n), quindi la chiamata a Recur_facto(n-1) non è l'ultima cosa fatta da Recur_facto(n).
Python3
quanto è grande lo schermo del mio computer
# Program to calculate factorial of a number> # using a Non-Tail-Recursive function.> # non-tail recursive function> def> Recur_facto(n):> > >if> (n>=>=> 0>):> >return> 1> > >return> n>*> Recur_facto(n>->1>)> > # print the result> print>(Recur_facto(>6>))> |
>
>Produzione
720>
Possiamo scrivere la funzione data Recur_facto come funzione ricorsiva in coda. L'idea è di utilizzare un ulteriore argomento e nel secondo argomento inserire il valore del fattoriale. Quando n raggiunge 0, restituisce il valore finale del fattoriale del numero desiderato.
Python3
# Program to calculate factorial of a number> # using a Tail-Recursive function.> # A tail recursive function> def> Recur_facto(n, a>=> 1>):> > >if> (n>=>=> 0>):> >return> a> > >return> Recur_facto(n>-> 1>, n>*> a)> > # print the result> print>(Recur_facto(>6>))> |
>
>Produzione
kajal aggarwal
720>