问题说明

Gold King家的一对兔子经过投喂，已经到了繁殖的时候，Gold King查阅资料得到“兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来”。如果所有兔子都不死，那Gold King就有很多很多兔子。
那么问题就来了，假设从Gold King刚开始投喂兔子算起，经过n个月之后，会有多少对兔子呢？

输入格式

输入一个正整数n。

输出格式

递归实现输出有多少对兔子。

3

2

提示

1<=n<=40

来源/分类

算法培训-01-递归 算法培训-02-递归、递推、错排、排列组合