Ricorsione
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.
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)chiamafactorial(4)e moltiplica il risultato per 5.factorial(4)chiamafactorial(3)e moltiplica il risultato per 4.factorial(3)chiamafactorial(2)e moltiplica il risultato per 3.factorial(2)chiamafactorial(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
5che è uguale a120.
Grazie per i tuoi commenti!
Chieda ad AI
Chieda ad AI
Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione
