Fonction récursive C ++

Un processus dans lequel une fonction spécifique s'appelle directement ou indirectement est connue pour être une récursivité, et cette fonction respective est une fonction récursive. Le processus de récursivité traite de l'itération de plusieurs nombres à la même fonction. Pour résilier l'exécution d'un processus de récursivité, nous devons avoir un cas de base suivi d'une condition. Ce tutoriel utilise l'implication des fonctions de récursivité en C ++, donc avant de lire ceci, vous devez être familier avec les bases de ce langage de programmation.

La récursivité est une approche efficace pour dissoudre les problèmes tels que des tâches de calcul mathématiques complexes. Cela se fait en distribuant la tâche dans des sous-tâches. Ce processus se fait en suivant la règle de division et de conquér. Ce n'est pas une chose obligatoire d'utiliser toujours un processus de récursivité dans votre programme pour la répétition. Tout problème résolu par la récursivité peut également être résolu par itération. Mais la fonction récursive est plus efficace dans la programmation car le code est très court et facilement compréhensible tout en effectuant la même tâche. Le processus de récursivité est toujours recommandé pour des problèmes tels que la recherche et le tri, les traversées d'arbres, etc.

Note: Le processus de récursivité doit avoir une condition de terminaison ou une classe de base. Dans le deuxième cas, cela conduira à des exécutions infinies comme une boucle d'itérations.

Syntaxe de la fonction récursive (C ++)

La syntaxe de base de la fonction récursive est donnée comme suit:

void recurse ()
// déclaration (s)
recurse ();

Le concept consiste à diviser un problème en de nombreux problèmes plus petits, puis à ajouter toutes les conditions de base qui peuvent arrêter la récursivité.

Condition de base

Dans tout programme récursif, la solution d'un problème plus important s'exprime dans des problèmes plus petits.

Int Fact (int n)

si (n < = 1) // base case
retour 1;
autre
'Autre déclaration'

La déclaration / condition de 'n < =1' is defined here, and hence the larger value can be solved by converting to a smaller one until the condition of the base case is fulfilled. If we don't use a base condition in our program, then there will be no ending point specifying the code, the infinite execution will occur. Here we will use a sample example.

Fonction simple

Considérons maintenant un échantillon d'une fonction récursive dans laquelle nous prenons une valeur dans le programme principal, puis passez-le à la fonction. À l'intérieur d'une fonction, nous utilisons une instruction IF-ELSE. La partie «si» de l'instruction fait référence à la condition de base pour terminer la fonction ou pour limiter la sortie. Cela sera appliqué lorsque la valeur est inférieure à 1.

Si (val < 1)

Tandis que la fonction principale est appliquée sur la partie «else» de la fonction. C'est la fonction récursive.

# Fonction (Val - 1)

La valeur est affichée avant et après cette instruction, de sorte que la sortie contiendra les nombres en descendant et dans l'ordre croissant. L'exécution du code se fait via un compilateur G ++. '-o' est utilisé pour enregistrer la sortie d'un code source dans un fichier de sortie.

$ g ++ -o r1 r1.c
$ ./ R1

Maintenant, nous voulons voir l'effet de la condition de base dans ce programme. Nous verrons la valeur résultante; Si nous supprimons l'instruction IF-Else du même programme que celle décrite ci-dessus, quelle sera la sortie.

Vous pouvez voir que le reste du code est inchangé après avoir supprimé l'instruction conditionnelle. Après avoir supprimé l'instruction de base, la sortie ressemblera à l'image ci-dessous. Il n'y aura pas de point final défini pour cette exécution. Vous pouvez remarquer que la sortie est une sorte infinie un seul numéro.

Cette même sortie dure de nombreuses lignes jusqu'à ce qu'un message de Core Dump soit affiché.

Fonctionnement de la récursivité

Supposons qu'un programmeur est disposé à déterminer la somme des n nombres de premiers nombres, il existe de nombreuses façons de déterminer la somme, mais la plus simple est d'ajouter les nombres en commençant de 1 à n. La fonction ressemblera donc à ceci:

F (n) = 1 + 2 + 3 + 4 + 5 +… + n

L'exemple ci-dessus est l'ajout simple des nombres. La deuxième approche traite de l'utilisation d'une fonction récursive.

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

Maintenant, vous pouvez souligner la différence entre les deux approches. Dans la deuxième approche, f () est une dissimilarité de base, comme on l'appelle lui-même.

La récursivité est de deux types. L'un est une récursion directe. Le second est une récursivité indirecte. Une fonction est appelée un récursive indirect s'il a un appel de fonction pour une autre fonction et cette autre fonction appelle la première fonction directement ou indirectement. Un échantillon pour la récursion directe est illustré comme:

Int f (int n)
F (n);
// du code

Tandis qu'un échantillon pour la récursivité indirecte est représenté comme:

void f (int n)
F1 ();
void f1 (int n)
F();
retour;

Nous allons maintenant développer les deux types de fonctions récursives à travers quelques exemples de base.

Récursivité directe

Exemple 1

Cet exemple traite du calcul de la série Fibonacci. Encore une fois, le concept est le même; Une déclaration conditionnelle est utilisée ici pour arrêter la condition; La valeur doit être égale à zéro. Sinon, si la valeur est égale à 1 ou 2, elle reviendra 1. Comme cette formation de série nécessite 2 nombres, le nombre utilisé dans le programme principal doit être supérieur à 2. La formule de déclaration pour le Fibonacci est écrite dans l'art «else» de la condition. C'est principalement la récursivité du programme.

# Fonction (val - 1) + fonction (val - 2))

Tandis que la fonction principale initiera l'appel fonctionnel en contournant la valeur. Cette valeur est un nombre à laquelle la sortie doit être. La sortie peut être vérifiée à travers la borne Linux par un compilateur G ++.

Exemple 2

Cet exemple traite du calcul factoriel d'un nombre. Pour ce calcul, un nombre doit être supérieur à 1, donc nous avons ici appliqué une condition de base; Si cette partie de la déclaration «IF» est remplie, le programme sera interrompu; Sinon, le fonctionnement mathématique est appliqué au nombre.

Fonction Val * (Val - 1)

Il s'agit de la fonction de récursivité, dans laquelle la réponse de la fonction est à nouveau utilisée dans l'appel de la fonction.

La valeur résultante est indiquée ci-dessous.

Récursivité indirecte

Nous appliquerons le même calcul de factorielle indirectement. Comme nous l'avons décrit précédemment, que dans la récursivité indirecte, les fonctions ne l'appellent pas, nous avons donc besoin d'une autre fonction à cet effet. Prenez un exemple qui a deux fonctions. Dans la fonction A, la fonction de récursivité est déclarée de la même manière que dans l'exemple précédent, mais l'appel de fonction est pour la deuxième fonction, fonction b. La fonction B contient la même méthode de calcul, et il contient l'appel récursif pour la fonction A.

Dans le programme principal, un appel de fonction à la fonction a est fait.

Lorsque vous voyez la sortie, vous remarquerez que la réponse pour les deux méthodes de récursivité est la même, mais seule la différence est dans l'approche utilisée.

Conclusion

«C ++ Recursive Function» présente de nombreux avantages car il est utilisé dans les processus de recherche et de tri. La condition de base a le rôle principal dans l'exécution de la récursivité, car elle limite la sortie et l'exécution infinie. Les exemples couramment utilisés sont expliqués ici pour fournir à la compréhension de l'utilisateur de la récursivité.