裴波那契（Fibonacci）数列的定义为：它的第1项和第2项均为1，以后各项为其前两项之和。若裴波那契数列中的第n项用Fib（n）表示，则计算公式为： 试编写出计算Fib（n）的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度。

正确答案:递归算法：

递归算法的时间复杂度为O（2ⁿ），空间复杂度为O（n）；非递归算法的时间复杂度为O（n），空间复杂度为O（1）。