Python 中的递归和回溯是什么?

pythonserver side programmingprogramming更新于 2023/11/10 5:41:00

递归

递归在划分和解决问题时很有用。每个递归调用本身都会衍生出其他递归调用。递归函数的核心是两种类型的案例:基本案例，它告诉递归何时终止，以及调用它们所在函数的递归案例。自然使用递归解决方案的一个简单问题是计算阶乘。递归阶乘算法有两种情况:n = 0 时的基准情况，以及 n>0 时的递归情况。

回溯是一种用于寻找某些计算问题的解决方案的通用算法，它逐步为解决方案构建选择，并拒绝继续处理会导致不可能解决方案的轨迹。如果先前的选择被证明是错误的，回溯允许我们撤消它们。

阶乘的典型实现如下 -

def factorial(n):
  #测试基本情况
     if n==0:
         return 1
         # 进行计算和递归调用
         f= n*factorial(n-1)
      print(f)
  return(f)
factorial(4)

此代码打印出数字 1、2、4、24。要计算阶乘 4，需要四次递归调用加上初始父调用。