Une fonction récursive est une fonction dont la valeur à tout moment peut être calculée à partir des valeurs de la fonction à certains points précédents. Par exemple, supposons une fonction f(k) = f(k-2) + f(k-3) qui est définie sur un entier non négatif. Si nous avons la valeur de la fonction à k = 0 et k = 2, nous pouvons également trouver sa valeur à tout autre entier non négatif. En d’autres termes, on peut dire qu’une fonction récursive fait référence à une fonction qui utilise ses propres points précédents pour déterminer les termes suivants et forme ainsi une séquence de termes. Dans cet article, nous découvrirons les fonctions récursives ainsi que certains exemples.
liste java en tableau
Qu’est-ce que la récursivité ?
La récursivité fait référence à un processus dans lequel un processus récursif se répète. Récursif est une sorte de fonction d'une ou plusieurs variables, généralement spécifiées par un certain processus qui produit des valeurs de cette fonction en implémentant continuellement une relation particulière avec les valeurs connues de la fonction.
Ici, nous comprendrons la récursion à l'aide d'un exemple.
Supposons que vous deviez emprunter un escalier pour atteindre le premier étage depuis le rez-de-chaussée. Donc, pour ce faire, vous devez procéder par étapes. Il n’y a qu’un seul moyen d’accéder à la deuxième marche : la première marche trempée. Supposons que vous souhaitiez passer à la troisième étape ; vous devez d'abord faire la deuxième étape. Ici, vous pouvez clairement voir le processus de répétition. Ici, vous pouvez voir qu'à chaque étape suivante, vous ajoutez l'étape précédente comme une séquence répétée avec la même différence entre chaque étape. C’est le véritable concept derrière la fonction récursive.
Étape 2: Étape 1 + étape la plus basse.
Étape 3: Étape 2 + Étape 1 + étape la plus basse.
Étape 4: Étape 3 + étape 2 + étape 1 + étape la plus basse, et ainsi de suite.
Un ensemble de nombres naturels est l'exemple de base des fonctions récursives qui partent de un va jusqu'à l'infini, 1,2,3,4,5,6,7,8, 9,…….infinitif. Par conséquent, l’ensemble des nombres naturels présente une fonction récursive car vous pouvez voir une différence commune entre chaque terme sous la forme 1 ; il montre à chaque fois que le terme suivant s'est répété par le terme précédent.
Qu'est-ce qu'une fonction définie de manière récursive ?
Les fonctions définies de manière récursive comprennent deux parties. La première partie traite de la définition du plus petit argument, et d'autre part, la deuxième partie traite de la définition du nième terme. Le plus petit argument est noté f (0) ou f (1), tandis que le nième argument est noté f (n).
Suivez l'exemple donné.
Supposons qu'une séquence soit 4,6,8,10
La formule explicite pour la séquence ci-dessus est f (n)= 2n + 2
La formule explicite de la séquence ci-dessus est donnée par
f (0) = 2
f(n) = f (n-1) + 2
Maintenant, nous pouvons obtenir les termes de séquence en appliquant la formule récursive comme suit f(2 ) f (1) + 2
f(2) = 6
f (0) = 2
f(1) = f(0) + 2
f(1) = 2 + 2 = 4
f(2 ) = f(1) + 2
f(2) = 4 + 2 = 6
f(3 ) = f(2) + 2
f(3 ) = 6 + 2 = 8
À l’aide de la formule de fonction récursive ci-dessus, nous pouvons déterminer le terme suivant.
Qu'est-ce qui rend la fonction récursive ?
Rendre n'importe quelle fonction récursive nécessite son propre terme pour calculer le terme suivant dans la séquence. Par exemple, si vous souhaitez calculer le nième terme d’une séquence donnée, vous devez d’abord connaître le terme précédent et le terme précédant le terme précédent. Par conséquent, vous devez connaître le terme précédent pour savoir si la séquence est récursive ou non récursive. On peut donc conclure que si la fonction a besoin du terme précédent pour déterminer le terme suivant dans la séquence, la fonction est considérée comme une fonction récursive.
La formule de la fonction récursive
Si un1, un2, un3, un4, un5, un6, ……..unn,……est plusieurs ensembles ou une séquence, alors une formule récursive devra calculer tous les termes qui existaient auparavant pour calculer la valeur d'un
unn= unn-1 +un1
La formule ci-dessus peut également être définie comme formule récursive de séquence arithmétique. Vous voyez clairement dans la séquence mentionnée ci-dessus qu'il s'agit d'une suite arithmétique, qui comprend le premier terme suivi des autres termes et une différence commune entre chaque terme. La différence commune fait référence à un nombre que vous leur ajoutez ou soustrayez.
Une fonction récursive peut également être définie comme la séquence géométrique, où les ensembles de nombres ou une séquence ont un facteur commun ou un rapport commun entre eux. La formule de la séquence géométrique est donnée par
unn= unn-1 *r
Habituellement, la fonction récursive est définie en deux parties. Le premier est l'énoncé du premier terme avec la formule, et un autre est l'énoncé du premier terme avec la règle relative aux termes successifs.
Comment écrire une formule récursive pour une séquence arithmétique
Pour écrire la formule récursive pour la formule de séquence arithmétique, suivez les étapes indiquées
Étape 1:
Dans un premier temps, vous devez vous assurer que la suite donnée est arithmétique ou non (pour cela, vous devez ajouter ou soustraire deux termes successifs). Si vous obtenez le même résultat, alors la séquence est considérée comme une séquence arithmétique.
Étape 2:
Maintenant, vous devez trouver la différence commune pour la séquence donnée.
Étape 3:
Formulez la formule récursive en utilisant le premier terme, puis créez la formule en utilisant le terme précédent et la différence commune ; ainsi vous obtiendrez le résultat donné
arpenter une commande
unn= unn-1 +d
maintenant, nous comprenons la formule donnée à l'aide d'un exemple
supposons que 3,5,7,9,11 est une séquence donnée
Dans l'exemple ci-dessus, vous pouvez facilement trouver qu'il s'agit de la suite arithmétique car chaque terme de la suite augmente de 2. Ainsi, la différence commune entre deux termes est 2. Nous connaissons la formule de la suite récursive
unn= unn-1 +d
Donné,
ré = 2
un1= 3
donc,
un2= un(2-1)+ 2 = un1+2 = 3+2 = 5
un3= un(3-1)+ 2 = un2+2 = 5+2 = 7
un4= un(4-1)+ 2 = un3+2 = 7+2 = 9
un5= un(5-1)+ 2 = a + 2 = 9+2 = 11, et le processus continue.
Comment écrire une formule récursive pour une séquence géométrique ?
Pour écrire la formule récursive pour la formule de séquence géométrique, suivez les étapes indiquées :
Étape 1
Dans un premier temps, vous devez vous assurer que la séquence donnée est géométrique ou non (pour cela, vous devez multiplier ou diviser chaque terme par un nombre). Si vous obtenez le même résultat d’un terme au terme suivant, la séquence est considérée comme une séquence géométrique.
Étape 2
Maintenant, vous devez trouver la raison commune pour la séquence donnée.
Étape 3
Formulez la formule récursive en utilisant le premier terme, puis créez la formule en utilisant le terme précédent et la raison ; ainsi vous obtiendrez le résultat donné
unn=r*unn-1
Maintenant, nous comprenons la formule donnée à l'aide d'un exemple
supposons que 2,8,32, 128,.est une séquence donnée
Dans l'exemple ci-dessus, vous pouvez facilement trouver qu'il s'agit de la suite géométrique car le terme successif de la séquence est obtenu en multipliant 4 par le terme précédent. Ainsi, la raison entre deux termes est 4. On connaît la formule de la suite récursive
unn=r*unn-1
unn= 4
unn-1= ?
Donné,
r = 4
un1= 2
100 km/h en mph
donc,
un2= un(2-1)* 4 = un1+ * 4 = 2* 4 = 8
un3= un(3-1)* 4 = un2* 4 = 8 * 4 = 32
un4= un(4-1)* 4 = un3* 4 = 32* 4 = 128, et le processus continue.
Exemple de fonction récursive
Exemple 1:
Déterminer la formule récursive de la séquence 4,8,16,32,64, 128,….?
Solution:
Étant donné la séquence 4,8,16,32,64,128,…..
La suite donnée est géométrique car si on multiplie le terme précédent, on obtient les termes successifs.
Pour déterminer la formule récursive pour la séquence donnée, nous devons l'écrire sous forme de tableau
| Numéros de trimestre | Terme de séquence | Notation de fonction | Notation d'indice |
|---|---|---|---|
| 1 | 4 | f(1) | un1 |
| 2 | 8 | f(2) | un2 |
| 3 | 16 | f(3) | un3 |
| 4 | 32 | f(4) | un4 |
| 5 | 64 | f(5) | un5 |
| 6 | 128 | f(6) | un6 |
| n | . | f(n) | unn |
Par conséquent, la formule récursive en notion de fonction est donnée par
f(1) = 4, f(n) . f(n-1)
En notation en indice, la formule récursive est donnée par
un1= 4, unn= 2. unn-1