C程序 使用递归查找自然数之和

在这里，我们将看到如何用递归法寻找自然数之和。下面是一些例子。

输入： 5
输出： 15
解释： 1 + 2 + 3 + 4 + 5 = 15

输入： 10
输出： 55
解释： 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

步骤:

• 给定一个数字n。
• 为了计算和，我们将使用一个递归函数recSum(n)。
• 基本条件。如果n<=1，那么recSum(n)返回n。
• 递归调用：返回n + recSum(n-1)。

下面是用递归法求自然数之和的C语言程序。

// C program to find the sum of n
// natural numbers using recursion
#include <stdio.h>
 
// Returns the sum of first n
// natural numbers
int recSum(int n)
{
  // Base condition
    if (n <= 1)
        return n;
   
  // Recursive call
    return n + recSum(n - 1);
}
 
// Driver code
int main()
{
    int n = 10;
    printf("Sum = %d ", recSum(n));
    return 0;
}

输出

Sum = 55 

时间的复杂性： O(n)。

辅助空间： O(n)。