题目描述

斐波那契数列的前几项为：$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$ 从第三项起，每一项都是紧挨着的前两项的和。 请用递归函数计算斐波那契数列的第 $n$ 项。

输入格式

一行一个整数 $n$，表示要求的项数。

输出格式

一行一个整数，表示斐波那契数列第 $n$ 项的值。

10

34

数据范围与提示

• $1 \le n \le 30$
• 保证结果在 int 范围内。