求斐波那契数的非递归实现

今天在做MOOC“程序设计入门—Python”的习题，原题如下：

时间限制：500ms 内存限制：32000kb

一开始，我用递归算法实现，运行时间居然超过了500ms的限制。后来改用循环实现，运行时间的测试结果是17ms！看来递归的效率真的会比循环低很多！

本题源码如下：

#!/usr/bin/env python
# encoding: utf-8

#一个斐波那契数列的前10项为：1, 2, 3, 5, 8, 13, 21, 34, 55, 89，
#对于一个最大项的值不超过n的斐波那契数列，求值为偶数的项的和。

#第n位的斐波那契数
def fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        a = 1
        b = 2
        for i in range(3,n+1):
            c = a + b
            a = b
            b = c
        return b

def print_sum():
    n = int(raw_input())
    sum = 0
    i = 1
    while True:
        temp_num = fib(i)
        if temp_num > n:
            break
        if temp_num % 2 == 0:
            sum += temp_num
        i += 1
    print sum

print_sum()