Как найти сумму натуральных чисел с помощью рекурсии

23 июня, 2021 Дядя Влад

Рекурсия – это процесс, в котором функция прямо или косвенно вызывает себя. Рекурсивные алгоритмы широко используются в информатике для решения сложных задач, разбивая их на более простые.

Вы можете лучше понять рекурсивные концепции, решив базовые задачи программирования, такие как «произведение двух чисел», «сумма первых n натуральных чисел» и другие.

В этой статье вы узнаете, как найти сумму первых n натуральных чисел с помощью рекурсии.

Постановка задачи

Вам дано натуральное число n , вам нужно найти сумму первых n натуральных чисел с помощью рекурсии.

Пример 1 : Пусть n = 5

Следовательно, сумма первых 5 натуральных чисел = 1 + 2 + 3 + 4 + 5 = 15.

Таким образом, на выходе получается 15.

Пример 2 : Пусть n = 7

Следовательно, сумма первых 7 натуральных чисел = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

Таким образом, на выходе получается 28.

Пример 3 : Пусть n = 6

Следовательно, сумма первых 6 натуральных чисел = 1 + 2 + 3 + 4 + 5 + 6 = 21.

Таким образом, на выходе получается 21.

Рекурсивная функция для нахождения суммы первых N натуральных чисел

Большинство рекурсивных функций имеют следующую относительную структуру:

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

Чтобы найти сумму первых n натуральных чисел, просмотрите и примените следующий псевдокод:

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

Теперь вы можете реализовать этот псевдокод на своем любимом языке программирования.

Связанный: Что такое функция в программировании?

Примечание . Вы также можете найти сумму первых n натуральных чисел, используя следующую математическую формулу:

Сумма n натуральных чисел = n * (n + 1) / 2

Используя этот метод, вы можете найти сумму за один шаг без использования рекурсии.

Реализация C ++ для нахождения суммы первых N натуральных чисел с помощью рекурсии

Ниже приведена реализация C ++ для нахождения суммы первых n натуральных чисел с помощью рекурсии:

 // 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;
 }

Выход:

 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

Реализация Python для нахождения суммы первых N натуральных чисел с помощью рекурсии

Ниже представлена реализация Python для нахождения суммы первых n натуральных чисел с помощью рекурсии:

Связанный: Динамическое программирование: примеры, общие проблемы и решения

 # 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))

Выход:

 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 для нахождения суммы первых N натуральных чисел с помощью рекурсии

Ниже приведена реализация C для нахождения суммы первых n натуральных чисел с помощью рекурсии:

 // 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;
 }

Выход:

 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

Реализация JavaScript для нахождения суммы первых N натуральных чисел с помощью рекурсии

Ниже приведена реализация JavaScript для нахождения суммы первых n натуральных чисел с помощью рекурсии:

 // 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>");

Выход:

 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

Реализация Java для нахождения суммы первых N натуральных чисел с помощью рекурсии

Ниже приведена реализация Java для нахождения суммы первых n натуральных чисел с помощью рекурсии:

По теме:что такое рекурсивная функция и как ее создать на 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));
 }
 }

Выход:

 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

Узнать больше о рекурсии

Рекурсивное мышление очень важно в программировании. Иногда рекурсивное решение может быть проще для чтения, чем итеративное. Вы можете решить многие проблемы, такие как проблема Ханойской башни, DFS графа, обход дерева Inorder / Preorder / Postorder и т. Д., Используя рекурсию.

Рекурсия – очень мощная стратегия решения проблем. В настоящее время он также широко используется в функциональном программировании. Вы должны знать основы рекурсии и то, как вы можете применить ее в своих программах.