Risolvere Funzioni Ricorsive a Tratti: Il Metodo del Punto di Raccordo

Risolvere Funzioni Ricorsive a Tratti: Il Metodo del Punto di Raccordo

Quando ci si imbatte in una funzione ricorsiva definita a tratti, la tentazione istintiva è quasi sempre la stessa: cercare di ricavare la formula generale.

Si prova a srotolare la sequenza, si cercano pattern nascosti, e spesso si finisce in un vicolo cieco.

Questo accade perché alcuni problemi sono costruiti esattamente per punire chi cerca l’espressione chiusa.

In questa tipologia di esercizi, molto frequente nelle gare di matematica, la chiave non è calcolare la funzione ovunque, ma forzarla a rivelare il suo valore in un singolo punto di snodo. Vediamo come un semplice passaggio algebrico sul confine di definizione permette di far collassare l’intero problema, trasformando un calcolo apparentemente impossibile in una banale equazione lineare.

Esercizio Guidato

Sia [math]f: \mathbb{Z} \to \mathbb{R}[/math] una funzione definita ricorsivamente da:

[math]\displaystyle f(x) = \begin{cases}
f(x-1) + x, & x > 4 \\
x – f(x+1), & x \le 4
\end{cases}[/math]

Calcolare il valore di [math]f(5) + f(6)[/math].

Soluzione

La funzione è definita in modo diverso a seconda che [math]x[/math] sia maggiore di [math]4[/math] oppure no. L’idea vincente è esprimere tutte le quantità incognite in funzione di un’unica variabile, sfruttando la relazione al punto di confine [math]x = 4[/math].

Iniziamo scrivendo le espressioni per i valori richiesti. Poiché [math]5 > 4[/math], abbiamo:

[math]f(5) = f(4) + 5[/math]

Allo stesso modo, essendo [math]6 > 4[/math]:

[math]f(6) = f(5) + 6[/math]

Sostituendo l’espressione di [math]f(5)[/math] appena trovata, otteniamo [math]f(6)[/math] in funzione di [math]f(4)[/math]:

[math]f(6) = (f(4) + 5) + 6 = f(4) + 11[/math]

Ora il problema si sposta sulla determinazione di [math]f(4)[/math]. Per [math]x = 4[/math] entra in gioco il secondo ramo della funzione:

[math]f(4) = 4 – f(5)[/math]

💡 Il Trucco: La Magia del Punto di Raccordo

È in questo momento che avviene la magia. Sapendo dal passaggio precedente che [math]f(5) = f(4) + 5[/math], andiamo a sostituire questa espressione all’interno dell’equazione appena trovata:

[math]f(4) = 4 – (f(4) + 5)[/math]

L’idea chiave:

La ricorsione non viene svolta. Viene trasformata in un’equazione.

Sviluppando i calcoli da questa sostituzione, la ricorsione è ormai neutralizzata:

[math]f(4) = -1 – f(4)[/math]

Portando i termini simili da una parte, otteniamo [math]2f(4) = -1[/math], da cui ricaviamo facilmente:

[math]\displaystyle f(4) = -\frac{1}{2}[/math]

Trovato il valore al punto di raccordo, il resto è in discesa. Calcoliamo [math]f(5)[/math]:

[math]\displaystyle f(5) = f(4) + 5 = -\frac{1}{2} + 5 = \frac{9}{2}[/math]

E calcoliamo [math]f(6)[/math]:

[math]\displaystyle f(6) = f(5) + 6 = \frac{9}{2} + 6 = \frac{21}{2}[/math]

Infine, la somma richiesta è:

[math]\displaystyle f(5) + f(6) = \frac{9}{2} + \frac{21}{2} = \frac{30}{2} = 15[/math]

Risposta: [math]15[/math]

Esercizi Avanzati di Consolidamento

L’approccio basato sul punto di raccordo è replicabile.

Vediamo alcune varianti con diverse strutture algebriche.

Esercizio Avanzato 1

Sia [math]f(x)[/math] definita come:

[math]\displaystyle f(x) = \begin{cases}
f(x-1) + 2x, & x > 3 \\
x – f(x+1), & x \le 3
\end{cases}[/math]

Calcolare [math]f(4) + f(5)[/math].

Soluzione

Esprimiamo i termini necessari in funzione del punto di snodo [math]x = 3[/math].

Per [math]x = 4[/math], ricaviamo [math]f(4) = f(3) + 8[/math].

Per [math]x = 5[/math], ricaviamo [math]f(5) = f(4) + 10[/math].

Per [math]x = 3[/math], il ramo inferiore ci dice che [math]f(3) = 3 – f(4)[/math].

Sostituendo l’ultima espressione nella prima, applichiamo il trucco:

[math]f(4) = 3 – f(4) + 8[/math]

[math]\displaystyle \begin{aligned}
2f(4) &= 11, \\
f(4) &= \frac{11}{2}.
\end{aligned}[/math]

Di conseguenza:

[math]\displaystyle f(5) = \frac{11}{2} + 10 = \frac{31}{2}[/math]

La somma richiesta è:

[math]\displaystyle f(4) + f(5) = \frac{42}{2} = 21[/math]

Risposta: [math]21[/math]

Esercizio Avanzato 2

Sia [math]f(x)[/math] definita come:

[math]\displaystyle f(x) = \begin{cases}
f(x-1) + 3, & x > 2 \\
2x – f(x+1), & x \le 2
\end{cases}[/math]

Calcolare [math]f(3) + f(4)[/math].

Soluzione

Il punto di raccordo è [math]x = 2[/math].

Per [math]x = 3[/math], si ha [math]f(3) = f(2) + 3[/math].

Per [math]x = 4[/math], si ha [math]f(4) = f(3) + 3[/math].

Per [math]x = 2[/math], vale [math]f(2) = 4 – f(3)[/math].

Sostituendo la relazione di [math]f(2)[/math] nell’equazione per [math]f(3)[/math]:

[math]f(3) = 4 – f(3) + 3[/math]

[math]\displaystyle \begin{aligned}
2f(3) &= 7, \\
f(3) &= \frac{7}{2}.
\end{aligned}[/math]

Procediamo calcolando [math]f(4)[/math]:

[math]\displaystyle f(4) = \frac{7}{2} + 3 = \frac{13}{2}[/math]

La somma vale:

[math]\displaystyle \frac{7}{2} + \frac{13}{2} = 10[/math]

Risposta: [math]10[/math]

Esercizio Avanzato 3

Sia [math]f(x)[/math] definita come:

[math]\displaystyle f(x) = \begin{cases}
f(x-1) + x^2, & x > 1 \\
1 – f(x+1), & x \le 1
\end{cases}[/math]

Calcolare [math]f(2) + f(3)[/math].

Soluzione

Il perno della funzione è [math]x = 1[/math].

Per [math]x = 2[/math], vale [math]f(2) = f(1) + 4[/math].

Per [math]x = 3[/math], vale [math]f(3) = f(2) + 9[/math].

Per [math]x = 1[/math], il ramo inferiore impone [math]f(1) = 1 – f(2)[/math].

Unendo le equazioni per [math]f(2)[/math] e [math]f(1)[/math]:

[math]f(2) = 1 – f(2) + 4[/math]

[math]\displaystyle \begin{aligned}
2f(2) &= 5, \\
f(2) &= \frac{5}{2}.
\end{aligned}[/math]

Calcoliamo quindi [math]f(3)[/math]:

[math]\displaystyle f(3) = \frac{5}{2} + 9 = \frac{23}{2}[/math]

La somma vale:

[math]\displaystyle \frac{5}{2} + \frac{23}{2} = 14[/math]

Risposta: [math]14[/math]

Esercizio Avanzato 4

Sia [math]f(x)[/math] definita come:

[math]\displaystyle f(x) = \begin{cases}
f(x-1) + x, & x > 0 \\
2 – f(x+1), & x \le 0
\end{cases}[/math]

Calcolare [math]f(1) + f(2) + f(3)[/math].

Soluzione

Il raccordo si trova nell’origine, [math]x = 0[/math].

Scriviamo in sequenza:

Per [math]x = 1 \implies f(1) = f(0) + 1[/math]

Per [math]x = 2 \implies f(2) = f(1) + 2[/math]

Per [math]x = 3 \implies f(3) = f(2) + 3[/math]

Per [math]x = 0 \implies f(0) = 2 – f(1)[/math]

Risolviamo l’equazione nel punto di contatto tra i due rami:

[math]f(1) = 2 – f(1) + 1[/math]

[math]\displaystyle \begin{aligned}
2f(1) &= 3, \\
f(1) &= \frac{3}{2}.
\end{aligned}[/math]

Da qui procediamo a cascata:

[math]\displaystyle f(2) = \frac{3}{2} + 2 = \frac{7}{2}[/math]

[math]\displaystyle f(3) = \frac{7}{2} + 3 = \frac{13}{2}[/math]

La somma complessiva è:

[math]\displaystyle \frac{3}{2} + \frac{7}{2} + \frac{13}{2} = \frac{23}{2}[/math]

Risposta: [math]\displaystyle \frac{23}{2}[/math]

Perché questa classe di problemi è interessante?

Dal punto di vista strutturale, l’eleganza di questo problema risiede interamente nel suo comportamento al limite del dominio. Analizziamo il meccanismo del primo esercizio: se provassimo a implementare questa funzione in modo “ingenuo” tramite uno script in Python o C++, otterremmo rapidamente un errore fatale di esecuzione.

Chiedere a una macchina di valutare [math]f(4)[/math] innescherebbe una chiamata a [math]f(5)[/math]. Ma poiché [math]5 > 4[/math], la funzione chiamerebbe a sua volta [math]f(4) + 5[/math], creando di fatto un ciclo infinito (nello specifico, un superamento del limite di ricorsione, o Stack Overflow). Il grafo delle dipendenze della funzione contiene un loop chiuso.

Il problema, dunque, non è risolvibile per pura sostituzione computazionale in modalità top-down. La soluzione matematica richiede un cambio di paradigma: trattare l’invocazione ricorsiva [math]f(k)[/math] non come un processo algoritmico da eseguire iterativamente, ma come un’incognita algebrica statica, risolvibile con le regole esposte di seguito.

def f(x):
    if x > 4:
        return f(x - 1) + x
    else:
        return x - f(x + 1)

print(f(5))

RecursionError: maximum recursion depth exceeded

f(5)
│
└── f(4)
     │
     └── f(5)
          │
          └── f(4)
               │
               └── f(5)
                    │
                    ...

Quando funziona questo metodo? (Generalizzazione)

Questo procedimento non è una forzatura adatta a un singolo esercizio, ma un vero e proprio metodo generale. È applicabile ogni qual volta si presentano queste specifiche condizioni:

• la funzione è definita a tratti;
• i due rami si richiamano attraverso il punto di confine;
• il ciclo coinvolge pochi valori consecutivi;
• il valore al raccordo compare da entrambi i lati della definizione.

In questi casi la ricorsione può essere trasformata in un sistema algebrico di poche equazioni. Invece di cercare una formula chiusa inesistente o impraticabile, ci si ancora all’unica certezza del sistema, risolvendo il problema in pochi, eleganti passaggi algebrici.