裴波那契（Fibonacci）数列的定义为：它的第1项和第2项均为1，以后各项为其前两项之和。若裴波那契数列中的第n项用Fib（n）表示，则计算公式为：<br /> <img src="https://nimg.ppkao.com/2019-04/wangjue/2019042914560663707.jpg?sign=804b79efadc7c59cd1f802da515f47e6&t=62d7897a" /><br /> 试编写出计算Fib（n）的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度。