Scorri per mostrare il menu

Ricorsione in programmazione si riferisce alla tecnica in cui una funzione richiama sé stessa per risolvere un'istanza più piccola dello stesso problema. È un modo potente ed elegante per risolvere problemi che possono essere suddivisi in sottoproblemi più piccoli dello stesso tipo.

Le funzioni ricorsive sono tipicamente costituite da due componenti:

Caso base: Definisce la condizione di terminazione per la funzione ricorsiva. Quando si raggiunge il caso base, la funzione smette di richiamarsi e restituisce un valore specifico. Questo è necessario per evitare la ricorsione infinita.
Caso ricorsivo: Definisce la logica per suddividere il problema in sottoproblemi più piccoli e richiamare la funzione ricorsivamente con input ridotti. Il caso ricorsivo permette alla funzione di avanzare verso il caso base.

Nota

Il fattoriale di un numero n è definito come segue:

n! = n*(n-1)*(n-2)*..*2*1 = n*(n-1)!

main.cpp


              12345678910111213141516171819
            
#include <iostream>

// Function to calculate factorial
int factorial(int n)
{
    // Base case: factorial of 0 or 1 is 1
    if (n == 0 || n == 1)
        return 1;

    // Recursive case: multiply n with factorial of (n-1)
    std::cout << "Recursive Case: " << n << " * factorial(" << n - 1 << ")" << std::endl;
    return n * factorial(n - 1);
}

int main()
{
    // Call the function
    std::cout << factorial(5) << std::endl;
}

Caso base: Il caso base si verifica quando l'input n è uguale a 0 o 1. In questo caso, il fattoriale è definito come 1. Il caso base garantisce che la ricorsione termini e previene la ricorsione infinita.

Caso ricorsivo: Il caso ricorsivo è la logica per calcolare il fattoriale di n quando n è maggiore di 1. Consiste nel chiamare ricorsivamente la funzione fattoriale con n - 1 come argomento e moltiplicare il risultato per n. Questo riduce il problema a un sottoproblema più piccolo calcolando il fattoriale di un numero minore.

Chiamata della funzione con argomento uguale a 5. Ecco il processo passo dopo passo:

factorial(5) chiama factorial(4) e moltiplica il risultato per 5.
factorial(4) chiama factorial(3) e moltiplica il risultato per 4.
factorial(3) chiama factorial(2) e moltiplica il risultato per 3.
factorial(2) chiama factorial(1) e moltiplica il risultato per 2.
factorial(1) è il caso base e restituisce 1.
la moltiplicazione continua risalendo la catena, ottenendo il fattoriale finale di 5 che è uguale a 120.

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 4. Capitolo 3

Chieda ad AI

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

Ricorsione