编写程序，用递推法计算斐波那契（Fibonacci）数列的第n项。

求解思路：斐波那契（Fibonacci）数列为0，1，1，2，3，5，8，13，……，即：

F(0)=0,F(1)=1,

F(n)=F(n-1)+F(n-2),当n>1时。

用递推法编写的程序为：

执行结果

所谓递归算法就是在函数过程中直接或间接调用自己，还是求斐波那契数列的问题，相应的递归程序为：

执行结果 递归算法简单，但不能无限递归。因此，算法中需要设置递归结束条件。

递归法的时间效率较低，原因是重复计算太多。

例如：计算Fib(5)，总计算次数为2Fib(6)-1=15。