Summary  
This chapter covers recursion, detailing how to define a base case and a recursive case so a function calls itself with simpler inputs, and explains how the call stack manages these nested calls.  

General domain of usage  
Processing tree data structures

Una **funzione ricorsiva** è una funzione che richiama sé stessa per risolvere un problema suddividendolo in parti più piccole e semplici.



Definizione

Gli elementi chiave della ricorsione sono:
- **Caso base**: la condizione che interrompe la ricorsione;
- **Caso ricorsivo**: la parte in cui la funzione richiama sé stessa con un input più semplice.

## Perché usare la ricorsione?

Alcuni problemi possono essere naturalmente espressi in termini di sottoproblemi più piccoli. La ricorsione offre un modo chiaro ed elegante per risolverli, facendo sì che una funzione richiami sé stessa per gestire i casi più semplici. È comunemente utilizzata in attività come l'elaborazione di alberi, l'esplorazione di percorsi o la scomposizione di strutture (ad esempio, liste, stringhe).



def print_message(message, times):
    if times > 0:                              # Base case: stop when times is 0
        print(message)
        print_message(message, times - 1)     # Recursive case

print_message("Hello, Recursion!", 3)

Procedimento passo dopo passo per comprendere il funzionamento:

1. `times = 3` → condizione vera, stampa il messaggio, chiama `print_message(message, 2)`;
2. `times = 2` → condizione vera, stampa il messaggio, chiama `print_message(message, 1)`;
3. `times = 1` → condizione vera, stampa il messaggio, chiama `print_message(message, 0)`;
4. `times = 0` → condizione falsa, la ricorsione si interrompe.

**Risultato**: il messaggio viene stampato tre volte.



## Lo stack delle chiamate

Ogni volta che la funzione richiama sé stessa, aggiunge un nuovo frame allo **stack delle chiamate** — una struttura di memoria che tiene traccia delle chiamate di funzione attive. Una volta raggiunto il caso base, ciascuna chiamata precedente viene completata una alla volta in ordine inverso.

Ogni funzione ricorsiva deve avere un caso base. In sua assenza, la funzione continuerà a chiamare sé stessa all'infinito causando un `RecursionError`.

Nota

import unittest

def _dynamic_test(test_case, condition, success_message, failure_message):
    if condition:
        test_case._testMethodName = success_message
        test_case.assertTrue(True, success_message)
    else:
        test_case._testMethodName = failure_message
        test_case.fail(failure_message)

class TestListSum(unittest.TestCase):

    def test_list_sum_basic(self):
        import user_code
        try:
            result = user_code.list_sum([1, 2, 3, 4, 5])
            expected = 15
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[1, 2, 3, 4, 5]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `15` for `[1, 2, 3, 4, 5]`.", failure_message)

    def test_list_sum_another_list(self):
        import user_code
        try:
            result = user_code.list_sum([10, 20, 30])
            expected = 60
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[10, 20, 30]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `60` for `[10, 20, 30]`.", failure_message)

    def test_list_sum_empty(self):
        import user_code
        try:
            result = user_code.list_sum([])
            expected = 0
            condition = result == expected
            failure_message = f"Expected `{expected}` for an empty list, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` correctly returns `0` for an empty list.", failure_message)

    def test_recursion_used(self):
        import user_code
        import inspect
        try:
            source = inspect.getsource(user_code.list_sum)
            condition = "list_sum(" in source.split("def list_sum")[1]
            failure_message = "Expected `list_sum` to call itself recursively."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` function uses recursion.", failure_message)

if __name__ == '__main__':
    unittest.main()

test_main.py

Acquisire una solida comprensione di come le funzioni modellano la programmazione in Python. Padroneggiare la definizione e la chiamata delle funzioni, la gestione degli argomenti, il trattamento dei valori di ritorno e la creazione di codice flessibile ed efficiente utilizzando ricorsione ed espressioni lambda.

Esplora cosa sono le funzioni e perché sono essenziali in Python. Scopri come creare funzioni, definire argomenti, gestire i valori di ritorno e utilizzare efficacemente le funzioni integrate.

Scopri come funzionano gli argomenti posizionali e opzionali in Python. Sviluppo di funzioni adattabili che gestiscono diversi input e migliorano la flessibilità del codice.

Comprendere come lavorare con argomenti arbitrari e keyword per gestire dimensioni di input variabili. Apprendere come queste tecniche rendano le funzioni più dinamiche e organizzate.

Scopri come i valori di ritorno rappresentano l'output di una funzione. Impara a restituire valori singoli o multipli, utilizzare None ed esplorare i generatori per un controllo più avanzato del flusso dei dati.

Sblocca concetti avanzati sulle funzioni con la ricorsione e le funzioni lambda. Scopri come la ricorsione risolve problemi ripetitivi e come le espressioni lambda creano funzioni concise in una sola riga.

Ricorsione

Perché usare la ricorsione?

Un esempio semplice

Lo stack delle chiamate

Soluzione