La récursivité est un concept fondamental en informatique et en mathématiques qui permet aux fonctions de s'appeler elles-mêmes, permettant ainsi de résoudre des problèmes complexes par des étapes itératives. Une représentation visuelle couramment utilisée pour comprendre et analyser l’exécution de fonctions récursives est un arbre de récursivité. Dans cet article, nous explorerons la théorie derrière les arbres de récursivité, leur structure et leur importance dans la compréhension des algorithmes récursifs.
Qu’est-ce qu’un arbre de récursion ?
Un arbre de récursion est une représentation graphique qui illustre le flux d'exécution d'une fonction récursive. Il fournit une ventilation visuelle des appels récursifs, montrant la progression de l'algorithme à mesure qu'il se ramifie et atteint finalement un cas de base. La structure arborescente aide à analyser la complexité temporelle et à comprendre le processus récursif impliqué.
Structure arborescente
Chaque nœud d'un arbre de récursion représente un appel récursif particulier. L'appel initial est représenté en haut, les appels suivants se ramifiant en dessous. L'arbre pousse vers le bas, formant une structure hiérarchique. Le facteur de branchement de chaque nœud dépend du nombre d'appels récursifs effectués au sein de la fonction. De plus, la profondeur de l'arborescence correspond au nombre d'appels récursifs avant d'atteindre le cas de base.
Cas de base
Le cas de base sert de condition de terminaison pour une fonction récursive. Il définit le point auquel la récursion s'arrête et la fonction commence à renvoyer des valeurs. Dans un arbre de récursivité, les nœuds représentant le cas de base sont généralement représentés comme des nœuds feuilles, car ils n'entraînent pas d'autres appels récursifs.
mon livecricket dans
Appels récursifs
Les nœuds enfants dans un arbre de récursion représentent les appels récursifs effectués au sein de la fonction. Chaque nœud enfant correspond à un appel récursif distinct, entraînant la création de nouveaux sous-problèmes. Les valeurs ou paramètres transmis à ces appels récursifs peuvent différer, entraînant des variations dans les caractéristiques des sous-problèmes.
Flux d'exécution :
La traversée d'un arbre de récursion fournit un aperçu du flux d'exécution d'une fonction récursive. À partir de l'appel initial au nœud racine, nous suivons les branches pour atteindre les appels suivants jusqu'à ce que nous rencontrions le cas de base. Au fur et à mesure que les cas de base sont atteints, les appels récursifs commencent à revenir et leurs nœuds respectifs dans l'arborescence sont marqués avec les valeurs renvoyées. Le parcours se poursuit jusqu'à ce que l'arbre entier ait été parcouru.
Analyse de la complexité temporelle
Les arbres de récursivité aident à analyser la complexité temporelle des algorithmes récursifs. En examinant la structure de l'arborescence, nous pouvons déterminer le nombre d'appels récursifs effectués et le travail effectué à chaque niveau. Cette analyse aide à comprendre l’efficacité globale de l’algorithme et à identifier toute inefficacité potentielle ou opportunité d’optimisation.
Introduction
- Pensez à un programme qui détermine la factorielle d'un nombre. Cette fonction prend un nombre N comme entrée et renvoie la factorielle de N en conséquence. Le pseudo-code de cette fonction ressemblera à,
// find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ - La récursivité est illustrée par la fonction mentionnée précédemment. Nous invoquons une fonction pour déterminer la factorielle d'un nombre. Ensuite, étant donné une valeur inférieure du même nombre, cette fonction s'appelle elle-même. Cela continue jusqu'à ce que nous atteignions le cas de base, dans lequel il n'y a plus d'appels de fonction.
- La récursivité est une technique permettant de gérer des problèmes complexes lorsque le résultat dépend des résultats d'instances plus petites du même problème.
- Si l’on pense aux fonctions, une fonction est dite récursive si elle continue de s’appeler jusqu’à ce qu’elle atteigne le cas de base.
- Toute fonction récursive comporte deux composants principaux : le cas de base et l'étape récursive. On arrête de passer à la phase récursive une fois qu'on atteint le cas de base. Pour éviter une récursion sans fin, les cas de base doivent être correctement définis et sont cruciaux. La définition de la récursivité infinie est une récursivité qui n’atteint jamais le cas de base. Si un programme n’atteint jamais le scénario de base, le débordement de pile continuera à se produire.
Types de récursion
De manière générale, il existe deux formes différentes de récursivité :
- Récursion linéaire
- Récursion de l'arbre
- Récursion linéaire
Récursion linéaire
- Une fonction qui s’appelle une seule fois à chaque exécution est dite linéairement récursive. Une belle illustration de la récursion linéaire est la fonction factorielle. Le nom « récursion linéaire » fait référence au fait qu’une fonction linéairement récursive prend un temps linéaire pour s’exécuter.
- Jetez un œil au pseudo-code ci-dessous :
function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } - Si l'on regarde la fonction doSomething(n), elle accepte un paramètre nommé n et effectue quelques calculs avant d'appeler à nouveau la même procédure mais avec des valeurs inférieures.
- Lorsque la méthode doSomething() est appelée avec la valeur d'argument n, disons que T(n) représente le temps total nécessaire pour terminer le calcul. Pour cela, on peut également formuler une relation de récurrence, T(n) = T(n-1) + K. K sert ici de constante. La constante K est incluse car il faut du temps à la fonction pour allouer ou désallouer de la mémoire à une variable ou effectuer une opération mathématique. Nous utilisons K pour définir le temps car il est si infime et insignifiant.
- La complexité temporelle de ce programme récursif peut être simplement calculée puisque, dans le pire des cas, la méthode doSomething() est appelée n fois. Formellement parlant, la complexité temporelle de la fonction est O(N).
Récursion de l'arbre
- Lorsque vous effectuez un appel récursif dans votre cas récursif plus d'une fois, on parle de récursion d'arborescence. Une illustration efficace de la récursion des arbres est la séquence de Fibonacci. Les fonctions récursives des arbres fonctionnent en temps exponentiel ; ils ne sont pas linéaires dans leur complexité temporelle.
- Jetez un œil au pseudo-code ci-dessous,
function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } - La seule différence entre ce code et le précédent est que celui-ci fait un appel supplémentaire à la même fonction avec une valeur inférieure de n.
- Mettons T(n) = T(n-1) + T(n-2) + k comme relation de récurrence pour cette fonction. K sert à nouveau de constante.
- Lorsque plusieurs appels à la même fonction avec des valeurs plus petites sont effectués, ce type de récursion est appelé récursivité arborescente. L’aspect intriguant est maintenant : combien de temps cette fonction prend-elle ?
- Faites une supposition basée sur l'arbre de récursion ci-dessous pour la même fonction.
- Vous penserez peut-être qu'il est difficile d'estimer la complexité temporelle en examinant directement une fonction récursive, en particulier lorsqu'il s'agit d'une récursion arborescente. La méthode de l'arbre de récursion est l'une des nombreuses techniques permettant de calculer la complexité temporelle de telles fonctions. Examinons-le plus en détail.
Qu’est-ce que la méthode de l’arbre de récursion ?
- Les relations de récurrence telles que T(N) = T(N/2) + N ou les deux que nous avons abordées plus tôt dans la section sur les types de récursion sont résolues à l'aide de l'approche de l'arbre de récursion. Ces relations de récurrence utilisent souvent une stratégie diviser pour mieux régner pour résoudre les problèmes.
- Il faut du temps pour intégrer les réponses aux sous-problèmes plus petits qui sont créés lorsqu'un problème plus vaste est décomposé en sous-problèmes plus petits.
- La relation de récurrence, par exemple, est T(N) = 2 * T(N/2) + O(N) pour le tri par fusion. Le temps nécessaire pour combiner les réponses à deux sous-problèmes d’une taille combinée de T(N/2) est O(N), ce qui est également vrai au niveau de la mise en œuvre.
- Par exemple, puisque la relation de récurrence pour la recherche binaire est T(N) = T(N/2) + 1, nous savons que chaque itération de recherche binaire aboutit à un espace de recherche réduit de moitié. Une fois le résultat déterminé, nous quittons la fonction. La relation de récurrence a +1 ajouté car il s'agit d'une opération à temps constant.
- La relation de récurrence T(n) = 2T(n/2) + Kn est à considérer. Kn désigne le temps nécessaire pour combiner les réponses à des sous-problèmes à n/2 dimensions.
- Décrivons l'arbre de récursion pour la relation de récurrence susmentionnée.
Nous pouvons tirer quelques conclusions de l’étude de l’arbre de récursivité ci-dessus, notamment
1. L’ampleur du problème à chaque niveau est tout ce qui compte pour déterminer la valeur d’un nœud. La taille du problème est n au niveau 0, n/2 au niveau 1, n/2 au niveau 2, etc.
2. En général, nous définissons la hauteur de l'arbre comme étant égale à log (n), où n est la taille du problème, et la hauteur de cet arbre de récursion est égale au nombre de niveaux de l'arbre. Cela est vrai parce que, comme nous venons de l’établir, la stratégie diviser pour régner est utilisée par les relations de récurrence pour résoudre des problèmes, et passer d’un problème de taille n à un problème de taille 1 nécessite simplement de suivre des étapes log(n).
- Considérons par exemple la valeur de N = 16. Si nous sommes autorisés à diviser N par 2 à chaque étape, combien d’étapes sont nécessaires pour obtenir N = 1 ? Considérant que nous divisons par deux à chaque étape, la bonne réponse est 4, qui est la valeur de log(16) base 2.
journal (16) base 2
journal (2 ^ 4) base 2
4 * log(2) base 2, puisque log(a) base a = 1
donc, 4 * log(2) base 2 = 4
3. A chaque niveau, le deuxième terme de la récurrence est considéré comme la racine.
Bien que le mot « arbre » apparaisse dans le nom de cette stratégie, vous n'avez pas besoin d'être un expert en arbres pour le comprendre.
Comment utiliser un arbre de récursion pour résoudre des relations de récurrence ?
Le coût du sous-problème dans la technique de l’arbre de récursion est le temps nécessaire pour résoudre le sous-problème. Par conséquent, si vous remarquez l'expression « coût » liée à l'arbre de récursivité, elle fait simplement référence au temps nécessaire pour résoudre un certain sous-problème.
numéro alphabétique
Comprenons toutes ces étapes avec quelques exemples.
Exemple
Considérons la relation de récurrence,
T(n) = 2T(n/2) + K
Solution
La relation de récurrence donnée montre les propriétés suivantes,
Un problème de taille n est divisé en deux sous-problèmes chacun de taille n/2. Le coût de la combinaison des solutions à ces sous-problèmes est K.
Chaque problème de taille n/2 est divisé en deux sous-problèmes chacun de taille n/4 et ainsi de suite.
Au dernier niveau, la taille du sous-problème sera réduite à 1. En d’autres termes, nous atteignons finalement le cas de base.
Suivons les étapes pour résoudre cette relation de récurrence,
Étape 1 : Dessinez l’arbre de récursion
disquette
Étape 2 : Calculer la hauteur de l'arbre
Puisque nous savons que lorsque nous divisons continuellement un nombre par 2, il arrive un moment où ce nombre est réduit à 1. Comme pour le problème de taille N, supposons qu'après K divisions par 2, N devienne égal à 1, ce qui implique, ( n / 2^k) = 1
Ici, n / 2^k est la taille du problème au dernier niveau et elle est toujours égale à 1.
Nous pouvons maintenant facilement calculer la valeur de k à partir de l’expression ci-dessus en prenant log() des deux côtés. Vous trouverez ci-dessous une dérivation plus claire,
ensemble de textes dactylographiés
n = 2^k
- journal(n) = journal(2^k)
- journal(n) = k * journal(2)
- k = journal(n) / journal(2)
- k = log(n) base 2
La hauteur de l’arbre est donc log(n) base 2.
Étape 3 : Calculez le coût à chaque niveau
- Coût au niveau 0 = K, deux sous-problèmes sont fusionnés.
- Coût au niveau 1 = K + K = 2*K, deux sous-problèmes sont fusionnés deux fois.
- Coût au niveau 2 = K + K + K + K = 4*K, deux sous-problèmes sont fusionnés quatre fois. et ainsi de suite....
Étape 4 : Calculez le nombre de nœuds à chaque niveau
Déterminons d'abord le nombre de nœuds dans le dernier niveau. De l'arbre de récursivité, nous pouvons déduire ceci
- Le niveau 0 a 1 (2 ^ 0) nœud
- Le niveau 1 a 2 (2 ^ 1) nœuds
- Le niveau 2 a 4 (2 ^ 2) nœuds
- Le niveau 3 a 8 (2 ^ 3) nœuds
Ainsi, le niveau log(n) devrait avoir 2^(log(n)) nœuds, c'est-à-dire n nœuds.
Étape 5 : Résumez le coût de tous les niveaux
- Le coût total peut s’écrire sous la forme :
- Coût total = Coût de tous les niveaux sauf le dernier niveau + Coût du dernier niveau
- Coût total = Coût pour le niveau 0 + Coût pour le niveau 1 + Coût pour le niveau 2 +.... + Coût pour le niveau-log(n) + Coût pour le dernier niveau
Le coût du dernier niveau est calculé séparément car il s'agit du cas de base et aucune fusion n'est effectuée au dernier niveau. Le coût pour résoudre un seul problème à ce niveau est donc une valeur constante. Prenons-le comme O (1).
Mettons les valeurs dans les formules,
- T(n) = K + 2*K + 4*K + .... + log(n)` fois + `O(1) * n
- T(n) = K(1 + 2 + 4 + .... + log(n) fois)` + `O(n)
- T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) fois + O(n)
Si vous regardez attentivement l'expression ci-dessus, elle forme une progression géométrique (a, ar, ar^2, ar^3 ...... temps infini). La somme de GP est donnée par S(N) = a / (r - 1). Voici le premier terme et r est la raison.