#Ricorsione e ricerca completaIn quasi tutti i problemi, l’obiettivo è svolgere una computazione richiesta nel modo più efficiente possibile. Può capitare che, per mancanza di idee o perché non è possibile fare di meglio, ci interessi scrivere una soluzione che esplori tutte le possibilità compatibili con la struttura del problema. Questo è possibile principalmente attraverso funzioni ricorsive, ovvero funzioni che chiamano se stesse. Facciamo un esempio di funzione ricorsiva:
int somma_primi_n_numeri(int n) {
if (n == 0)
return 0;
return n + somma_primi_n_numeri(n - 1);
}
Questa funzione calcola evidentemente la somma dei primi 𝑛 numeri naturali (con 𝑛≥0)1. È possibile dividere il corpo della funzione in due parti principali:
•Il caso base: 𝑛=0 è la più piccola istanza del problema e siamo in grado di risolverlo senza ulteriori calcoli.•Il caso generale: 𝑛>0, per cui possiamo dire che la somma dei numeri da 0 a 𝑛 è uguale a 𝑛 più la somma dei numeri da 0 a 𝑛−1.Questa funzione ha complessità 𝒪︀(𝑛) perché chiamare somma_primi_n_numeri(n) comporta la chiamata alla stessa funzione con parametro 𝑛−1, poi 𝑛−2 e così via fino a 0.
Un altro esempio è la funzione per calcolare il fattoriale mostrata nel capitolo introduttivo al C++.
In entrambi questi esempi sono presenti un caso base e un caso generale. Una funzione ricorsiva senza caso base non terminerebbe mai l’esecuzione e continuerebbe a chiamarsi all’infinito. È buona pratica che il caso base di una funzione ricorsiva sia quanto più semplice ed elementare possibile.
Un altro esempio comune di funzione ricorsiva è quella che definisce i numeri di Fibonacci, in cui ogni termine è la somma dei due precedenti. Si prendono come casi base fib(0)=0 e fib(1)=1.
int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
In questo caso però la complessità non è più lineare in 𝑛, ma esponenziale2.
Ci sono casi in cui la ricerca completa è l’unico modo per risolvere un problema: un esempio è stampare tutti i possibili array di lunghezza 𝑛 composti da numeri compresi tra 1 e 𝑘 (eventualmente anche ripetuti).
void rec(int n, int k, vector<int> V) {
if (V.size() == n) {
for (int v : V)
cout << v << ' ';
cout << '\n';
return;
}
for (int x = 1; x <= k; x++) {
V.push_back(x);
rec(n, k, V);
V.pop_back();
}
}
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2
L’output mostrato a fianco è il risultato della chiamata rec(3, 2, {}). Il vettore 𝑉 passato tra i parametri è un vettore di appoggio che riempiremo con le varie chiamate (notare che, con qualche accorgimento, è possibile passare 𝑉 per riferimento per non crearne una copia a ogni chiamata).
Se 𝑉 ha 𝑛 elementi, abbiamo finito e possiamo stampare il contenuto del vettore. Altrimenti vogliamo mettere uno alla volta tutti i possibili valori alla fine di 𝑉, ricorrendo poi sulla restante parte dell’array. Per rendere più chiaro lo schema delle chiamate ricorsive è possibile farne una rappresentazione ad albero in cui ogni nodo è una chiamata e ogni foglia contiene uno dei possibili array generati. Per semplicità sono omessi i parametri 𝑛 e 𝑘 nelle chiamate successive alla prima.
1
2
1
2
1
2
1
2
1
2
1
2
1
2
rec(3,2,[])
rec([1])
rec([2])
rec([1,1])
rec([1,2])
rec([2,1])
rec([2,2])
rec([1,1,1])
rec([1,1,2])
rec([1,2,1])
rec([1,2,2])
rec([2,1,1])
rec([2,1,2])
rec([2,2,1])
rec([2,2,2])
[1,1,1]
[1,1,2]
[1,2,1]
[1,2,2]
[2,1,1]
[2,1,2]
[2,2,1]
[2,2,2]
Figure 1: Lo schema ad albero delle chiamate ricorsive.
Notiamo che gli array vengono generati in ordine lessicografico se i valori vengono localmente aggiunti in ordine lessicografico.
Numero della cabala OIS2016
Un numero è bello se ha al massimo 𝑁≤18 cifre, è composto solo dalle cifre 3, 6 e 9, e non ci sono due cifre adiacenti uguali. Siamo interessati al massimo resto di un numero bello diviso per 𝑀.
Prova il problema online: https://training.olinfo.it/task/ois_cabala
Soluzione
Un’osservazione utile è che, scelta la prima cifra tra le 3 disponibili, ogni cifra successiva ha solo due possibilità perché non può essere uguale a quella precedente. Questo abbassa la complessità della ricerca completa da 𝒪︀(3𝑁) a 𝒪︀(2𝑁).
Ora basta generare tutti i numeri belli. Visto che il problema ha più casi di test, è riportata solo la funzione solve(int N, long long M) che risolve un singolo testcase.
long long resto_massimo, limite;
void rec(long long x, long long M) {
if (x >= limite) return;
resto_massimo = max(resto_massimo, x % M);
int ultima_cifra = x % 10;
for (int cifra : {3, 6, 9})
if (ultima_cifra != cifra)
rec(10 * x + cifra, M);
}
long long solve(int N, long long M) {
resto_massimo = 0;
limite = pow(10, N);
rec(0, M);
return resto_massimo;
}
Un altro esempio classico di problema che si risolve ricorsivamente è quello della torre di Hanoi.
Tower of Hanoi CSES
Ci sono tre pile numerate da 1 a 3. All’inizio ci sono 𝑁 dischi nella pila di sinistra di dimensione, partendo dall’alto, 1,2,…,𝑁. Possiamo spostare solo il disco in cima a ogni pila, a patto che la pila di destinazione sia vuota o abbia in cima un disco più grande di quello che spostiamo. Vogliamo stampare una sequenza di mosse per ricreare la pila di dischi a destra nel minor numero di mosse.
Prova il problema online: https://cses.fi/problemset/task/2165/
Soluzione
A prima vista sembra un problema complesso, ma ragionando “ricorsivamente” si semplifica notevolmente.
Facciamo finta di saper risolvere il problema per qualsiasi 𝑛, cioè di saper spostare 𝑛≤𝑁 dischi da una pila di partenza a una di arrivo. Allora ci basterà spostare i primi 𝑁−1 dischi dalla prima alla seconda pila in modo da liberare il disco più grande. A questo punto spostiamo il più grande da sinistra a destra e infine spostiamo i primi 𝑁−1 dal centro a destra.
Quando spostiamo i primi 𝑁−1 non ci dobbiamo preoccupare dei dischi sotto perché sono più grandi. Il numero totale di mosse è 2𝑁−1. Si può semplicemente contare man mano che vengono eseguite, oppure notando che mosse(𝑁)=mosse(𝑁−1)+1+mosse(𝑁−1) e che mosse(1)= 1.
void hanoi(int n, int from, int to) {
if (n == 1) {
cout << from << " " << to << "\n";
return;
}
hanoi(n - 1, from, 6 - from - to);
hanoi(1, from, to);
hanoi(n - 1, 6 - from - to, to);
}
La chiamata hanoi(N, 1, 3) risolve il problema. Per individuare la pila di appoggio viene usata la formula 6−from−to.
#Problemi consigliati
Weird Algorithm (https://cses.fi/problemset/task/1068)
Tris in solitaria (https://training.olinfo.it/task/ois_solitario)
Tris in solitaria 2 (https://training.olinfo.it/task/solitario2)
Geometric Mean (https://training.olinfo.it/task/ois_geometricmean)
1È ovviamente possibile eseguire lo stesso calcolo con un ciclo for o con la formula nota 𝑛(𝑛+1)2.2Vedremo in un capitolo successivo come rendere questa funzione lineare in 𝑛.