NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 24 题

#include<iostream>
using namespace std;
int n;
void f2(int x,int y);
void f1(int x,int y)
{
    if(x<n)
        f2(y,x+y);
}
void f2(int x,int y)
{
    cout<<x<<' ';
    f1(y,x+y);
}
int main()
{
    cin>>n;
    f1(0,1);
    return 0;

    return 0;
}

输入：30 输出：_______________

这题考递归调用栈的展开顺序。拿到题别急着写代码，先别管函数名，盯着参数变化：初始是(0,1)，每次调用都把两个数加起来传给下一次，关键是看谁先打印。f1 里调 f2，f2 打印后调 f1，相当于把打印动作往后推了一格，但数值是斐波那契式累加的，顺着这个逻辑推几层就能对上答案。

最容易错在没分清 f1 和 f2 谁先打印。很多学生会以为 f1 先输出，或者把 f2 打印的 x 当成当前层的 x 直接输出，忽略了 f2 打印的是上一轮传进来的 x，然后才递归调用 f1 去算下一轮。另外，边界条件 x<n 的判断也容易看错，比如把 x 当成当前层刚打印的值去判断，而不是判断下一轮要不要继续。还有人会误以为这是普通循环，试图用 while 写，结果把递归的“先打印再递归”顺序搞反了。

考点与概念

这道题考查的是递归函数的调用过程，尤其是函数间互相递归（f1 调 f2，f2 调 f1）时，调用栈的展开顺序和打印时机。核心概念很简单：程序不会一次性把所有结果算完再输出，而是边递归边输出——f2 里那句 cout<<x<<' '; 会在进入 f2 时立刻执行，然后才去递归调用 f1。所以输出的顺序完全取决于谁先被调用、谁先打印。

命题人怎么挖坑

命题人故意把两个函数互相调用，而且打印语句放在 f2 的开头，就是想考你：能不能在脑子里模拟出递归树的展开过程。常见陷阱有三处： 1. 误以为 f1 先打印（实际上 f1 只负责递归，不打印）； 2. 把参数搞混，认为 x 和 y 的角色没变，导致算出错误的斐波那契式序列； 3. 忽略 x<n 的边界，多输出一项或漏输出一项。

思考心法：拿到题先想什么？

1. 先确定初始调用：main 里调用的是 f1(0,1)，所以第一层是 f1，x=0, y=1。 2. 看 f1 做了什么：if(x<n)，因为 0<30，成立，于是调用 f2(y, x+y) → f2(1, 1)。 3. 看 f2 做了什么：cout<<x<<' '; → 输出 1；然后递归调用 f1(y, x+y) → f1(1, 2)。 4. 回到 f1：x=1<30，调用 f2(y, x+y) → f2(2, 3)。 5. 看 f2：输出 2；递归 f1(3, 5)。 6. 回到 f1：x=3<30，调用 f2(5, 8)。 7. 看 f2：输出 5；递归 f1(8, 13)。 8. 回到 f1：x=8<30，调用 f2(13, 21)。 9. 看 f2：输出 13；递归 f1(21, 34)。 10. 回到 f1：x=21<30，调用 f2(34, 55)。 11. 看 f2：输出 34；递归 f1(55, 89)。 12. 回到 f1：x=55≥30，不满足条件，不再调用 f2，函数返回。

逐层推演，输出序列

按照上面的步骤，每次 f2 被调用时都会立刻打印一次 x，然后才继续往下递归。所以输出的顺序就是：

1 2 5 13 34

避坑提醒

• 别把 f1 当成“先打印再递归”，f1 只负责判断和调用 f2，打印是 f2 的事。
• 别把参数当成“当前层的 x 和 y 直接输出”，输出的是 f2 刚接收到的 x，也就是上一轮传进来的 y。
• 别忽略 x<n 的边界，当 x 达到或超过 n 时，递归立刻停止，不会再输出任何值。

考频与趋势

根据题库数据，二分查找这个知识点共考过 39 题，覆盖 7 个考试级别（2008-2026 年）。从逐年分布看：

• 2008 年 2 题
• 2009 年 1 题
• 2011 年 2 题
• 2019 年 1 题
• 2021 年 1 题
• 2022 年 2 题
• 2023 年 4 题
• 2024 年 9 题
• 2025 年 7 题
• 2026 年 5 题
• 还有若干“null 年”共 5 题

分赛事来看：

• GESP 五级：16 题
• GESP 七级：7 题
• CSP 入门级：5 题
• CSP 提高级：5 题
• NOIP 提高组 初赛：3 题（本题就属于这一档）
• NOIP 普及组 初赛：2 题
• GESP 六级：1 题

从数据能看出，递归与调用栈这类题目在近年（尤其是 2023-2026）明显增多，2024 年单年就考了 9 题，2025 年 7 题，说明命题人越来越喜欢考“边递归边输出”的陷阱题。虽然本题考的是斐波那契式递归，但本质和二分查找的递归实现（如折半查找的递归写法）在调用栈展开上非常相似。

预测未来怎么考

基于现有数据，递归类题目在 NOIP 提高组初赛中的频率呈上升趋势，且常与数组、字符串或简单数学序列结合。未来几年（2026-2027）很可能会继续出现类似“互相递归 + 边递归边输出”的题型，可能换成其他序列（如阶乘、卡特兰数）或者加入更多层级的函数嵌套（比如 f1 调 f2 调 f3 再调回 f1），考察你对调用栈深度的理解。如果数据不足以支撑更具体的预测（比如某个特定年份的题量），那就如实说明“暂无足够依据预测”。

总结

这道题看似简单，实则是在考你能不能在脑子里完整模拟递归调用栈的展开过程。记住：f1 只负责判断和调用 f2，f2 负责打印和调用 f1，参数每次都是把两个数加起来传给下一层。顺着这个逻辑一步步推，输出序列自然就是 1 2 5 13 34。别再被互相递归搞晕了，冷静下来，一层一层看，答案就出来了。