递归实现Recaman序列：为何计数器反复上下波动？

问题根源 #

你的代码里**多次重复调用recursion(inputnum-1)**是核心问题：

• 判断条件(recursion(inputnum-1)-inputnum)<0时调用了一次递归
• printf输出和return返回时又各调用了一次
• 每次调用都会完整触发从inputnum-1到0的递归流程，导致inputnum==0的基准情况被反复执行，调试语句重复打印，同时递归次数呈指数级增长，效率极低。

修复后的代码 #

把前一次递归的结果先保存到变量中，后续直接复用这个值，避免重复递归：

#include <stdio.h>

int recursion(int inputnum) {
    if (inputnum == 0) {
        printf("term %d, zero returned\n", inputnum);
        return 0; 
    } else {
        // 仅递归一次获取前一项结果，后续直接复用
        int prev = recursion(inputnum - 1);
        int current;
        if ((prev - inputnum) < 0) {
            current = prev + inputnum;
        } else {
            current = prev - inputnum;
        }
        printf("returning %d at term %d \n", current, inputnum);
        return current;
    }
}

int main(void) {
    int numberofterms = 3;
    printf("Final result: %d\n", recursion(numberofterms));
    return 0;
}

运行说明 #

修复后，当numberofterms=3时，递归流程仅执行一次完整链路：

1. 调用recursion(3) → 先触发recursion(2)
2. 调用recursion(2) → 先触发recursion(1)
3. 调用recursion(1) → 先触发recursion(0)
4. recursion(0)触发基准情况，打印term 0, zero returned并返回0
5. 回到recursion(1)，计算current=0+1=1，打印returning 1 at term 1并返回1
6. 回到recursion(2)，计算current=1+2=3，打印returning 3 at term 2并返回3
7. 回到recursion(3)，计算current=3-3=0，打印returning 0 at term 3并返回0
8. main函数输出最终结果Final result: 0

这样就不会重复触发基准情况，递归流程清晰且高效。

内容的提问来源于stack exchange，提问作者VT G