Récursion -1

Introduction 1

Le processus dans lequel une fonction s'appelle elle-même est appelé récursivité et le
la fonction correspondante est appelée une fonction récursive.
Puisque la programmation informatique est une application fondamentale des mathématiques, alors laissez
essayons d'abord de comprendre le raisonnement mathématique derrière la récursivité.
En général, nous connaissons tous le concept de fonctions. En un mot, les fonctions sont
des équations mathématiques qui produisent un résultat lors de la fourniture d'une entrée. Par exemple :
Supposons que la fonction F(x) soit une fonction définie par : F(x) = x^2 + 4
Nous pouvons écrire le code Java de cette fonction comme :

public statique int F(int x){
retour (x * x + 4);
>

Maintenant, nous pouvons transmettre différentes valeurs de x à cette fonction et recevoir notre sortie
en conséquence.
Avant de passer à la récursion, essayons de comprendre un autre mathématique
concept connu sous le nom de Principe d'induction mathématique (PMI).

Le principe d'induction mathématique (PMI) est une technique permettant de prouver une affirmation, un
formule, ou un théorème affirmé sur un ensemble de nombres naturels. Il a le
en suivant trois étapes :
1.** Étape du cas trivial* : Dans cette étape, nous prouverons l'énoncé souhaité pour
un cas de base comme n = 0 ou n = 1.
2.*Étape d'hypothèse** : Dans cette étape, nous supposerons que l'énoncé souhaité
est valable pour n = k.

1. Étape de preuve : À partir des résultats de l'étape d'hypothèse, nous prouverons que, n = k + 1 est également vrai pour l'équation souhaitée chaque fois que n = k est vrai.

Par exemple : Prouvons en utilisant le principe d'induction mathématique que :
S(N) : 1 + 2 + 3 + ... + N = (N * (N + 1))/2
(La somme des N premiers nombres naturels)
Preuve :
Étape 1 : Pour N = 1, S(1) = 1 est vrai.
Étape 2 : Supposons que l'énoncé donné soit vrai pour N = k, c'est-à-dire
1 + 2 + 3 + .... + k = (k * (k + 1))/2
Étape 3 : Prouvons l'énoncé pour N = k + 1 en utilisant l'étape 2.

À prouver : 1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
Preuve :

Ajout de (k+1) à la fois LHS et RHS dans le résultat obtenu à l'étape 2 :
1 + 2 + 3 + ... + (k+1) = (k*(k+1))/2 + (k+1)

Maintenant, en prenant (k+1) commun du côté RHS :
1 + 2 + 3 + ... + (k+1) = (k+1)*((k + 2)/2)

Selon la déclaration que nous essayons de prouver :
1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
C'est donc prouvé.

Fonctionnement de la récursion

Nous pouvons définir les étapes de l'approche récursive en résumant les trois ci-dessus
étapes :
● Cas de base : une fonction récursive doit avoir une condition de fin à laquelle
le processus cessera de s'appeler. Un tel cas est appelé cas de base. Sans scénario de base, il continuera à s'appeler et restera coincé dans un
boucle infinie. Bientôt, la profondeur de récursion* sera dépassée et ça lancera
une erreur.
● Appel récursif : La fonction récursive s'invoquera sur une version plus petite
du problème principal. Nous devons être prudents lors de la rédaction de cette étape telle qu'elle est
Il est crucial de comprendre correctement quel est votre petit problème.
● Petit calcul : Généralement, on effectue une étape de calcul dans chaque récursive
appel. On peut réaliser cette étape de calcul avant ou après l'appel récursif
selon la nature du problème.

Remarque : La récursion utilise une pile intégrée qui stocke les appels récursifs. Par conséquent, le
le nombre d'appels récursifs doit être aussi petit que possible pour éviter un débordement de mémoire. Si
le nombre d'appels récursifs dépasse le montant maximum autorisé, le
**la profondeur de récursion** sera dépassée.
Voyons maintenant comment résoudre quelques problèmes courants en utilisant Recursion

Énoncé du problème - Trouver la factorielle d'un nombre

Approche : comprendre les trois étapes du PMI, puis les relier en utilisant
récursivité

1. Étape d'induction : Calcul de la factorielle d'un nombre n - F(n) Hypothèse d'induction : Nous avons déjà obtenu la factorielle de n-1 - F(n-1)
2. Exprimer F(n) en termes de F(n-1) : F(n)=n*F(n-1). Ainsi on obtient

public static int fact(int n){
int ans = fait(n-1); #Étape d'hypothèse
retourner ans * n ; #Résoudre le problème à partir de l'étape d'hypothèse
>

1. Le code n'est toujours pas complet. La partie manquante est le cas de base. Maintenant nous allons essai à sec pour trouver le cas où la récursion doit s'arrêter. Considérons n = 5 :

Comme nous pouvons le voir ci-dessus, nous connaissons déjà la réponse de n = 0, qui est 1. Nous le ferons donc
gardez cela comme cas de base. Ainsi, le code devient désormais :

factorielle int statique publique (int n){
if (n == 0) // cas de base
renvoie 1 ;
d'autre
return n*factorial(n-1); // cas récursif
>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!