Tutto quello che devi sapere sulla ricorsione in Python



Questo articolo ti aiuterà a ottenere una conoscenza dettagliata e completa della ricorsione in Python. Come funziona? e qual è il suo scopo?

In parole semplici, la ricorsione è un modo per risolvere il problema facendo chiamare a se stessa una funzione, la parola ' ricorsivo 'Ha origine dal verbo latino' ricorrere ', Che significa rifare qualcosa. Questo è ciò che fa la funzione ricorsiva, ripete la stessa cosa ancora e ancora, cioè richiama se stessa. In questo articolo impareremo la ricorsione in python. Di seguito sono riportati gli argomenti trattati in questo blog:

Cos'è la ricorsione in Python?

La ricorsione è il processo di determinazione di qualcosa in termini di se stessa. Sappiamo che in Python, qualsiasi funzione può chiamare qualsiasi altra funzione, una funzione può anche chiamare se stessa. Questi tipi di funzioni che chiamano se stessa fino a quando la condizione certa non è soddisfatta sono definiti funzioni ricorsive.





Recursion-in-Python

diamo alcuni esempi per vedere come funziona, se ti viene fornito un numero intero positivo n il fattoriale sarebbe.



  • n! = n * (n-1) * (n-2) e così via.
  • 2! = 2 * (2-1)
  • uno! = 1
  • 0! = 0
  • 4! = 4 * 3!
  • 3! = 3 * 2!
  • 2! = 2 * 1!

La sostituzione dei valori precedenti produrrà la seguente espressione

  • 4! = 4 * 3 * 2 * 1

Dobbiamo definire una funzione diciamo fact (n) che prende un intero positivo o 0 come parametro e restituisce l'ennesimo fattoriale, come possiamo farlo usando la ricorsione?

java trova il valore più alto nell'array

Vediamo, per farlo usando la ricorsione dobbiamo esaminare la seguente equazione



  • n! = n. (n-1). (n-2) & hellip3.2.1

  • n! = n. (n-1)! #possiamo riscrivere la dichiarazione precedente come su questa riga

  • Ora qui se passiamo 2 come parametro otterremo:

    • 2! = 2,1! = 2

  • Allo stesso modo, se passiamo 1 otterremo:

    • uno! = 1.0! = 1

  • Ma se passiamo 0, si rompe

    • 0! = 0. (- 1)! e qui il fattoriale per -1 non è definito, quindi funziona solo per valori> 0

  • Quindi dobbiamo scrivere due casi

    • 1. n! = n. (n-1)! se n> = 1

    • 2. 1 se n = 0

Questa è una soluzione completa per tutti i numeri interi positivi e 0.

cosa è awt in java

Condizione di risoluzione

Una funzione ricorsiva deve soddisfare una condizione importante per essere terminata. Spostandosi verso una condizione in cui il problema può essere risolto senza ulteriore ricorsione, una funzione ricorsiva terminerà, riducendo al minimo il problema nei passaggi secondari più piccoli. Una ricorsione può finire in un ciclo infinito se la condizione di terminazione non è soddisfatta nelle chiamate.

Condizioni fattoriali:

  • fattoriale di n = n * (n-1) fintanto che n è maggiore di 1.
  • 1 se n = 0

Convertiremo le condizioni fattoriali sopra in codice Python:

def fact (n): if n == 1: return n else: return n * fact (n-1)

Facciamo un esempio, supponiamo di voler trovare un fattoriale di 4:

fact (4) #questo restituirà 4 * fact (3) e così via fino a n == 1.
 Produzione: 24

È usato così spesso come esempio per la ricorsione a causa della sua semplicità e chiarezza. Risolvendo istanze più piccole di un problema in ogni fase è definita come ricorsione in informatica.

Limite di ricorsione di Python

In alcuni linguaggi è possibile creare un ciclo ricorsivo infinito ma, in Python, esiste un limite di ricorsione. Per controllare il limite eseguire la seguente funzione dal modulo sys. che darà il limite del set di ricorsione per python.

import sys sys.getrecursionlimit ()
 Produzione: 1000

Puoi anche modificare il limite utilizzando functionsetrecursionlimit () del modulo sys in base alle tue esigenze, ora creiamo una funzione che si chiama in modo ricorsivo finché non supera il limite e controlla cosa succede:

convertire double in int java
def recursive (): recursive () if __name__ == '__main__': recursive ()

Se esegui il codice precedente, otterrai un'eccezione di runtime: RuntimeError: profondità massima di ricorsione superata. Python ti impedisce di creare una funzione che finisce in un ciclo ricorsivo senza fine.

Appiattimento degli elenchi con la ricorsione

Altre cose che puoi fare usando la ricorsione eccetto i fattoriali, diciamo che vuoi creare un singolo da un elenco annidato, puoi farlo usando il codice seguente:

def flatten (a_list, flat_list = none): se flat_list è none: flat_list = [] for item in a_list: if isinstance (item, list): flatten (item, flat_list) else: flat_list.append (item) return flat_list if __name__ == '__main__': annidato = [1,2,3, [4,5], 6] x = appiattisci (annidato) print (x)
 Produzione: [1,2,3,4,5,6]

L'esecuzione del codice sopra risulterà in un singolo elenco invece di un elenco di interi contenente l'elenco di interi che abbiamo usato come input. Puoi anche fare la stessa cosa usando anche altri modi, Python ha qualcosa chiamato itertools.chain () puoi controllare il codice usato per creare una catena di funzioni () è un approccio diverso per fare la stessa cosa che abbiamo fatto noi.

Vantaggi della ricorsione

  • Il codice è pulito ed elegante in una funzione ricorsiva.

  • Un'attività composita può essere suddivisa in sottoproblemi più semplici usando la ricorsione.

  • La generazione di sequenze è più facile con la ricorsione rispetto all'utilizzo di un'iterazione annidata.

Svantaggi della ricorsione

  • A volte può essere difficile seguire la logica alla base della funzione ricorsiva.

  • Le chiamate ricorsive sono costose (inefficienti) poiché occupano molta memoria e tempo.

  • Le funzioni ricorsive sono difficili da eseguire il debug.

In questo articolo abbiamo visto cos'è la ricorsione e come possiamo sviluppare funzioni ricorsive dall'istruzione del problema, come può essere definita matematicamente un'istruzione del problema. Abbiamo risolto un problema del fattoriale e scoperto le condizioni richieste per trovare fattoriali da cui siamo stati in grado di convertire quelle condizioni in codice Python dandoti la comprensione di come funziona la ricorsione. Penso che sia chiaro che Python abbia un limite incorporato per la ricorsione per impedire agli sviluppatori di creare funzioni ricorsive mal costruite. Una cosa importante da notare è che la ricorsione è difficile da eseguire il debug poiché la funzione continua a chiamare se stessa.