récurcivité
Appliquer les processus itératifs du passé pouvait s'avérer long et fastidieux. Avec l'avènement de l'informatique, de nouvelles voies se sont ouvertes. L'écriture de programmes récursifs, s'appelant eux-mêmes, permet de prouver plus facilement le bon fonctionnement d'un algorithme. D'un point de vue pratique, la récursivité offre une alternative élégante et souvent limpide aux boucles. L'écriture (courte) de ces programmes récursifs, alliée à une puissance de calcul croissante, ouvre des horizons dans la résolution de problèmes variés qui occupent encore les mathématiciens, en combinatoire, géométrie ou recherche opérationnelle. L'essor des fractales chères à Benoît Mandelbrot permet aussi à tout un chacun d'expérimenter aujourd'hui ce puissant concept d'une fonction qui s'appelle elle-même.
Tutti gli articoli di questo dossier
La dimostrazione di un programma | Tangente
Scrivere un programma informatico è una cosa. Dimostrare che conduce davvero al risultato atteso è un’altra! Uno dei grandi vantaggi della ricorsività è che permette di produrre programmi dei quali è facile dimostrare che forniscono effettivamente i risultati attesi. Esiste infatti un legame tra la scrittura e la dimostrazione di un programma.
I frattali, l’estetica dell’iterazione
Considerare una trasformazione geometrica e ripeterla a scale diverse permette di costruire figure affascinanti, il cui aspetto estetico è ben lungi dall’essere l’unico motivo di interesse. (Ri)scopriamo insieme i frattali più emblematici!
La ricchissima successione di Prouhet-Thue-Morse
La parola di Morse, o successione di Prouhet-Thue-Morse, è un oggetto matematico facile da costruire e che racchiude molti tesori. Partiamo insieme alla scoperta di una successione combinatoria che meriterebbe una fama pari a quella di Fibonacci!
Le sfide della geometria algoritmica | Tangente
Non ci si pensa sempre, ma molti problemi di natura geometrica possono essere risolti mediante procedimenti iterativi o, più in generale, algoritmi. Lo studio di queste questioni costituisce la geometria algoritmica! È un campo vivace e molto attivo, in cui molte questioni dall’apparenza elementare attendono ancora una soluzione.
Le frazioni continue,
È possibile scrivere i numeri reali indipendentemente dalla scelta arbitraria di una base. L’algoritmo di Euclide fornisce un metodo che si estende a tutti i reali e conduce alla nozione di frazione continua. Con questo formalismo, il numero d’oro diventa l’irrazionale più semplice da scrivere!
Cicli nella programmazione | Tangente
I diversi tipi di ciclo sono strutture informatiche fondamentali. Sebbene il loro impiego sia spesso naturale, pone comunque alcuni problemi, come stabilire se il programma prima o poi si arresterà. La ricorsione offre risposte pertinenti.