Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

Ricorsione

La ricorsione consiste nel fatto che una funzione richiama sé stessa, direttamente o tramite altre funzioni. Perché il calcolo termini, servono un caso base raggiungibile e passaggi ricorsivi che procedano verso quel caso.

Versione: C++23; repository compiler flag, production runtime not attested

Sintassi

ReturnType function(Parameters) {
    if (base_condition) return base_value;
    return combine(function(smaller_arguments));
}

La ricorsione (recursion) è una tecnica in cui una funzione richiama sé stessa, direttamente o indirettamente tramite altre funzioni. Non richiede parole chiave speciali: usa la normale sintassi delle chiamate di funzione. C++ consente le chiamate ricorsive, ma main non deve essere chiamata ricorsivamente.

Un algoritmo tipico ha un caso base, che restituisce un risultato senza effettuare un’altra chiamata, e un passaggio ricorsivo, che riduce il problema. Per i dati per cui il calcolo deve terminare, ogni catena di chiamate deve raggiungere un caso base. Avere soltanto una condizione di arresto non basta se gli argomenti non la soddisfano mai.

Nell’esempio, sum_to(5) calcola la somma da 1 a 5 inclusi. Le chiamate riducono n finché raggiunge 0; i ritorni successivi sommano quindi i valori in sospeso, ottenendo 15. Ogni invocazione ha il proprio parametro n: non è un’unica variabile condivisa. Per n <= 0, la funzione restituisce 0.

Non considerare l’esempio una soluzione per dati di dimensioni arbitrarie: una ricorsione profonda può esaurire le risorse di esecuzione e una somma fuori dall’intervallo di int causa un comportamento indefinito. Per dati grandi, valuta un ciclo e controlli dell’intervallo. La fonte indicata è una bozza dello standard in evoluzione, non una pubblicazione C++23 definitiva; l’esempio usa una sintassi compatibile con C++23.

Esempi

#include <iostream>

int sum_to(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main() {
    std::cout << sum_to(5) << '\n';
}

Risultato

15

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti