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

更多Python相关文章，请阅读：Python 教程

递归

递归在分割和解决问题时非常有用。每个递归调用本身会产生其他递归调用。递归函数的核心有两种类型的情况：基本情况，用于告诉递归何时终止，和调用它们的递归情况。一个自然使用递归解决方案的简单问题是计算阶乘。递归阶乘算法有两种情况：当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需要四个递归调用以及最初的父调用。