C语言递归实现自然数求和：代码回溯逻辑疑问

首先你的代码存在一个严重问题：sum函数在处理n≠1的分支时没有返回值，这会导致程序出现未定义行为（比如输出错误结果或者崩溃）。修正后的完整代码如下：

#include<stdio.h>  // 原代码用的conio.h现在多数编译器不支持，换成通用的stdio.h
// #include<conio.h>
// #include<math.h>  // 这段代码不需要math.h，可删除
int sum(int n);
int main()
{
    printf("sum is %d", sum(5));
    return 0;
}
// 递归函数
int sum(int n)
{
    if(n==1)
    {
        return 1;
    }
    int sumNm1 = sum(n-1); // 计算1到n-1的和
    int sumN = sumNm1 + n;
    return sumN; // 必须添加返回语句
}

当调用sum(5)后，递归的执行分为递推和回溯两个阶段，其中回溯的逻辑如下：

递推阶段（从n=5到n=1） #

• 调用sum(5)：n≠1，暂停后续代码执行，先调用sum(4)
• 调用sum(4)：n≠1，暂停后续代码执行，先调用sum(3)
• 调用sum(3)：n≠1，暂停后续代码执行，先调用sum(2)
• 调用sum(2)：n≠1，暂停后续代码执行，先调用sum(1)
• 调用sum(1)：n=1触发终止条件，直接返回1，递推阶段结束，正式进入回溯。

回溯阶段（从n=1回到n=5） #

• sum(2)拿到sum(1)返回的1，计算sumN = 1 + 2 = 3，返回3给sum(3)
• sum(3)拿到sum(2)返回的3，计算sumN = 3 + 3 = 6，返回6给sum(4)
• sum(4)拿到sum(3)返回的6，计算sumN = 6 + 4 = 10，返回10给sum(5)
• sum(5)拿到sum(4)返回的10，计算sumN = 10 + 5 = 15，返回15给main函数

最后main函数接收到返回值15，通过printf输出结果。

内容的提问来源于stack exchange，提问作者avinash Fav