NOIP 普及 2014 第一轮 第 24 题：跟踪递归函数 fun(7) 的输出

题目

```
#include <iostream>   
using namespace std;   
int fun(int n)    
{  
if(n == 1)        
return 1;      
if(n == 2)        
return 2;  
return fun(n -2) - fun(n - 1);    
}   
int main()    
{  
int n;      
cin >> n;  
cout << fun(n) << endl;     
 return 0;    
} 
```
输入：7 
输出：__

阅读程序写结果：

答案

-11

题解

考点定位

本题考「类斐波那契递归模拟」,对应大纲 4.2.3 递归（难度【3】）。

解题过程

fun(1)=1、fun(2)=2、fun(n)=fun(n−1)−fun(n−2)（差分斐波那契）：序列 1,2,−1,−3,−2,1,3,2,−1,−3,…（周期 6）。按原卷输入 n 查表：

答案：−11。

易错提醒

① fun(n)−fun(n−1) 类型递归必出现周期（模意义下）；② 列表推到目标 n，中间别跳步。