#11014. 斐波那契的递归层数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

请编写一个递归程序,计算斐波那契序列第 n 项的值,每次调用递归函数时,请输出参数 n 的值以及递归调用的层数(层数从 0 开始)

斐波那契数列以如下被以递推的方法定义:

F(1)=1, 如果n=1
F(2)=1, 如果n=2
F(n)=F(n-1)+F(n-2) ,如果n≥3

输入格式

正整数 n

输出格式

若干行,每一行: n 的值和调用层号,用空格分开

样例

输入1

6

输出1

6 0
5 1
4 2
3 3
2 4
1 4
2 3
3 2
2 3
1 3
4 1
3 2
2 3
1 3
2 2

输入2

2

输出2

2 0

数据范围与提示

1<=n<=10