la récursivité est le processus de définition d’un problème (ou la solution à un problème) en termes de (une version plus simple de) lui-même.

Par exemple, nous pouvons définir l’opération « trouver votre chemin de la maison »:

  1. Si vous êtes à la maison, arrêtez de bouger.

  2. Prendre une étape vers la maison.

  3. « trouver votre chemin de la maison ».

ici, la solution pour trouver votre chemin du retour est en deux étapes (trois étapes). Premièrement, nous ne rentrons pas chez nous 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, nous refaire l’ensemble de l’algorithme.

l’exemple ci-dessus est appelé récursion de queue. C’est là que la toute dernière instruction appelle l’algorithme récursif. La récursivité de la queue peut directement être traduite en boucles.

comment écririez-vous un « algorithme » récursif pour trouver Temple Square?

un Autre exemple de récursivité serait de trouver la valeur maximale d’une liste de nombres. La valeur maximale dans une liste est le premier nombre ou le plus grand des nombres restants., Voici comment écrire le pseudocode de l’algorithme:

parties d’un algorithme récursif

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

  1. cas de Base (c’est-à-dire quand arrêter)

  2. travailler vers le cas de Base

  3. appel récursif (c’est-à-dire

    le « travail vers le cas de base » est l’endroit où nous simplifions le problème (par exemple, diviser la liste en deux parties, chacune plus petite que l’original). L’appel récursif, c’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 n’avait qu’un seul numéro… et par définition s’il n’y a qu’un seul nombre, c’est le plus grand).

    exemple Simple: ajouter trois nombres

    ajouter trois nombres équivaut à ajouter les deux premiers nombres, puis à ajouter à nouveau ces deux nombres.

    (remarque, dans Matlab, une fonction peut être appelée sans tous les arguments. La fonction nargin indique à l’ordinateur combien de valeurs ont été spécifiées., Ainsi add_numbers(1) aurait un nargin de 1; add_numbers(1,1) aurait un nargin de 2; add_numbers(1,1,1) aurait un nargin de 3.)

    Identifier les 3 parties de l’algorithme récursif:

    Tous algorithme récursif doit avoir les trois étapes suivantes:

    Pourquoi la Récursivité Fonctionne

    Dans un algorithme récursif, l’ordinateur se « souvient » de chaque état précédent du problème. Ces informations sont  » conservées « par l’ordinateur sur la » pile d’activation  » (c’est-à-dire à l’intérieur de chaque espace de travail functions).

    chaque fonction a son propre espace de travail par appel de la fonction.,

    exemple de labyrinthe:

    considérons une grille rectangulaire de pièces, où chaque pièce peut ou non avoir des portes sur les côtés Nord, Sud, Est et Ouest.

    Comment trouvez-vous votre chemin hors d’un labyrinthe? Voici un « algorithme » possible pour trouver la réponse:

    pour chaque porte de la pièce actuelle, si la porte mène à la sortie, prenez cette porte.

    Le « truc » ici est bien sûr, comment savons-nous si la porte mène à une salle qui mène à la sortie? La réponse est que nous ne le faisons pas, mais nous pouvons laisser l’ordinateur le comprendre pour nous.

    quelle est la partie récursive de l’algorithme ci-dessus?, C’est la « porte mène hors du labyrinthe ». Comment savons-nous si une porte mène hors du labyrinthe? Nous le savons parce qu’à l’intérieur de la pièce voisine (en passant par la porte), nous posons la même question, Comment sortir du labyrinthe?

    ce qui se passe, c’est que l’ordinateur « se souvient » de tous les « Quoi I ». Ce que si je prends la première porte, ce que si je prends la deuxième porte, ce que si je prends la porte suivante, etc. Et pour chaque porte possible que vous pouvez traverser, l’ordinateur se souvient de ceux que I, et pour chaque porte après cela, et après cela, etc., jusqu’à ce que la fin soit trouvée.

    Voici une implémentation de code proche de la réalité.,

    Question: Quel est le cas de base ci-dessus?

    réponse: (c’était une question piège) il n’y a pas de cas de base dans le code. Vous devez vérifier au début de la pièce est la sortie. Si elle l’est, pas de récursivité! 

      function success = find_way_out( maze, room ) if room is exit → return true room ← mark as visited % rest of code ... end

    Question: Comment marquez-vous la pièce comme visitée?

    Réponse: Il existe différentes techniques. Si la pièce est une structure (ou un objet), vous pouvez ajouter la direction du champ visité à la pièce. (par exemple, salle de.visited = true;) si vous n’utilisez pas d’objets, vous pouvez avoir une matrice de drapeaux booléens qui est la même taille/forme que le labyrinthe et utiliser ces valeurs.,

    Question: les autres problèmes avec l’algorithme ci-dessus?

    réponse: la réponse à cela peut être trouvée en pensant à la question suivante: Que se passerait-il si le labyrinthe était une grille géante de pièces rectangulaires de taille identique, chacune avec des portes sur chaque mur? Imaginez que vous allez au nord par la première porte, puis à l’est par la porte des chambres suivantes, puis au sud par cette porte des chambres, puis à l’ouest par cette porte des chambres. Où voulez-vous vous retrouver? De retour où vous avez commencé! Pire, vous pourriez continuer à faire cette boucle pour toujours. Comment un aventurier intrépide résoudrait-il ce problème?,

    une réponse à cela est d’utiliser un morceau de craie et de mettre un grand X sur le sol de chaque pièce dans laquelle vous entrez. Ainsi, lorsque vous revenez dans une pièce avec un X sur le sol, vous savez que vous n’avez pas besoin d’entrer. Dans le cas du programme, un indicateur booléen « vu » ou « visité » doit être utilisé. Chaque chambre a un drapeau. Chaque pièce commence par le drapeau étant mis à false. Lorsque vous visitez une pièce, vous définissez le drapeau sur true., Enfin, dans le » cas de base », vous avez une ligne telle que: 

      function success = find_way_out( maze, room ) % exit chack if room is visited → return false % rest of code ... end

    la récursivité peut également être appliquée à des algorithmes informatiques:

    certains exemples liés à L’ordinateur incluent: ajout d’une liste de nombres, calcul de la séquence de Fibonacci, calcul D’une factorielle et Sudoku.

    boucles et récursivité de queue

    certains algorithmes récursifs sont très similaires aux boucles. Ces algorithmes sont appelés « queue récursive » parce que la dernière déclaration de l’algorithme est de « relancer » l’algorithme. Les algorithmes récursifs de queue peuvent être directement traduits en boucles.