题目描述

北武当山主峰四周几乎都是陡壁悬崖，只有一条人造“天梯”可攀，天梯由n级就山凿筑的石阶组成，欢欢打算通过天梯攀上北武当山主峰。

攀天梯时，他有时一步一级石阶，有时一步两级，那么，他攀上这n级的天梯有多少种不同的方法？

输入格式

一个整数 n ( 1 ≤ n ≤ 80 )。

输出格式

一个整数，表示欢欢攀上这n级天梯的方法数。

样例

5

8

补充要求

用递推和递归算法分别实现本地，观察两种方法对应的运行时间和内存占用情况。思考一下为什么。