|
Récursivité Comme les boucles d'oreilles de la
Vache qui rit ou encore les fractales et leur autosimilarité, la récursivité
est une invention diabolique qui se renvoie à elle-même. Certains langages de programmation
sont bien connus pour posséder ces propriétés: LISP ou PROLOG. Mais, il est
possible d'implémenter des procédures récursives avec tout langage de
programmation. Exemple de définition récursive (qui utilise sa propre définition pour se définir) Un nombre est polydivisible
s'il est divisible par sa quantité de chiffres et si ce nombre tronqué de son
unité est aussi polydivisible. >>> |
Récursif
Récurrent: qui se répète, qui revient
régulièrement Du
latin recurrens: revenant rapidement en arrière; de recurro: revenir en
courant. Maths:
suite ou série
récurrente: chaque terme s’exprime à partir du terme qui le précède. Un
= Un – 1 + Un – 2. Suite récurrente de Fibonacci. Récursif: qui se définit en s’utilisant soi-même,
directement ou indirectement. On peut définir la fonction factorielle de manière
récursive: n! = (n – 1)! x n Naturam
expellas furca, tamen usque recurret:
tu peux chasser le naturel à coups de fourche, il reviendra toujours au
galop. |
|
||
|
|
|
Magie pour atteindre une démonstration sans
explorer tous les cas |
Magie pour atteindre un
résultat, sans détailler toutes les étapes de calcul |
|
Exemple avec la somme des entiers jusqu'à
n: Je sais que si Sn = ½ n
(n + 1) alors Sn+1 = ½ (n+1) (n + 2) et que cette formule est
vraie pour n = 2 (en effet: ½ x2 x 3 = 3 et S est bien égal à 1 + 2 = 3. |
Exemple avec le tracé du cercle Procédure cercle: avancer d'un pas et
tourner à gauche d'un cran. Programme cercle: Procédure cercle tant que le point
courant est différent du point de départ. |
|
|
||
Méthode itérative (classique)
|
|
|
Méthode récursive
|
|
|
Voir Programmation de la fonction
factorielle (explications détaillées: algorithme, Maple et Scheme)
|
||||
|
Exemple Maple
|
|||
Méthode itérative (classique)
|
|
|||
Astuce! Pour s'en sortir
facilement avec le test des différences, on va utiliser la formation d'un ensemble {…}, lequel ne tolère pas les redondances.
Ce qui veut dire que si l'ensemble comporte moins d'éléments que la
collection originales, c'est qu'il y a redondance d'éléments. |
|
|||
Méthode récursive Voir Algorithme de permutation
|
etc. |
|||
Programme pour six nombres permutés.
|
|
|
||
Voir Instruction
seq / Premiers permutables
/ Programmation
– Index
Retour |
|
Suite |
|
Voir |
|
Site |
|
Cette page |