|
|
La ricorsione è un modo di specificare un'entità (un oggetto, una struttura, un algoritmo, ecc.) in termini di se stessa. Nella ricorsione istanze più complesse di un' entità vengono definite a partire da istanze più semplici della stessa entità, e solo le istanze elementari, cioè quelle più semplici di tutte, vengono date esplicitamente. Un modo più "algoritmico" di spiegare la ricorsione potrebbe essere il seguente:
Base della ricorsione, si da la definizione esplicita del caso elementare;
Passo ricorsivo, si definisce l'entità originale come combinazione delle sue parti.
Il concetto di ricorsione nella programmazione è strettamente collegato a quello di induzione o ricorrenza in Matematica. Molti concetti matematici sono definiti in modo induttivo o tramite ricorrenze. L'esempio canonico di un concetto matematico definito in modo induttivo è quello di numero naturale:
Base: 0 è un numero naturale
Passo: se n è un numero naturale, allora anche il successore di n, S(n) (cioè n + 1), è un numero naturale.
La ricorsione sta alla base di una tecnica molto potente di programmazione, chiamata divide et impera (in latino "dividi e comanda", la tecnica usata da Giulio Cesare per sconfiggere i Galli). Essa consiste nello scomporre (divide) un problema in sottoproblemi dello stesso tipo, più semplici da risolvere (impera). Questa tecnica è la chiave per la progettazione di molti algoritmi importanti, ed è un ingrediente fondamentale della programmazione dinamica.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.