algoritmo ricorsivo

In informatica viene detto algoritmo ricorsivo un algoritmo espresso in termini di se stesso, ovvero in cui l'esecuzione dell'algoritmo su un insieme di dati comporta la semplificazione o suddivisione dell'insieme di dati e l'applicazione dello stesso algoritmo agli insiemi di dati semplificati. Tale tecnica risulta particolarmente utile per eseguire dei compiti ripetitivi su di un set di variabili in input. L'algoritmo richiama se stesso generando una sequenza di chiamate che ha termine al verificarsi di una condizione particolare che viene chiamata condizione di terminazione, che in genere si ha con particolari valori di input. La tecnica ricorsiva permette di scrivere algoritmi eleganti e sintetici per molti tipi di problemi comuni, anche se non sempre le soluzioni ricorsive sono le più efficienti. Questo è dovuto al fatto che comunemente la ricorsione viene implementata utilizzando le funzioni, e che l'invocazione di una funzione ha un costo rilevante, e questo rende più efficienti gli algoritmi iterativi. In alcuni casi la ricorsione è altrettanto efficiente di un ciclo iterativo: linguaggi dei paradigmi funzionali o logici tipicamente non hanno il concetto di ciclo ed usano la ricorsione ottimizzando automaticamente.