5.用递归算法计算1到n的累加和。

使用递归算法计算从1到n的累加和，也称为求和或阶乘，是最经典的数学问题之一。递归的基本思想是将大问题分解成若干相同的小问题，然后逐个解决，直到达到基本情况。对于这个问题，基本情况通常是当n等于1时，结果为1；否则，我们将n减1，并加上当前n的值。

以下是一个简单的C语言代码实现：

#include <stdio.h>

// 递归函数定义
int recursive_sum(int n) {
    // 基本情况
    if (n == 1) {
        return 1;
    } else {
        // 递归调用，将n减1并加上当前n
        return n + recursive_sum(n - 1);
    }
}

int main() {
    int n;
    printf("请输入一个正整数n：");
    scanf("%d", &n);

    // 计算累加和并输出结果
    int sum = recursive_sum(n);
    printf("从1到%d的累加和是：%d\n", n, sum);

    return 0;
}

相关问题

C语言用递归算法实现，输入整数 n（n>0），求 1+3+5+7....+(2*n-1)的和

可以用递归函数来实现这个功能。具体的实现方法如下：

#include <stdio.h>

int sum(int n);

int main() {
    int n;
    printf("请输入一个正整数：");
    scanf("%d", &n);
    printf("1+3+5+...+(2*%d-1)=%d\n", n, sum(n));
    return 0;
}

int sum(int n) {
    if (n == 1) { // 当n等于1时，直接返回1
        return 1;
    } else {
        return 2 * n - 1 + sum(n - 1); // 当n大于1时，递归调用sum函数，并将结果累加
    }
}

这里的递归函数 `sum` 用来计算从1到n的奇数和。当n等于1时，直接返回1，否则递归调用sum函数，将结果累加返回。

需要注意的是，在使用递归的时候，需要设置递归终止条件，否则会出现无限递归导致程序崩溃的情况。在本题中，当n等于1时，我们就可以直接返回1。

计算1加到100的非递归算法和递归算法的时间复杂度

1. 非递归算法（例如使用循环）计算从1加到100的和，通常会通过累加的方式来完成。这个过程可以看作是一个简单的线性操作，时间复杂度是O(n)，其中n为100，因为我们需要做100次加法。这种算法不会因为函数调用自身而增加额外的时间开销。

2. 递归算法则会将问题分解成更小的部分来解决。比如著名的斐波那契数列求和问题，可以用递归定义为 F(1) = 1, F(2) = 2, F(n) = F(n-1) + F(n-2)。对于1到100的和，我们可以用Fibonacci序列的思想，但是直接应用递归并不适用于计算总和，因为它会重复很多项。为了优化，我们可以采用记忆化搜索或者动态规划来避免重复计算，但这本质上还是O(2^n)的时间复杂度，因为每个值都需要计算一次。

总结一下：
- 非递归算法：时间复杂度为O(n)
- 递归算法（未优化）：理论上最坏情况下的时间复杂度为O(2^n)