Cos’è la ricorsione e come la usi?

La ricorsione è un concetto di programmazione divertente ma può essere un po ‘complicato da imparare. Ricorsione significa semplicemente qualcosa che si ripete. Se vuoi vedere un esempio sfacciato di ricorsione, prova a cercare ricorsione su Google. Troverai un uovo di Pasqua in cui i suggerimenti dei risultati di ricerca sono ricorsivi. Se, d’altra parte, vuoi imparare a codificare una funzione ricorsiva, continua a leggere!

Cos’è una funzione ricorsiva?

Una funzione ricorsiva è una funzione che chiama se stessa. In sostanza crei un ciclo con una funzione. Come puoi immaginare, queste possono essere funzioni complicate da scrivere. Non vuoi che il tuo codice venga eseguito per sempre.

Simile a un ciclo, una funzione ricorsiva sarà controllata da una condizione. Una volta soddisfatta la condizione, la funzione interrompe la chiamata a se stessa, il che interrompe il ciclo. È così che puoi creare una funzione che chiama se stessa senza che funzioni per sempre.

Sebbene una funzione ricorsiva si comporti come un ciclo, viene eseguita dal computer in modo diverso. Quindi, alcuni algoritmi sono più efficienti in un ciclo e altri beneficiano di una funzione ricorsiva. Ma prima di esaminare come utilizzare una funzione ricorsiva, è necessario sapere come scriverne una.

Come scrivere una funzione ricorsiva

Tutte le funzioni ricorsive hanno la stessa struttura di base:

FUNCTION name
 IF condition THEN
 RETURN result
 ELSE
 CALL FUNCTION name
 END FUNCTION

L’esempio sopra è scritto in pseudo-codice. Delinea la struttura della funzione, che può essere applicata a qualsiasi lingua. Per semplicità, in questo articolo, ci concentreremo su Python.

La prima cosa da notare su una funzione ricorsiva è che quando la condizione è soddisfatta, la funzione esce dalla ricorsione. Ciò significa che quando scrivi una funzione ricorsiva, la prima cosa che vorrai determinare è quando fermare la ricorsione.

Se la condizione non è soddisfatta, la funzione chiamerà se stessa. Quindi, se vuoi inviare informazioni al ciclo successivo, dovrai inviarle come argomento nella tua funzione. Questo può dare alle funzioni ricorsive molto più potere.

Correlati: che cos’è una funzione nella programmazione?

Esempio di funzione ricorsiva in Python

Sarà molto più facile capire come funziona la ricorsione quando la vedrai in azione. Per dimostrarlo, scriviamo una funzione ricorsiva che restituisca il fattoriale di un numero.

I fattoriali restituiscono il prodotto di un numero e di tutti gli interi prima di esso. Ad esempio, il fattoriale di 5 è 5 x 4 x 3 x 2 x 1 o 120.

def factorialFunction(numberToMultiply):
 if numberToMultiply == 1 :
 return 1
 else :
 return numberToMultiply * factorialFunction(numberToMultiply - 1)

 result = factorialFunction(3)
 print(result)
 //Outputs: 6

Il programma sopra ti darà il risultato 6, che è il fattoriale del numero 3. All’inizio può creare un po ‘di confusione. Sarà utile eseguire il programma passo dopo passo.

  1. Quando la funzione viene chiamata, numberToMultiply è uguale a 3.
  2. La condizione non è soddisfatta, quindi passiamo alla condizione else .
  3. La nostra funzione restituisce 3 * ma viene poi messa in pausa. Deve chiamare se stesso per determinare il resto del valore che sta restituendo.
  4. Quando la funzione viene chiamata questa volta, il valore di numberToMultiply è uguale a 2.
  5. La condizione non è soddisfatta, quindi passiamo alla condizione else.
  6. La nostra funzione restituisce 2 * ma viene poi messa in pausa. Deve chiamare se stesso per determinare il resto del valore che sta restituendo.
  7. La funzione viene chiamata ancora una volta. Questa volta, il valore di numberToMultiply è uguale a 1.
  8. La nostra condizione if è soddisfatta. La funzione restituisce 1.
  9. La funzione del passaggio 6 può ora restituire 2 * 1 alla funzione del passaggio 3.
  10. La funzione al passaggio tre può ora restituire 3 * 2 * 1, che è 6.

La ricorsione è un concetto complicato. Può essere utile pensarlo come impilare una funzione sopra un’altra funzione. Una volta che una funzione è stata finalmente risolta, può rimandare le informazioni indietro nello stack, finché tutte le funzioni non hanno la loro risposta.

Questo è più o meno quello che fa il tuo computer. Quando si chiama la funzione, viene mantenuta in memoria fino a quando non viene restituita. Ciò significa che le funzioni ricorsive possono utilizzare molta più memoria di un ciclo.

Quindi, potrebbe non essere efficiente scrivere i cicli come funzioni ricorsive, ma è un ottimo modo per esercitarsi a costruirli. Dovresti essere in grado di codificare i cicli come funzioni ricorsive con risultati simili.

Un esempio di come convertire un ciclo in una funzione ricorsiva

print("Enter an even number:")
 i = int(input())
 while (i % 2) != 0 :
 print("That number is not even. Please enter a new number:")
 i = int(input())

Questo ciclo può anche essere scritto in modo ricorsivo come:

def recursiveFunction(number) :
 if (number % 2) == 0 :
 return number
 else:
 print("That number is not even. Please enter a new number:")
 recursiveFunction(int(input()))

 print("Enter and even number:")
 i = recursiveFunction(int(input()))

Il primo passo è determinare quando si desidera che la funzione venga interrotta. In questo caso, vogliamo che si fermi una volta immesso un numero pari. Nel nostro esempio, number tiene traccia dell’input dell’utente. Se inseriscono un numero pari, restituiamo il numero. Altrimenti, continueremo a chiedere un nuovo numero.

Per impostare il ciclo, chiamiamo di nuovo la nostra funzione. Ma questa volta, il numero che passiamo alla funzione successiva è il nuovo numero inserito dall’utente. La prossima chiamata di funzione controllerà il numero.

Questa è davvero una brutta funzione! Sì, sta controllando se il numero è pari, come il nostro ciclo, ma non è efficiente. Ogni volta che l’utente immette un numero dispari, la funzione viene mantenuta in memoria e viene chiamata una nuova funzione. Se lo fai abbastanza volte, finirai la memoria!

Correlati: esempi di Python di base che ti aiuteranno a imparare velocemente

Un esempio reale di una funzione ricorsiva

Gli esempi precedenti erano buoni esempi di quando non usare la ricorsione. Allora, dove viene utilizzata la ricorsione? Un buon esempio di quando si desidera utilizzare la ricorsione è la ricerca in un albero binario.

Quando i dati sono strutturati in un albero binario, devi percorrere molti percorsi per cercare i dati. In ogni punto dell’albero, devi decidere se vuoi continuare la ricerca a destra oa sinistra. Puoi salvare la parte dell’albero che hai visitato in una variabile, ma una funzione ricorsiva può tracciare naturalmente quell’informazione.

Immagina di cercare il numero sei nell’albero sopra. Potremmo creare una funzione ricorsiva che ricerca l’albero da sinistra a destra. L’algoritmo sarebbe simile a questo:

FUNCTION searchTree(branchToSearch)
 IF find 6 OR end of tree THEN
 RETURN result
 ELSE
 PROCESS branch
 CALL FUNCTION searchTree(left)
 CALL FUNCTION searchTree(right)
 END FUNCTION

In questo esempio di pseudocodice, l’algoritmo cercherà prima il lato sinistro dell’albero. Ogni volta che si visita un nuovo numero, la funzione viene messa in pausa e mantenuta in memoria. Questo ci permette di monitorare dove siamo stati.

L’algoritmo cercherà sempre prima il lato sinistro il più lontano possibile. una volta raggiunta la fine dell’albero, il searchTree (a sinistra) si completerà e controllerà il lato destro. Dopo aver controllato entrambi i lati, la ricerca esegue il backup di un ramo e continua a controllare il lato destro.

Se gli algoritmi cercassero l’intero albero, lo farebbero nell’ordine:

2, 7, 2, 6, 5, 11, 5, 9 e 4

Vedi se riesci a seguire usando lo pseudo-codice sopra.

Revisione della ricorsione

La ricorsione è un argomento avanzato. Ci vorrà del tempo per capirlo e ancora di più per diventare bravo a codificarlo. Aiuterà se passi passo dopo passo attraverso le funzioni ricorsive. Potrebbe anche aiutare a impilare schede o post-it mentre si esegue una funzione quando si impara a rappresentare ciascuna chiamata di funzione.

Quando scrivi una funzione ricorsiva, inizia decidendo come vuoi uscire dalla funzione. Quindi, determina come impostare il tuo loop. Identificare quali informazioni devono essere inviate alla successiva chiamata di funzione e quali devono essere restituite.

Il modo migliore per imparare la ricorsione è praticarla e imparare dai propri errori. Guarda un po ‘del tuo vecchio codice e sfida te stesso a riscrivere i loop come funzioni ricorsive. Probabilmente non renderà il tuo codice più efficiente, ma sarà una buona pratica.