题目描述

斐波那契数列 $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$ 从第三项起，每一项都是紧挨着的前两项的和。写出计算斐波那契数列任意一个数据项的递归程序。（第一个数为 $0$。）

输入格式

输入一个正整数 $n$，表示所求的项数。

输出格式

输出斐波那契数列第 $n$ 项的值。

样例

10

34

数据范围

• $1 \le n \le 30$

来源

CodesOnline