涵俊教编程（一）递归

2018, Jun 04    
讨论：什么是递归？


引出两个重要的概念：

  • Boundary Case 结束条件

  • Recursion Equation 递归式


应用（一）n! 
f(n) = n * f(n-1)
n = 0, f(n) = 1
应用（二）C(n,k) 
C(n,k) = C(n-1,k) + C(n-1,k-1)
n = 0, C(n,k) = 1
k = 0, C(n,k) = 1
k = 1, C(n,k) = n
k = n, C(n,k) = 1
应用（三）斐波那契数列 
f(n) = f(n-1) + f(n-2)
n = 0, f(n) = 1
n = 1, f(n) = 1


时间复杂度


答案
  • n!
      • O(n) = 1 + O(n-1)
  • 斐波那契数列
      • O(n) = O(n-1) + O(n-2) + 1
      规模（数值）上大于斐波那契数列本身


    练习：写出递推法求斐波那契数列第 n 项的 Python 函数

    
def f(n):
    if n == 0 or n == 1:
        return 1
    else:
        return f(n-1) + f(n-2)


    思考：有没有更优的方法？

    
L = [1,1]

for i in range(0, n-2):
    L.append(L[i]+L[i+1])

print(L[n-1])


    总结

  • 递归
  • 递推
  • 记忆化


    • 作业

    用上述三种方法完成 C(n,k) 和斐波那契数列第 n 项的计算

    # 学习