Concetto di funzione ricorsiva Python: tutorial Python per principianti

Nel mondo dell'informatica, la ricorsione si riferisce alla tecnica di definire una cosa nei propri termini. In altre parole, una funzione ricorsiva chiama se stessa per l'elaborazione. In questo articolo comprenderemo il concetto di funzione ricorsiva in Python , un linguaggio di programmazione ampiamente utilizzato del 21° secolo.

Cos'è la ricorsione Python ?

In Python, un gruppo di istruzioni correlate che eseguono un'attività specifica è definito "funzione". Quindi, le funzioni suddividono il tuo programma in blocchi più piccoli. Ed è risaputo che una funzione può chiamare altre funzioni in Python.

Ma alcune altre funzioni possono chiamarsi. Queste sono note come funzioni ricorsive. Considera due specchi paralleli posti uno di fronte all'altro. Ora, qualsiasi oggetto tenuto tra gli specchi verrebbe riflesso in modo ricorsivo.

Entriamo nel dettaglio della funzione ricorsiva per comprenderne chiaramente il funzionamento.

La funzione ricorsiva

Sappiamo che una funzione ricorsiva in Python chiama se stessa come è definita tramite espressioni autoreferenziali, cioè in termini di se stessa. Continua a ripetere il suo comportamento finché non viene soddisfatta una condizione particolare per restituire un valore o un risultato. Vediamo ora un esempio per sapere come funziona.

Leggi anche: Domande e risposte sull'intervista Python

Supponiamo di voler scoprire il fattoriale di un intero. Il fattoriale non è altro che il prodotto di tutti i numeri, a partire da 1 fino a quel numero intero. Ad esempio, il fattoriale di 5 (scritto come 5!) sarebbe 1*2*3*4*5*6, cioè 720. Abbiamo una funzione ricorsiva calc_factorial(x), che è definita come segue:

def calc_factorial(x):

#Funzione ricorsiva per trovare il fattoriale di un intero

se x == 1:

ritorno 1

altro

ritorno (x * calc_factorial(x-1))

Cosa accadrebbe se chiami questa funzione con un numero intero positivo come 4? Bene, ogni chiamata di funzione aggiungerà uno stack frame fino a raggiungere il caso base (quando il numero si riduce a 1). La condizione di base è necessaria affinché la ricorsione termini e non continui all'infinito. Quindi, nel caso indicato, il valore 24 verrà restituito dopo la quarta chiamata.

Implementazione della funzione ricorsiva in Python

Ci possono essere varie applicazioni di funzioni ricorsive in Python. Ad esempio, vuoi creare una grafica con un motivo ripetuto, ad esempio un fiocco di neve di Koch. La ricorsione può essere utilizzata per generare modelli frattali, che sono costituiti da versioni più piccole dello stesso disegno.

Un altro esempio è quello del game solving. Puoi scrivere algoritmi ricorsivi per risolvere Sudoku e numerosi giochi complessi. La ricorsione è più comunemente usata nei problemi di ricerca, ordinamento e attraversamento.

Una caratteristica sorprendente della funzione è che l'implementazione ricorsiva consente il backtracking. Quindi, la ricorsione consiste nel costruire una soluzione in modo incrementale e rimuovere quelle soluzioni che non soddisfano i vincoli del problema in nessuna fase. Per raggiungere questo obiettivo sono necessarie due cose: il mantenimento dello stato e una struttura dei dati adeguata. Continua a leggere per familiarizzare con questi termini.

Leggi: Stipendio per sviluppatori Python in India

Mantenimento dello stato

Ogni chiamata ricorsiva in Python ha il proprio contesto di esecuzione. Mentre gestisci le funzioni ricorsive in Python, devi eseguire il thread dello stato attraverso ogni chiamata ricorsiva. In questo modo, lo stato corrente diventa parte del contesto di esecuzione della chiamata corrente. Puoi anche mantenere lo stato in ambito globale.

Ad esempio, se stai usando la ricorsione per calcolare 1+2+3+4+…….+10. Qui, il numero corrente che stai aggiungendo e la somma accumulata fino a quel punto formano lo stato che devi mantenere. Il mantenimento dello stato implica il passaggio dello stato corrente aggiornato come argomenti attraverso ogni chiamata. Ecco come puoi farlo.

def sum_numbers(current_number, accumulated_sum)

#Caso base

#Ritorna allo stato finale

se numero attuale==11:

restituire somma_accumulata

#Caso Ricorsivo

#Thread lo stato attraverso una chiamata ricorsiva

Altro:

return sum_numbers(current_number + 1, cumulated_sum + current_number)

In alternativa, puoi usare lo stato mutevole globale. Per mantenere lo stato utilizzando questo metodo, mantieni lo stato nell'ambito globale.

numero_corrente = 1

somma_accumulata = 0

def somma_numeri():

numero_corrente globale

somma_accumulata globale

#Caso base

se numero_corrente==11

restituire somma_accumulata

#Caso Ricorsivo

altro:

somma_accumulata = somma_accumulata + numero_corrente

numero_corrente = numero_corrente + 1

restituisce somma_numeri()

Strutture dati ricorsive

Una struttura dati è considerata ricorsiva se può essere definita in termini di versioni più piccole e più semplici di se stessa. Esempi di strutture dati ricorsive includono elenchi, alberi, strutture gerarchiche, dizionari, ecc. Un elenco può avere altri elenchi come elementi. Un albero ha sottoalberi, nodi foglia e così via.

È importante notare qui che la struttura delle funzioni ricorsive è spesso modellata sulle strutture di dati che prende come input. Quindi, le strutture dati ricorsive e le funzioni ricorsive vanno di pari passo.

Ricorsività nel calcolo di Fibonacci

Il matematico italiano Fibonacci definì per primo i numeri di Fibonacci nel XIII secolo per modellare la crescita della popolazione dei conigli. Ha dedotto che partendo da una coppia di conigli nel primo anno, il numero di coppie di conigli nate in un dato anno è uguale al numero di coppie di conigli nate in ciascuno degli ultimi due anni. Questo può essere scritto come: Fn = Fn-1 + Fn-2 (casi base: F0=1 e F1=1).

Quando si scrive una funzione ricorsiva per calcolare il numero di Fibonacci, può risultare in una ricorsione ingenua. Ciò accade quando si segue ingenuamente la definizione della funzione ricorsiva e si finisce per ricalcolare i valori inutilmente. Per evitare il ricalcolo, puoi applicare lru_cache decorator alla funzione. Memorizza i risultati nella cache e evita che il processo diventi inefficiente.

Leggi di più: I 10 migliori strumenti Python che ogni sviluppatore Python dovrebbe conoscere

Pro e contro del ricorsivo

La ricorsione aiuta a semplificare un'attività complessa suddividendola in sottoproblemi. Le funzioni ricorsive rendono il codice più pulito e anche la generazione di sequenze semplice. Ma la ricorsione non arriva senza i suoi limiti. A volte, le chiamate possono rivelarsi costose e inefficienti poiché consumano molto tempo e memoria. Anche le funzioni ricorsive possono essere difficili da eseguire il debug.

Avvolgendo

In questo articolo, abbiamo trattato il concetto di ricorsione Python , lo abbiamo dimostrato usando alcuni esempi e abbiamo anche discusso alcuni dei suoi vantaggi e svantaggi. Con tutte queste informazioni, puoi facilmente spiegare le funzioni ricorsive nella tua prossima intervista con Python!

Se sei curioso di conoscere la scienza dei dati, dai un'occhiata al Diploma PG in Data Science di IIIT-B e upGrad, creato per i professionisti che lavorano e offre oltre 10 casi di studio e progetti, workshop pratici pratici, tutoraggio con esperti del settore, 1- on-1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.