Un programma informatico è detto ricorsivo se, durante la sua esecuzione, richiama sé stesso. Senza esempi, questa frase è difficile da capire… ed è ancora più difficile capire perché oggi tutti i linguaggi di programmazione usino la ricorsività, mentre i primi, come Cobol per la gestione o Fortran per il calcolo scientifico, ne facevano a meno. Uno dei motivi è l’affidabilità dei programmi ricorsivi, praticamente gli unici di cui si possa dimostrare che fanno davvero ciò che devono fare…
Induzione e giochi di carte
======================================================================================================
Prendete un mazzo di carte, mescolatelo e provate a ordinarlo. Come fare? A priori, il compito è complesso. Il principio di induzione permette di semplificarlo notevolmente ponendo la domanda in modo diverso: immaginate di saper ordinare n carte, come ordinarne n + 1? In termini più concreti, sapete ordinare un mazzo di quattro carte. Ve ne viene data una in più: che cosa fate?
Naturalmente ordinate le prime quattro, poi inserite la quinta al posto giusto. Basta confrontarla successivamente con le carte già ordinate, cominciando dalla prima. Qui la nuova carta va inserita dopo la seconda. Questo metodo si fonda esattamente sull’idea di induzione! Per convincervene, formalizziamolo nello stile delle dimostrazioni per induzione. Ecco dunque un metodo che, dato un mazzo di carte T, restituisce lo stesso mazzo ordinato:
