python编写程序,定义一个求 Fibonacci(斐波那契)数列的函数fib(n),并编写测试代码,输出前 20 项(每项宽度 5 个字符位置,右对齐),每行输出 10个。运行效果参见图 8-5。请分别使用递归和非递归方式实现。

递归方式实现：

def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

for i in range(20):
    print('{:>5}'.format(fib(i)), end='')
    if i % 10 == 9:
        print()

非递归方式实现：

def fib(n):
    if n <= 1:
        return n
    else:
        a, b = 0, 1
        for i in range(n-1):
            a, b = b, a+b
        return b

for i in range(20):
    print('{:>5}'.format(fib(i)), end='')
    if i % 10 == 9:
        print()

输出结果如下：

    0    1    1    2    3    5    8   13   21   34
   55   89  144  233  377  610  987 1597 2584 4181