La récursivité expliquée avec une image GIF – 6/6

Un programme est dit récursif lorsqu’une entité s’appelle elle-même. Un programme est appelé itératif lorsqu’il y a une boucle (ou répétition).

Une figure fractale ou fractale est une courbe ou surface de forme irrégulière ou morcelée qui se crée en suivant des règles déterministes ou stochastiques impliquant une homothétie interne. Le terme « fractale » est un néologisme créé par Benoît Mandelbrot en 1974 à partir de la racine latine fractus, qui signifie brisé, irrégulier .

Un des plus beaux exemples de fractale donné par la nature est le chou Romanesco.

Les fractales sont très utilisées pour générer des paysages virtuels.

Exemple : Un arbre

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.

La récursivité expliquée avec une image GIF – 5/6

Un programme est dit récursif lorsqu’une entité s’appelle elle-même. Un programme est appelé itératif lorsqu’il y a une boucle (ou répétition).

Exemple : Programme triangle de Pascal

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.

La récursivité expliquée avec une image GIF – 4/6

Un programme est dit récursif lorsqu’une entité s’appelle elle-même. Un programme est appelé itératif lorsqu’il y a une boucle (ou répétition).

Exemple : la suite de Fibonacci

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.

La récursivité expliquée avec une image GIF – 3/6

Un programme est dit récursif lorsqu’une entité s’appelle elle-même. Un programme est appelé itératif lorsqu’il y a une boucle (ou répétition).

Exemple : Programme pour trouver la factorielle d’un nombre

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.

La récursivité expliquée avec une image GIF – 2/6

En mathématiques, en informatique, en biologie, mais aussi dans notre quotidien, nous faisons souvent face à des situations où un problème doit être résolu en utilisant une méthode de résolution qui est répétée plusieurs fois. Dans l’itération, cette méthode est appliquée par paliers de façon séquentielle, dans la récursivité, la méthode s’appelle elle-même.
La récursivité est un principe de pensée exigeant et est souvent désigné comme « trop compliqué ». La récursivité est cependant si fondamentale qu’il n’est pas possible de l’éviter.

L’image GIF ci-dessus illustre le principe de base de la récursivité.

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.

La récursivité expliquée avec une image GIF – 1/6

En mathématiques, en informatique, en biologie, mais aussi dans notre quotidien, nous faisons souvent face à des situations où un problème doit être résolu en utilisant une méthode de résolution qui est répétée plusieurs fois. Dans l’itération, cette méthode est appliquée par paliers de façon séquentielle, dans la récursivité, la méthode s’appelle elle-même.
La récursivité est un principe de pensée exigeant et est souvent désigné comme « trop
compliqué ». La récursivité est cependant si fondamentale qu’il n’est pas possible de l’éviter.

L’image GIF ci-dessus illustre le principe de base de la récursivité.

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.

Différence entre récursion et itération

Un programme est dit récursif lorsqu’une entité s’appelle elle-même. Un programme est appelé itératif lorsqu’il y a une boucle (ou répétition).

Exemple : Programme pour trouver la factorielle d’un nombre

Vous trouverez ci-dessous des explications détaillées pour illustrer la différence entre les deux :

1 – Complexité du temps : Trouver la complexité temporelle de la récursion est plus difficile que celle de l’itération.

  • Récursion : La complexité temporelle de la récursivité peut être trouvée en trouvant la valeur du n-ième appel récursif par rapport aux appels précédents. Ainsi, trouver le cas de destination en termes de cas de base, et le résoudre en termes de cas de base nous donne une idée de la complexité temporelle des équations récursives.
  • Itération : La complexité temporelle de l’itération peut être trouvée en trouvant le nombre de cycles qui se répètent à l’intérieur de la boucle.

2 – Utilisation : L’utilisation de l’une ou l’autre de ces techniques est un compromis entre la complexité temporelle et la taille du code. Si la complexité temporelle est le point central, et que le nombre d’appels récursifs est important, il est préférable d’utiliser l’itération. Cependant, si la complexité temporelle n’est pas un problème et que la taille du code l’est, la récursivité serait la solution.

  • Récursion : La récursivité consiste à appeler la même fonction à nouveau, et donc, a une très petite longueur de code. Cependant, comme nous l’avons vu dans l’analyse, la complexité temporelle de la récursion peut devenir exponentielle lorsqu’il y a un nombre considérable d’appels récursifs. Par conséquent, l’utilisation de la récursion est avantageuse dans le cas d’un code plus court, mais d’une complexité temporelle plus élevée.
    Itération : L’itération est la répétition d’un bloc de code. Cela implique une plus grande taille de code, mais la complexité temporelle est généralement moindre que pour la récursivité.

3 – Répétition infinie : La répétition infinie en récursion peut entraîner un crash du processeur mais en itération, elle s’arrête lorsque la mémoire est épuisée.

  • Récursion : Dans la récursion, des appels récursifs infinis peuvent se produire en raison d’une erreur de spécification de la condition de base, qui, ne devenant jamais fausse, continue d’appeler la fonction, ce qui peut entraîner un crash du CPU du système.
  • Itération : L’itération infinie due à une erreur dans l’affectation ou l’incrémentation de l’itérateur, ou dans la condition de fin, conduira à des boucles infinies, qui peuvent ou non conduire à des erreurs système, mais arrêteront sûrement l’exécution du programme plus loin.
PROPRIÉTÉ RÉCURSION ITÉRATION
Définition La fonction s’appelle elle-même. Un ensemble d’instructions exécutées de manière répétitive.
Application Pour les fonctions. Pour les boucles.
Terminaison Par le cas de base, où il n’y aura pas d’appel de fonction. Lorsque la condition de sortie de l’itérateur cesse d’être remplie.
Utilisation Utilisé lorsque la taille du code doit être petite et que la complexité du temps ne pose pas de problème. Utilisé lorsque la complexité temporelle doit être compensée par une taille de code plus importante.
Taille du code Taille du code plus petite Taille du code plus grande.
Complexité temporelle Très grande (généralement exponentielle) complexité temporelle. Complexité temporelle relativement plus faible (généralement polynomiale et logarithmique).

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.