Initiation à l'algorithmique

Qu'est-ce que la récursivité

Introduction

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 nous-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).

Comment un problème particulier est-il résolu en utilisant la récursivité?

L'idée est de représenter un problème en termes d'un ou plusieurs petits problèmes, et d'ajouter une ou plusieurs conditions de base qui arrêtent la récursion.
Par exemple, nous calculons la factorielle n si nous connaissons la factorielle de (n-1). Le cas de base pour factorielle serait n = 0. Nous retournons 1 lorsque n = 0.

Pourquoi une erreur de débordement de pile se produit-elle en récursivité?

Si le cas de base n'est pas atteint ou n'est pas défini, le problème de débordement de pile peut survenir. Prenons un exemple pour comprendre cela.

    fonction factorielle(n)
        SI n==50 ALORS
            retourner 1
        SINON
            retourner n*factorielle(n-1)
    
    factoriel(30)

Si factorielle(30) est appelée, elle appellera factorielle(29), factorielle(28), factorielle(27), etc., mais le nombre n'atteindra jamais 30.
Le cas de base n'est donc pas atteint. Si la mémoire est épuisée par ces fonctions sur la pile, cela provoquera une erreur de débordement de pile.

Quelle est la différence entre une récursion directe et indirecte?

Une fonction fct est de récursive directe si elle appelle la même fonction fct.
Une fonction fct est de récursive indirecte si elle appelle une autre fonction, par exemple fct_new et fct_new appelle fct directement ou indirectement.

    fonction fct()
        fct_new()
    
    fonction fct_nex()
        fct()

Comment la mémoire est allouée à différents appels de fonction lors de la récursivité?

Lorsqu'une fonction est appelée, la mémoire lui est allouée sur la pile.
Une fonction récursive s’appelle elle-même, la mémoire d’une fonction appelée est allouée en plus de la mémoire allouée à la fonction appelante et une copie différente des variables locales est créée pour chaque appel de fonction.
Lorsque le cas de base est atteint, la fonction renvoie sa valeur à la fonction par laquelle elle est appelée, la mémoire est désallouée et le processus continue.

Prenons un exemple simple pour bien comprendre le fonctionnement de la récursivité.

            fonction factorielle(n)
                SI n=1 ALORS
                    retourner 1
                SINON
                    Ecrire(fact)
                    fact=n*factorielle(n-1)
                    retourner fact
            
                def factorielle(n):
                    if n == 1:
                        return 1
                    else:
                        print(n)
                        fact = n * factorielle(n-1)
                        print(fact)
                        return fact
                
                factorielle(3)
            

lorsque factorielle(3) est appelée, la mémoire est allouée à factorielle(3), la variable locale n est initialisée à 3 et les instruction de 1 à 4 est placées dans la pile.
comme indiqué dans le diagramme ci-dessous, donc premièrement la fonction affiche 3 et appelle factorielle(2), factorielle (2) affiche 2 et appelle factorielle(1). factorielle(1) retourne 1 à factorielle(2), les instruction restantes de factorielle(2) est exécutées (calculer fact=2*1, afficher 2) puis retourne 2 à factorielle(3), les instruction restantes de factorielle(3) est exécutées (calculer fact=3*2; afficher 6 et retourner la valeur finale 6 à l'utilisateur)
à la fin la pile est désallouée

Quels sont les inconvénients de la programmation récursive par rapport à la programmation itérative?

Notez que les programmes récursifs et itératifs ont les mêmes capacités de résolution de problèmes, c’est-à-dire que tous les programmes récursifs peuvent être écrits de manière itérative et vice versa.
Le programme récursif a besoin plus d'espace qu'un programme itératif, car toutes les fonctions resteront dans la pile jusqu'à ce que le cas de base soit atteint. En outre, le temps requis est plus long en raison d'appels de fonction.

Quels sont les avantages de la programmation récursive par rapport à la programmation itérative?

La récursivité fournit un moyen simple et propre d’écrire du code. Certains problèmes sont intrinsèquement récursifs, tels que les parcours d'arbres, la tour de Hanoi, etc. Pour de tels problèmes, il est préférable d'écrire du code récursif. Nous pouvons également écrire ces codes de manière itérative à l'aide de pile.

Partager ce cours avec tes amis :
Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :