递归

递归 link

一个函数直接或间接调用自身完成任务处理时，这个函数称为递归函数。递归函数朝解决问题的方向前进时，调用自身进行更深层次的问题处理，当最深层次的问题被解决时函数终止返回。递归常用于可以将问题拆解成具有更小数据规模的相同问题的处理。

• 确定基本不可拆解情况或条件，基本情况用于防止递归函数持续调用自身。
• 确定递归情况或条件，识别问题中相同背景的子问题，进行递归调用。
• 确保递归基本条件能够到达并终止递归调用。
• 联立子问题的处理结果完成原始问题的处理。

递归的优势：

• 帮助更好的构建逻辑处理流程。
• 递归思想帮助实现动态规划和分治相关算法。

使用示例 link

递归示例1 link

自然数的阶乘

def fact(n):
  if n == 0:
    return 1
  return n * fact(n - 1)
# Driver code
print(fact(5)) # 120

递归示例2 link

斐波那契数列
$ fib(n)= \begin{cases} n & n=0,n=1 \\ fib(n-1)+fib(n-2) & n > 1 \end{cases} $

def fib(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  return fib(n - 1) + fib(n - 2)
# Driver code
print(fib(7))