如何使用递归求自然数之和

递归是一个函数直接或间接调用自身的过程。递归算法广泛用于计算机科学,通过将复杂问题分解为更简单的问题来解决它们。

通过解决诸如“两个数的乘积”、“前 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

使用这种方法,您可以一步找到总和,而无需使用递归。

使用递归求前 N 个自然数之和的 C++ 实现

下面是使用递归求前 n 个自然数之和的 C++ 实现:

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

使用递归查找前 N 个自然数之和的 Python 实现

下面是使用递归求前 n 个自然数之和的 Python 实现:

相关:动态规划:示例、常见问题和解决方案

# 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

使用递归查找前 N 个自然数之和的 C 实现

下面是使用递归求前 n 个自然数之和的 C 实现:

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

使用递归查找前 N 个自然数之和的 JavaScript 实现

下面是使用递归求前 n 个自然数之和的 JavaScript 实现:

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

使用递归求前 N 个自然数之和的 Java 实现

下面是使用递归求前 n 个自然数之和的 Java 实现:

相关:什么是递归函数,以及如何在 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、中序/前序/后序树遍历等。

递归是一种非常强大的解决问题的策略。如今,它也广泛用于函数式编程。您必须了解递归的基础知识以及如何将其应用到您的编程工作中。