c++ 递归函数怎么写_c++斐波那契数列示例

递归函数必须有明确终止条件和自我调用；常见错误是漏写n==0导致栈溢出，C++中需同时处理base case和向其收敛的recursive case。

递归函数的基本写法：必须有终止条件和自我调用

没有终止条件的 fibonacci 会无限调用自己，直到栈溢出。C++ 递归函数核心就两点：明确的退出分支（base case），和向该分支收敛的递归分支（recursive case）。

常见错误是把终止条件写成 n == 1 却漏掉 n == 0，或者用 n 但没考虑负数输入——这会导致未定义行为。

• 斐波那契标准定义：fib(0) = 0，fib(1) = 1，fib(n) = fib(n-1) + fib(n-2)（n >= 2）
• 实际使用中，若只处理非负整数，n 可作为安全终止条件
• 不要在递归里做输入校验（如 if (n ），否则每次调用都重复检查，浪费开销

最简可行的 C++ 斐波那契递归实现

下面这个版本能跑通，但仅适用于小数值（n 左右）。它直接对应数学定义，可读性强，适合教学或逻辑验证。

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

注意：fibonacci(0) 返回 0，fibonacci(1) 返回 1，符合主流定义（OEIS A000045）。有些老教材从 fib(1)=1, fib(2)=1 开始编号，此时需调整终止条件为 n 并返回 1，但参数含义就变成“第 n 项”，容易混淆索引。

立即学习“C++免费学习笔记（深入）”；

为什么大一点的 n 就卡住？时间复杂度爆炸是硬伤

这个递归不是“慢”，而是指数级重复计算。比如算 fibonacci(5)，fibonacci(3) 会被算 2 次，fibonacci(2) 被算 3 次——随着 n 增大，调用次数接近 O(2^n)。

• fibonacci(40) 约需 2.6 亿次函数调用，在普通机器上明显卡顿
• fibonacci(50) 调用次数超 200 亿，基本不可接受
• 编译器无法自动优化这种朴素递归（不像尾递归可转循环），C++ 标准不保证尾调用消除

如果真要算大 n，要么改迭代（用两个变量滚动更新），要么加记忆化（std::unordered_map 缓存已算结果），但那就不是“纯递归”了。

调试时怎么确认是不是栈溢出了？

程序直接崩溃、没输出、或报错信息含 Segmentation fault（Linux/macOS）或 Stack overflow（Windows），大概率是递归太深。g++ 编译时加 -g，用 gdb 运行后崩了执行 bt（backtrace），能看到几百上千层 fibonacci 调用堆栈。

• 默认栈空间通常只有 1~8 MB，每层调用至少占几十字节（返回地址+参数+栈帧管理），n > 10000 就可能溢出
• 临时扩栈（如 Linux 下 ulimit -s 65536）治标不治本，不能解决指数复杂度问题
• 真正该做的，是意识到：递归在这里是表达意图的工具，不是性能解法

写递归时，先想清楚它是否真需要“层层展开”，还是只是图个逻辑直白。斐波那契就是个典型——递归写起来像公式，跑起来像灾难。