首页 > itarticle > 求斐波那契数列(python) 2 迭代 3 尾递归

求斐波那契数列(python) 2 迭代 3 尾递归

admin 11月 18, 2020 0

def (n):
   if (n == 0):
        return 0
    elif (n == 1): 
     return 1
    else:
       return fibonacci(n-1) + fibonacci(n-2)

2 迭代

def (n):
   n1 = 0
   n2 = 1
   n3 = n
   i = 0
    while (i <= n):
      n3 = n1 + n2
     n1 = n2
      n2 = n3
      i += 1
   return n3

3 尾递归

def (first, second, n):
   if (n<2):
        return n
    if (n == 2):
        return first+second
 return fibonacci(second, first+second, n-1)

	时间复杂度	空间复杂度
递归	O(N^2)	O(N)
迭代	O(N)	O(1)
尾递归	O(N)	/