Il problema è che chiami la tua funzione ricorsivamente N volte. Ogni volta che chiami la funzione viene consumata memoria sullo stack (almeno l'indirizzo di ritorno, più tutte le variabili locali). Se N è troppo grande lo stack non può contenere tutte le funzioni.
Hai due alternative:
- Riscrivere la funzione in modo che sia tail-recursive
- Riscrivere la funzione in modo iterativo (che è concettualmente la stessa cosa, una funzione tail-recursive è implementabile tramite iterazione)
Una funzione è tail-recursive se, ogni volta che chiama se stessa ricorsivamente, è l'ultima istruzione che esegue. La tua funzione non lo è: dopo aver chiamato se stessa deve usare il risultato nell'espressione da restituire. Quella funzione causerà uno stack overflow in qualsiasi linguaggio, non è un problema di Java.
La procedura standard per trasformare una funzione ricorsiva in una funzione tail-recursive è di usare un accumulatore. L'esempio classico del fattoriale:
- Codice:
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int factorial_tail_recursive_inner(int n, int accumulator) {
if (n == 0) {
return accumulator;
} else {
int new_accumulator = n * accumulator;
return factorial_tail_recursive_inner(n - 1, new_accumulator);
}
}
int factorial_tail_recursive(int n) {
int initial_accumulator = 1;
return factorial_tail_recursive_inner(n, initial_accumulator);
}
int factorial_iterative(int n) {
int accumulator = 1; // initial_accumulator
for (int i = 0; i < n; ++i) {
accumulator = n * accumulator; // recursive step
}
return accumulator;
}
Come vedi, in factorial_tail_recursive_inner() quando chiami ricorsivamente la funzione non hai più altre operazioni, restituisci direttamente il risultato. Questo permette al programma di liberare lo spazio prima della chiamata, dato che non servono più informazioni sulla funzione chiamante, quindi lo stack non cresce (semplificando molto).
Invece di usare il valore restituito dalla ricorsione mantieni un accumulatore continuamente aggiornato che viene passato lungo la ricorsione. Come vedi la soluzione iterativa è praticamente identica a quella tail-recursive. Si tratta esattamente di un ciclo implementato tramite ricorsione.
Quindi devi trovare un modo di riscrivere la tua funzione in modo che usi un accumulatore.