[C++] Dubbio su ricorsione di un algoritmo

[oleg.fresi]

Ho il seguente algoritmo:

#include <bits/stdc++.h> 
using namespace std; 
  
int countWaysUtil(int x, int n, int num) 
{ 
    int val = (x - pow(num, n)); 
    if (val == 0) 
        return 1; 
    if (val < 0) 
        return 0; 
  
    return countWaysUtil(val, n, num + 1) + 
           countWaysUtil(x, n, num + 1); 
} 
  
int countWays(int x, int n) 
{ 
    return countWaysUtil(x, n, 1); 
} 
  

int main() 
{ 
    int x = 100, n = 2; 
    cout << countWays(x, n); 
    return 0; 
} 

Il codice non è mio, l'ho trovato su internet per studiarlo. Il codice implementa un algoritmo che serve per contare tutti i modi di scrivere un numero come somma di potenze, data la base e l'esponenet in input.
La mia difficoltà sta nel capire come opera la ricorsione in questo caso, ovvero queste du chiamate ricorsive unite dalla somma:

return countWaysUtil(val, n, num + 1) + countWaysUtil(x, n, num + 1);

.
Potreste per favore spiegarmi o aiutarmi a capire come funziona?

[apatriarca]

Credo che in questi casi sia spesso utile stampare le funzioni che vengono richiamate con degli esempi più piccoli. Ho per esempio modificato il codice nel seguente modo con [tt]x = 10[/tt] in modo da avere un output più ridotto.

#include <iostream>
#include <cmath>
using namespace std;

int countWaysUtil(int x, int n, int num)
{
    int val = (x - pow(num, n));
    if (val == 0) {
        cout << "countWaysUtil(" << x   << ", " << n << ", " << num << ") = 1\n";
        return 1;
    }
    if (val < 0) {
        cout << "countWaysUtil(" << x   << ", " << n << ", " << num << ") = 0\n";
        return 0;
    }

    cout << "countWaysUtil(" << x   << ", " << n << ", " << num << ") = "
            "countWaysUtil(" << val << ", " << n << ", " << num + 1 << ") + "
            "countWaysUtil(" << x   << ", " << n << ", " << num + 1 << ")\n";

    return countWaysUtil(val, n, num + 1) +
           countWaysUtil(x, n, num + 1);
}

int countWays(int x, int n)
{
    return countWaysUtil(x, n, 1);
}


int main()
{
    int x = 10, n = 2;
    cout << countWays(x, n) << endl;
    return 0;
}

L'output è il seguente:

countWaysUtil(10, 2, 1) = countWaysUtil(9, 2, 2) + countWaysUtil(10, 2, 2)
countWaysUtil(9, 2, 2) = countWaysUtil(5, 2, 3) + countWaysUtil(9, 2, 3)
countWaysUtil(5, 2, 3) = 0
countWaysUtil(9, 2, 3) = 1
countWaysUtil(10, 2, 2) = countWaysUtil(6, 2, 3) + countWaysUtil(10, 2, 3)
countWaysUtil(6, 2, 3) = 0
countWaysUtil(10, 2, 3) = countWaysUtil(1, 2, 4) + countWaysUtil(10, 2, 4)
countWaysUtil(1, 2, 4) = 0
countWaysUtil(10, 2, 4) = 0
1

L'idea principale è che il terzo argomento cresce ad ogni passo ricorsivo e assume ogni valore intero fino a quando la sua potenza non superi o uguagli il valore del primo argomento. Se è esattamente uguale al primo argomento allora abbiamo trovato un modo per scrivere questo numero e restituiamo 1. Se il valore è più grande non abbiamo trovato alcun nuovo modo e quindi restituiamo \(0\). Quando non ci troviamo in nessuna delle due situazioni possiamo però dire che una scrittura del numero in termini di potenze può contenere o meno la potenza del valore che stiamo considerando. Nel primo caso dobbiamo sottrarre la potenza al primo argomento e nel secondo invece manteniamo il valore uguale. Siccome abbiamo considerato tutte le basi della potenza fino al valore del terzo argomento nel successivo passo ricorsivo considereremo il valore successivo. Spero di essere riuscito a darti una idea.