10022_Fibonacci数列的4种求法之一

众所周知，Fibonacci数列是一个著名数列。它的定义是：

f(1) = 1                                      when  n = 1

f(2) = 1                                      when  n = 2

f(n) = f( n-1 ) + f( n-2 )              when  n > 2

本组题目共有4题，请分别用4种不同的方式来完成，并比较这些做法的时间。

本题要求采用第一种方法：递归，且不得使用数组记忆结果。 否则，判cheat且封号。

本题不涉及高精度数。

每行一个整数i，表示Fibonacci数列的第i项。i < 47

对每个整数i，输出Fibonacci数列的第i项。

1
3
20

1
2
6765

本题的测试数据量在4题之中是最少的。

请用递归（也是一种搜索）方法求解本题，否则判cheat且封号。 不会写递归函数的，请先看书学会再写。