题目描述

请使用递归的方式求斐波那契数列的第 $n$ 项，下标从1开始。

斐波那契数列：$1,1,2,3,5…$，这个数列从第 $3$ 项开始，每一项都等于前两项之和

输入格式

共一行，包含整数 $n$。

输出格式

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

4

3

数据范围

$1 \le n \le 30$