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
é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 pour 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
par conséquent.
Avant de passer à la récursion, essayons de comprendre un autre problème 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 un énoncé, un
formule, ou un théorème affirmé sur un ensemble de nombres naturels. Il a le
en trois étapes :
1.** Étape du cas trivial* : Dans cette étape, nous allons prouver 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.

Pour 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
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
mesures:
● 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 cela 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, nous effectuons une étape de calcul à chaque récursif
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 : Déterminer les trois étapes du PMI, puis les relier à l'aide de
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). On obtient ainsi

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 allons donc
gardez cela comme cas de base. Par conséquent, le code devient désormais :

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