MPSI, PCSI et la PTSI

Appelez-nous au numéro (+212) 616 374 790 ou écrivez-nous à essaddouki@gmail.com

Demander le soutien en ligne de l'un de nos professeurs, à toute heure et où vous voulez, de 8h à minuit (GMT) Détails

Récursivité, cours et problèmes corrigés

Le processus dans lequel une fonction appelle elle-même directement ou indirectement est appelée récursion et la fonction correspondante est appelée une fonction récursive.
En utilisant un algorithme récursif, certains problèmes peuvent être résolus assez facilement. Tours de Hanoi (TOH), traversées d’arbres en ordre / en pré-ordre / post-ordre, DFS du graphe, etc. sont des exemples de ces problèmes.

Par exemple, nous pouvons définir l'opération "trouver le chemin du retour" comme suit:

  1. Si vous êtes à la maison, arrêtez de bouger.
  2. Faites un pas.
  3. "trouve ton chemin à la maison".

Ici, la solution pour trouver votre chemin de retour est de deux étapes (en faite trois étapes). D'abord, nous ne rentrons pas à la maison si nous sommes déjà à la maison. Deuxièmement, nous faisons une action très simple qui rend notre situation plus simple à résoudre. Enfin, refaire l'ensemble de l'algorithme.

Parties d'un algorithme récursif

Tous les algorithmes récursifs doivent avoir les éléments suivants:

  1. Scénario de référence ou de base (c.-à-d. quand arrêter)
  2. Travailler vers le cas de base
  3. Appel récursif (c'est-à-dire appeler lui-mêmes)

Le "Travailler vers le cas de base" consiste à simplifier le problème (par exemple, diviser la liste en deux parties, chacune plus petite que l'originale).
L'appel récursif est l'endroit où nous utilisons le même algorithme pour résoudre une version plus simple du problème.
Le cas de base est la solution au problème "le plus simple" possible (par exemple, le cas de base du problème 'trouver le plus grand nombre dans une liste' serait si la liste ne comportait qu'un seul numéro ... et par définition s'il y avait un seul nombre, c'est le plus grand).

Sommaire

Partager cette formation avec tes amis :