Comment trouver la somme des nombres naturels en utilisant la récursivité

La récursivité est un processus dans lequel une fonction s'appelle directement ou indirectement. Les algorithmes récursifs sont largement utilisés en informatique pour résoudre des problèmes complexes en les décomposant en plus simples.

Vous pouvez mieux comprendre les concepts récursifs en résolvant des problèmes de programmation de base comme le "produit de deux nombres", "la somme des n premiers nombres naturels", et plus encore.

Dans cet article, vous apprendrez à trouver la somme des n premiers nombres naturels en utilisant la récursivité.

Énoncé du problème

On vous donne un nombre naturel n , vous devez trouver la somme des n premiers nombres naturels en utilisant la récursivité.

Exemple 1 : Soit n = 5

Par conséquent, la somme des 5 premiers nombres naturels = 1 + 2 + 3 + 4 + 5 = 15.

Ainsi, la sortie est de 15.

Exemple 2 : Soit n = 7

Par conséquent, la somme des 7 premiers nombres naturels = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

Ainsi, la sortie est de 28.

Exemple 3 : Soit n = 6

Par conséquent, la somme des 6 premiers nombres naturels = 1 + 2 + 3 + 4 + 5 + 6 = 21.

Ainsi, la sortie est 21.

Fonction récursive pour trouver la somme des N premiers nombres naturels

La plupart des fonctions récursives ont la structure relative suivante :

 FUNCTION name
 IF condition THEN
 RETURN result
 ELSE
 CALL FUNCTION name
 END FUNCTION

Pour trouver la somme des n premiers nombres naturels, observez et appliquez le pseudocode suivant :

 findSum(n):
 IF n<=1 THEN
 RETURN n
 ELSE
 RETURN n + findSum(n-1)
 END FUNCTION

Maintenant, vous pouvez implémenter ce pseudocode dans votre langage de programmation préféré.

Connexe : Qu'est-ce qu'une fonction dans la programmation ?

Remarque : Vous pouvez également trouver la somme des n premiers nombres naturels en utilisant la formule mathématique suivante :

Somme de n entiers naturels = n * (n + 1) / 2

En utilisant cette méthode, vous pouvez trouver la somme en une seule étape sans utiliser la récursivité.

Implémentation C++ pour trouver la somme des N premiers nombres naturels à l'aide de la récursivité

Vous trouverez ci-dessous l'implémentation C++ pour trouver la somme des n premiers nombres naturels en utilisant la récursivité :

 // C++ implementation to find the sum of
 // first n natural numbers using recursion
 #include <iostream>
 using namespace std;
 // Recursive function to find the sum of first n natural numbers
 int findSum(int n)
 {
 if (n<=1)
 {
 return n;
 }
 else
 {
 return n + findSum(n-1);
 }
 }
 // Driver code
 int main()
 {
 int n1 = 5, n2 = 7, n3 = 6;
 cout << "n1: " << n1 << endl;
 cout << "n2: " << n2 << endl;
 cout << "n3: " << n3 << endl;
 cout << "Sum of first " << n1 << " natural numbers: " << findSum(n1) << endl;
 cout << "Sum of first " << n2 << " natural numbers: " << findSum(n2) << endl;
 cout << "Sum of first " << n3 << " natural numbers: " << findSum(n3) << endl;
 return 0;
 }

Production:

 n1: 5
 n2: 7
 n3: 6
 Sum of first 5 natural numbers: 15
 Sum of first 7 natural numbers: 28
 Sum of first 6 natural numbers: 21

Implémentation Python pour trouver la somme des N premiers nombres naturels à l'aide de la récursivité

Vous trouverez ci-dessous l'implémentation Python pour trouver la somme des n premiers nombres naturels en utilisant la récursivité :

Connexe : Programmation dynamique : exemples, problèmes courants et solutions

 # Python implementation to find the sum of
 # first n natural numbers using recursion
 # Recursive function to find the sum of first n natural numbers
 def findSum(n):
 if n<=1:
 return n
 else:
 return n + findSum(n-1)
 # Driver Code
 n1 = 5
 n2 = 7
 n3 = 6
 print("n1: ", n1)
 print("n2: ", n2)
 print("n3: ", n3)
 print("Sum of first ", n1, " natural numbers: ", findSum(n1))
 print("Sum of first ", n2, " natural numbers: ", findSum(n2))
 print("Sum of first ", n3, " natural numbers: ", findSum(n3))

Production:

 n1: 5
 n2: 7
 n3: 6
 Sum of first 5 natural numbers: 15
 Sum of first 7 natural numbers: 28
 Sum of first 6 natural numbers: 21

C Implémentation pour trouver la somme des N premiers nombres naturels à l'aide de la récursivité

Vous trouverez ci-dessous l'implémentation C pour trouver la somme des n premiers nombres naturels en utilisant la récursivité :

 // C implementation to find the sum of
 // first n natural numbers using recursion
 #include <stdio.h>
 // Recursive function to find the sum of first n natural numbers
 int findSum(int n)
 {
 if (n<=1)
 {
 return n;
 }
 else
 {
 return n + findSum(n-1);
 }
 }
 // Driver code
 int main()
 {
 int n1 = 5, n2 = 7, n3 = 6;
 printf("n1: %d ⁠n", n1);
 printf("n2: %d ⁠n", n2);
 printf("n3: %d ⁠n", n3);
 printf("Sum of first %d natural numbers: %d ⁠n", n1, findSum(n1));
 printf("Sum of first %d natural numbers: %d ⁠n", n2, findSum(n2));
 printf("Sum of first %d natural numbers: %d ⁠n", n3, findSum(n3));
 return 0;
 }

Production:

 n1: 5
 n2: 7
 n3: 6
 Sum of first 5 natural numbers: 15
 Sum of first 7 natural numbers: 28
 Sum of first 6 natural numbers: 21

Implémentation JavaScript pour trouver la somme des N premiers nombres naturels à l'aide de la récursivité

Vous trouverez ci-dessous l'implémentation JavaScript pour trouver la somme des n premiers nombres naturels en utilisant la récursivité :

 // JavaScript implementation to find the sum of
 // first n natural numbers using recursion
 // Recursive function to find the sum of first n natural numbers
 function findSum(n) {
 if (n<=1) {
 return n;
 } else {
 return n + findSum(n-1);
 }
 }

 // Driver Code
 var n1 = 5, n2 = 7, n3 = 6;
 document.write("n1: " + n1 + "<br>");
 document.write("n2: " + n2 + "<br>");
 document.write("n3: " + n3 + "<br>");
 document.write("Sum of first " + n1 + " natural numbers: " + findSum(n1) + "<br>");
 document.write("Sum of first " + n2 + " natural numbers: " + findSum(n2) + "<br>");
 document.write("Sum of first " + n3 + " natural numbers: " + findSum(n3) + "<br>");

Production:

 n1: 5
 n2: 7
 n3: 6
 Sum of first 5 natural numbers: 15
 Sum of first 7 natural numbers: 28
 Sum of first 6 natural numbers: 21

Implémentation Java pour trouver la somme des N premiers nombres naturels à l'aide de la récursivité

Vous trouverez ci-dessous l'implémentation Java pour trouver la somme des n premiers nombres naturels à l'aide de la récursivité :

Connexes :qu'est-ce qu'une fonction récursive et comment en créer une en Java ?

 // Java implementation to find the sum of
 // first n natural numbers using recursion
 public class Main
 {
 // Recursive function to find the sum of first n natural numbers
 public static int findSum(int n)
 {
 if (n <= 1)
 {
 return n;
 }
 else
 {
 return n + findSum(n - 1);
 }
 }
 // Driver code
 public static void main(String[] args)
 {
 int n1 = 5, n2 = 7, n3 = 6;
 System.out.println("n1: " + n1);
 System.out.println("n2: " + n2);
 System.out.println("n3: " + n3);
 System.out.println("Sum of first " + n1 + " natural numbers: " + findSum(n1));
 System.out.println("Sum of first " + n2 + " natural numbers: " + findSum(n2));
 System.out.println("Sum of first " + n3 + " natural numbers: " + findSum(n3));
 }
 }

Production:

 n1: 5
 n2: 7
 n3: 6
 Sum of first 5 natural numbers: 15
 Sum of first 7 natural numbers: 28
 Sum of first 6 natural numbers: 21

En savoir plus sur la récursivité

La pensée récursive est très importante dans la programmation. Parfois, la solution récursive peut être plus simple à lire que la solution itérative. Vous pouvez résoudre de nombreux problèmes tels que le problème de la tour de Hanoï, le DFS du graphique, les traversées d'arbres en ordre/précommande/postcommande, etc., en utilisant la récursivité.

La récursivité est une stratégie de résolution de problèmes très puissante. De nos jours, il est également largement utilisé dans la programmation fonctionnelle. Vous devez connaître les bases de la récursivité et savoir comment l'appliquer dans vos efforts de programmation.