Qu’est-ce que la récursivité ?
Le processus dans lequel une fonction s'appelle directement ou indirectement est appelé récursion et la fonction correspondante est appelée fonction récursive. Grâce à un algorithme récursif, certains problèmes peuvent être résolus assez facilement. Des exemples de tels problèmes sont Tours de Hanoï (TOH) , Traversées de l'arbre de commande/précommande/postcommande , DFS de Graph , etc. Une fonction récursive résout un problème particulier en appelant une copie d'elle-même et en résolvant des sous-problèmes plus petits des problèmes d'origine. De nombreux appels récursifs peuvent être générés selon les besoins. Il est essentiel de savoir que nous devons fournir un certain cas afin de mettre fin à ce processus de récursion. On peut donc dire qu'à chaque fois la fonction s'appelle avec une version plus simple du problème d'origine.

Besoin de récursion

La récursivité est une technique étonnante à l'aide de laquelle nous pouvons réduire la longueur de notre code et le rendre plus facile à lire et à écrire. Elle présente certains avantages par rapport à la technique d’itération qui seront discutés plus loin. Tâche qui peut être définie avec sa sous-tâche similaire, la récursivité est l'une des meilleures solutions pour cela. Par exemple; La Factorielle d'un nombre.

Propriétés de la récursivité :

• Effectuer les mêmes opérations plusieurs fois avec des entrées différentes.
• À chaque étape, nous essayons des entrées plus petites pour réduire le problème.
• Une condition de base est nécessaire pour arrêter la récursion, sinon une boucle infinie se produira.

Algorithme : étapes

The algorithmic steps for implementing recursion in a function are as follows: Step1 - Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself. Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.>

Une interprétation mathématique

Considérons un problème qu'un programmeur doit déterminer la somme des n premiers nombres naturels, il existe plusieurs façons de le faire, mais l'approche la plus simple consiste simplement à additionner les nombres commençant de 1 à n. La fonction ressemble donc simplement à ceci :

approche(1) – En ajoutant simplement un par un

f(n) = 1 + 2 + 3 +……..+n

mais il existe une autre approche mathématique pour représenter cela,

approche (2) – Ajout récursif

f(n) = 1 n=1

f(n) = n + f(n-1) n>1

Il y a une simple différence entre l'approche (1) et l'approche (2) et c'est dans approche(2) la fonction F( ) lui-même est appelé à l'intérieur de la fonction, donc ce phénomène est appelé récursion, et la fonction contenant la récursion est appelée fonction récursive, à la fin, c'est un excellent outil entre les mains des programmeurs pour coder certains problèmes de manière beaucoup plus simple et efficace. chemin.

Comment les fonctions récursives sont-elles stockées en mémoire ?

La récursion utilise plus de mémoire, car la fonction récursive s'ajoute à la pile à chaque appel récursif et y conserve les valeurs jusqu'à la fin de l'appel. La fonction récursive utilise la structure LIFO (LAST IN FIRST OUT) tout comme la structure de données de pile. structure-de-données-de-pile/

Quelle est la condition de base en récursivité ?
Dans le programme récursif, la solution au cas de base est fournie et la solution au problème plus important est exprimée en termes de problèmes plus petits.

int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }>

Dans l'exemple ci-dessus, le cas de base pour n <= 1 est défini et la valeur la plus grande d'un nombre peut être résolue en la convertissant en une valeur plus petite jusqu'à ce que le cas de base soit atteint.

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 problèmes plus petits, 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 la factorielle serait n = 0. Nous renvoyons 1 lorsque n = 0.

Pourquoi une erreur Stack Overflow se produit en récursion ?
Si le cas de base n’est pas atteint ou n’est pas défini, un problème de débordement de pile peut survenir. Prenons un exemple pour comprendre cela.

int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); }>

Si fact(10) est appelé, il appellera fact(9), fact(8), fact(7), etc. mais le nombre n'atteindra jamais 100. Ainsi, le cas de base n'est 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 la récursivité directe et indirecte ?
Une fonction fun est dite récursive directe si elle appelle la même fonction fun. Une fonction fun est appelée récursive indirecte si elle appelle une autre fonction, par exemple fun_new, et fun_new appelle fun directement ou indirectement. La différence entre la récursivité directe et indirecte a été illustrée dans le tableau 1.

 // An example of direct recursion void directRecFun() { // Some code.... directRecFun(); // Some code... } // An example of indirect recursion void indirectRecFun1() { // Some code... indirectRecFun2(); // Some code... } void indirectRecFun2() { // Some code... indirectRecFun1(); // Some code... }>

Quelle est la différence entre la récursivité avec et sans queue ?
Une fonction récursive est récursive lorsqu'un appel récursif est la dernière chose exécutée par la fonction. Se il vous plaît se référer article sur la récursion de la queue pour plus de détails.

Comment la mémoire est allouée aux différents appels de fonction en récursion ?
Lorsqu'une fonction est appelée depuis main(), 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 et la mémoire est désallouée et le processus continue.
Prenons l'exemple du fonctionnement de la récursivité en prenant une fonction simple.

RPC

>

>

Java

films123 à

>

>

Python3

>

>

C#

>

>

PHP

>

>

Javascript

>

>

3 2 1 1 2 3>

Complexité temporelle : O(1)
Espace auxiliaire : O(1)

Quand printFun(3) est appelé depuis main(), la mémoire est allouée à printFun(3) et un test de variable locale est initialisé à 3 et les instructions 1 à 4 sont poussées sur la pile comme indiqué dans le diagramme ci-dessous. Il imprime d’abord « 3 ». Dans la déclaration 2, printFun(2) est appelé et la mémoire est allouée à printFun(2) et une variable locale test est initialisée à 2 et les instructions 1 à 4 sont poussées dans la pile. De la même manière, printFun(2) appels printFun(1) et printFun(1) appels printFun(0) . printFun(0) va à l'instruction if et elle revient à printFun(1) . Les autres déclarations de printFun(1) sont exécutés et il revient à printFun(2) et ainsi de suite. Dans la sortie, les valeurs de 3 à 1 sont imprimées, puis 1 à 3 sont imprimées. La pile mémoire a été représentée dans le diagramme ci-dessous.

Récursivité VS Itération

Discutons maintenant de quelques problèmes pratiques qui peuvent être résolus en utilisant la récursivité et comprenons son fonctionnement de base. Pour une compréhension de base, veuillez lire les articles suivants.
Compréhension de base de la récursivité.
Problème 1 : Écrivez un programme et une relation de récurrence pour trouver la série de Fibonacci de n où n>2 .
Équation mathématique :

n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>

Relation réccurente:

T(n) = T(n-1) + T(n-2) + O(1)>

Programme récursif :

 Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>

Mise en œuvre:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

Unité arithmétique et logique

>

>

Javascript

>

>

Fibonacci series of 5 numbers is: 0 1 1 2 3>

Complexité temporelle : O(2ⁿ)
Espace auxiliaire : Sur)

Voici l'arbre récursif pour l'entrée 5 qui montre une image claire de la façon dont un gros problème peut être résolu en de plus petits.
fib(n) est une fonction de Fibonacci. La complexité temporelle du programme donné peut dépendre de l'appel de fonction.

fib(n) -> niveau CBT (UB) -> 2^n-1 nœuds -> 2^n appel de fonction -> 2^n*O(1) -> T(n) = O(2^n)

Pour le meilleur des cas.

T(n) = ?(2^n2)>

Fonctionnement:

Problème 2 : Écrivez un programme et une relation de récurrence pour trouver la factorielle de n où n>2 .
Équation mathématique :

1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>

Relation réccurente:

T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>

Programme récursif :
Saisir: n = 5
Sortir:
la factorielle de 5 est : 120
Mise en œuvre:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

liste java

>

Javascript

>

>

factorial of 5 is: 120>

Complexité temporelle : Sur)
Espace auxiliaire : Sur)

Fonctionnement:

Diagramme de la fonction de récursion factorielle pour la saisie utilisateur 5.

Exemple : applications réelles de la récursivité dans des problèmes réels

La récursion est une technique puissante qui a de nombreuses applications en informatique et en programmation. Voici quelques-unes des applications courantes de la récursivité :

Parcours d'arbres et de graphiques : la récursivité est fréquemment utilisée pour parcourir et rechercher des structures de données telles que des arbres et des graphiques. Les algorithmes récursifs peuvent être utilisés pour explorer tous les nœuds ou sommets d'un arbre ou d'un graphe de manière systématique. Algorithmes de tri : les algorithmes récursifs sont également utilisés dans les algorithmes de tri tels que le tri rapide et le tri par fusion. Ces algorithmes utilisent la récursion pour diviser les données en sous-tableaux ou sous-listes plus petits, les trier, puis les fusionner. Algorithmes diviser pour régner : de nombreux algorithmes qui utilisent une approche diviser pour régner, tels que l'algorithme de recherche binaire, utilisent la récursivité pour décomposer le problème en sous-problèmes plus petits. Génération fractale : des formes et des motifs fractaux peuvent être générés à l'aide d'algorithmes récursifs. Par exemple, l’ensemble de Mandelbrot est généré en appliquant de manière répétée une formule récursive à des nombres complexes. Algorithmes de backtracking : Les algorithmes de backtracking sont utilisés pour résoudre des problèmes qui impliquent de prendre une séquence de décisions, où chaque décision dépend des précédentes. Ces algorithmes peuvent être implémentés en utilisant la récursion pour explorer tous les chemins possibles et revenir en arrière lorsqu'une solution n'est pas trouvée. Mémoisation : la mémorisation est une technique qui consiste à stocker les résultats d'appels de fonctions coûteux et à renvoyer le résultat mis en cache lorsque les mêmes entrées se reproduisent. La mémorisation peut être implémentée à l'aide de fonctions récursives pour calculer et mettre en cache les résultats des sous-problèmes.

Ce ne sont là que quelques exemples des nombreuses applications de la récursivité en informatique et en programmation. La récursivité est un outil polyvalent et puissant qui peut être utilisé pour résoudre de nombreux types de problèmes différents.

Explication : un exemple réel de récursion :

La récursivité est une technique de programmation qui implique qu'une fonction s'appelle elle-même. Il peut s’agir d’un outil puissant pour résoudre des problèmes complexes, mais il nécessite également une mise en œuvre minutieuse pour éviter les boucles infinies et les débordements de pile.

Voici un exemple d’implémentation de la récursivité en Python :

C++

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

120>

Dans cet exemple, nous définissons une fonction appelée factorielle qui prend un entier n en entrée. La fonction utilise la récursion pour calculer la factorielle de n (c'est-à-dire le produit de tous les entiers positifs jusqu'à n).

La fonction factorielle vérifie d'abord si n est 0 ou 1, qui sont les cas de base. Si n vaut 0 ou 1, la fonction renvoie 1, puisque 0 ! et 1! sont tous deux 1.

Si n est supérieur à 1, la fonction entre dans le cas récursif. Il s'appelle avec n-1 comme argument et multiplie le résultat par n. Cela calcule n ! en calculant récursivement (n-1) !.

Il est important de noter que la récursivité peut être inefficace et entraîner des débordements de pile si elle n’est pas utilisée avec précaution. Chaque appel de fonction ajoute une nouvelle trame à la pile d'appels, ce qui peut rendre la pile trop grande si la récursion est trop profonde. De plus, la récursivité peut rendre le code plus difficile à comprendre et à déboguer, car elle nécessite de réfléchir à plusieurs niveaux d'appels de fonction.

Cependant, la récursivité peut également être un outil puissant pour résoudre des problèmes complexes, en particulier ceux qui impliquent de décomposer un problème en sous-problèmes plus petits. Lorsqu'elle est utilisée correctement, la récursivité peut rendre le code plus élégant et plus facile à lire.

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 pouvoirs de résolution de problèmes, c'est-à-dire que chaque programme récursif peut être écrit de manière itérative et vice versa, c'est également vrai. Le programme récursif nécessite plus d'espace que le programme itératif car toutes les fonctions resteront dans la pile jusqu'à ce que le cas de base soit atteint. Il nécessite également plus de temps en raison des appels de fonctions et des frais généraux renvoyés.

De plus, en raison de la longueur réduite du code, les codes sont difficiles à comprendre et il faut donc faire preuve d'une plus grande prudence lors de l'écriture du code. L'ordinateur peut manquer de mémoire si les appels récursifs ne sont pas correctement vérifiés.

Quels sont les avantages de la programmation récursive par rapport à la programmation itérative ?
La récursion fournit un moyen propre et simple d'écrire du code. Certains problèmes sont intrinsèquement récursifs comme les traversées 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 de tels codes de manière itérative à l’aide d’une structure de données de pile. Par exemple, reportez-vous à Inorder Tree Traversal without Recursion, Iterative Tower of Hanoi.

tableau de retour Java

Résumé de la récursion :

• Il existe deux types de cas en récursivité, à savoir le cas récursif et un cas de base.
• Le cas de base est utilisé pour terminer la fonction récursive lorsque le cas s'avère vrai.
• Chaque appel récursif crée une nouvelle copie de cette méthode dans la mémoire de la pile.
• Une récursivité infinie peut entraîner un manque de mémoire de pile.
• Exemples d'algorithmes récursifs : tri par fusion, tri rapide, tour de Hanoï, série de Fibonacci, problème factoriel, etc.

Problèmes pratiques basés sur les résultats pour les débutants :
Questions pratiques pour la récursivité | Ensemble 1
Questions pratiques pour la récursivité | Ensemble 2
Questions pratiques pour la récursivité | Ensemble 3
Questions pratiques pour la récursivité | Ensemble 4
Questions pratiques pour la récursivité | Ensemble 5
Questions pratiques pour la récursivité | Ensemble 6
Questions pratiques pour la récursivité | Ensemble 7
Quiz sur la récursion
Pratique de codage sur la récursion :
Tous les articles sur la récursivité
Problèmes de pratique récursive avec solutions