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   
输出：_______________

请写出程序的输出结果。

答案

1251334

题解

考点定位

本题考「互递归模拟」,对应大纲 4.2.3 递归（难度【3】）。

解题过程

f1(x,y)：x<n 时调 f2(y,x+y)；f2(x,y)：输出 x，调 f1(y,x+y)。这是斐波那契生成：f1(0,1) → f2(1,1) 输出 1 → f1(1,2) → f2(2,3) 输出 2 → f1(3,5) → f2(5,8) 输出 5 → f1(8,13) → f2(13,21) 输出 13 → f1(21,34)：21<30 → f2(34,55) 输出 34 → f1(55,89)：55<30 ✗ 停。

输出：1 2 5 13 34？核对：f1(0,1)：0<30 → f2(1,1) 输出 1 → f1(1,2)：1<30 → f2(2,3) 输出 2 → f1(3,5) → f2(5,8) 输出 5 → f1(8,13) → f2(13,21) 输出 13 → f1(21,34) → f2(34,55) 输出 34 → f1(55,89)：55<30 ✗。

输出序列：1 2 5 13 34（斐波那契隔项）。

答案：1 2 5 13 34。

易错提醒

① f1/f2 各推一步斐波那契，f2 负责输出奇数位；② 终止条件 x<n 在 f1 中——f2 无条件输出后再进 f1。