Concetto di ricorsione

1.1 Definizione di ricorsione e le sue principali concezioni.

La ricorsione è quando qualcosa fa se stessa ancora e ancora. Immagina di avere un'istruzione e parte di questa istruzione dice di seguire l'istruzione stessa. È come se avessi dato il comando di ripetere il comando stesso.

Esempi nella vita reale:

Specchi uno di fronte all'altro:

Immagina di essere tra due specchi. Vedi il tuo riflesso, e nel riflesso vedi anche il tuo riflesso, e così via. Questo è un esempio di ricorsione, perché ogni specchio mostra il riflesso dell'altro specchio.

Matrioske:

Una matrioska è una bambola che contiene un'altra bambola, e all'interno di quella un'altra, e così via. Quando arrivi alla bambola più piccola, non c'è più niente da aprire. È come il caso base nella ricorsione — il momento in cui fermarsi.

Divisione della pizza:

Immagina di dividere una pizza a metà. Poi prendi una metà e la dividi di nuovo a metà, e continui finché le fette non diventano troppo piccole da dividere. Dividere in parti è un processo ricorsivo, e il momento in cui non puoi più dividere una fetta è il caso base.

Importante! La ricorsione non è una ripetizione infinita di un comando, piuttosto si tratta di suddividere un problema complesso in parti, e l'approccio alla risoluzione delle parti del problema è analogo alla risoluzione dell'intero problema.

Come funziona?

Per comprendere la ricorsione, bisogna sapere due concetti base:

• Caso base: è la condizione in cui la ricorsione si interrompe. Per esempio, nel caso delle matrioske, il caso base è quando apri la matrioska più piccola, e dentro non c'è più nulla.
• Caso ricorsivo: è quando il problema si ripete con parti più piccole. Nell'esempio della pizza dividi una fetta e poi dividi la metà, e così via.

Perché è utile?

La ricorsione aiuta a risolvere problemi complessi, suddividendoli in parti più semplici. Invece di risolvere tutto il problema in una volta, lo risolvi a pezzetti.

Altri esempi dalla vita:

Fiaba all'interno di una fiaba:

Immagina che l'eroe di una fiaba racconti un'altra fiaba, e l'eroe di quella fiaba inizi a raccontare un'altra fiaba ancora. Quando una delle fiabe finisce, torni alla fiaba precedente. Il caso base è quando finisce l'ultima fiaba.

Disegno ricorsivo:

Disegni un grande triangolo e poi in ogni angolo di questo triangolo disegni un triangolo più piccolo, e così continui finché i triangoli diventano troppo piccoli. Il caso base è quando il triangolo diventa così piccolo da non poter essere disegnato.

1.2 Caso base: definizione ed esempi.

Il caso base è la condizione che interrompe le chiamate ricorsive e permette alla funzione di restituire un valore specifico. Di solito è la soluzione più semplice e ovvia del problema, che non richiede ulteriore ricorsione.

Esempi di caso base:

Fattoriale di un numero:

Il fattoriale di un numero n è indicato come F(n) == 1*2*3*…*n. È anche ovvio che F(n) == n* F(n-1).

Il caso base: il fattoriale del numero 0 o 1 è uguale a 1. F(0) == F(1)==1

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Caso base
    else:
        return n * factorial(n - 1)
        

Numeri di Fibonacci:

I numeri di Fibonacci sono una sequenza: 1, 1, 2, 3, 5, 8, 13, … Dove ogni numero successivo è la somma dei due precedenti. Per F(n) == F(n-1) + F(n-2)

Il caso base: i primi due numeri di Fibonacci sono uguali a 1, quindi il "numero zero" di Fibonacci è 0. Oppure F(0) = 0 e F(1) = 1.

def fibonacci(n):
    if n == 0:
        return 0  # Caso base
    elif n == 1:
        return 1  # Caso base
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 Caso ricorsivo: definizione ed esempi

Il caso ricorsivo è la parte della funzione che risolve il problema chiamando sé stessa con nuovi parametri che avvicinano la soluzione al caso base. Ogni chiamata ricorsiva riduce o modifica il problema per raggiungere infine il caso base.

Esempi di caso ricorsivo:

Fattoriale di un numero:

Il caso ricorsivo: il fattoriale di un numero n è n moltiplicato per il fattoriale di n-1.

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Caso base
    else:
        return n * factorial(n - 1)  # Caso ricorsivo
        

Numeri di Fibonacci:

Il caso ricorsivo: F(n) è la somma di F(n-1) e F(n-2).

def fibonacci(n):
    if n == 0:
        return 0  # Caso base
    elif n == 1:
        return 1  # Caso base
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Caso ricorsivo
        

1.4 Esempi di algoritmi ricorsivi

1. Percorso di un albero binario:

Esempio di percorso in ordine "in-order".

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# Esempio di utilizzo:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. Ricerca del massimo elemento in una lista:

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # Caso base
    else:
        max_of_rest = find_max(lst[1:])  # Caso ricorsivo
        return max(lst[0], max_of_rest)
        
# Esempio di utilizzo:
print(find_max([1, 5, 3, 9, 2]))  # Output: 9
        
        

3. Ricerca binaria ricorsiva:

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Caso base: elemento non trovato
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # Caso base: elemento trovato
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # Caso ricorsivo
    else:
        return binary_search(arr, target, left, mid - 1)  # Caso ricorsivo
        
# Esempio di utilizzo:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # Output: 4