Tutorial del Python - Funzione ricorsiva

1. Cos’è la funzione ricorsiva di Python
2. Limitazione della ricorsione
3. Vantaggio della ricorsione
4. Svantaggio della ricorsione

In questa sezione, imparerete la funzione ricorsiva di Python.

Cos’è la funzione ricorsiva di Python

Una funzione ricorsiva è una funzione che chiama se stessa e questo processo è chiamato ricorsione di funzione.

Per esempio, calcoliamo il fattoriale di un numero, per esempio, 6.

6 * 5 * 4 * 3 * 2 * 1

Nel codice seguente viene creata una funzione ricorsiva che trova il fattoriale di un numero:

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


a = 6
print("Factorial of", a, "=", fact(a))

Factorial of 6 = 720

La funzione fact(n) è una funzione ricorsiva. La funzione fact si chiama con l’argomento n-1 fino a quando il numero diventa 1 ed è così che si calcola il fattoriale, cioè moltiplicando il numero per il fattoriale di uno inferiore al numero.

In questa funzione ricorsiva, c’è una condizione di base che è quando il numero diventa 1, 1 viene restituito e in questo modo la chiamata ricorsiva diventa finita.

Quando si crea una funzione ricorsiva, ci deve essere una condizione di base per terminare quella chiamata ricorsiva.

Limitazione della ricorsione

Come avete notato, ogni volta che la funzione chiama se stessa, ha bisogno di un po’ di memoria per memorizzare alcuni valori intermedi. Pertanto la funzione ricorsiva consuma molta più memoria di una normale funzione non ricorsiva. Python imposta la limitazione delle chiamate ricorsive a 3000.

>>> import sys
>>> sys.getrecursionlimit()
3000

Solleva un RecursionError se la ricorsione supera 3000.

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))

Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    print(factorial(4000))
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  [Previous line repeated 989 more times]
  File "<pyshell#1>", line 2, in factorial
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Soluzione per rimuovere la limitazione della ricorsione

È possibile risolvere la limitazione della ricorsione impostando la limitazione della ricorsione su un numero maggiore della ricorsione richiesta.

import sys

sys.setrecursionlimit(5000)


def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))

Vantaggio della ricorsione

• Utilizzando funzioni ricorsive, il problema può essere suddiviso in sotto-problemi che possono essere facilmente risolti.
• Il codice diventa ordinato e pulito.

Svantaggio della ricorsione

• A volte è difficile seguire la logica della funzione ricorsiva.
• Per risolvere ogni problema secondario ci vorrà molto tempo, per cui le funzioni ricorsive sono inefficienti.