Python数据结构之递归方法讲解

本次课程将深入探讨Python中至关重要的递归技术。如果您对过往的基础内容感兴趣，可以参考以下系列文章进行回顾：

Python数据类型：Python数据结构之数据类型。 Python输入输出：Python数据结构之输入输出、控制和异常。 Python面向对象：Python数据结构之面向对象。 Python算法分析：Python数据结构算法分析。 Python数据结构之栈、队列和双端队列。

递归在处理重复性任务时是一个常被考察的关键概念，具有极高的学习价值。

1.递归概念

递归是一种解决问题的策略，其核心思想是将复杂问题不断拆解为更小的子问题，直至子问题可以通过常规方法直接求解。通常情况下，递归通过函数不断调用自身来实现。尽管表面看似简单，但递归能帮助我们构建出极其优雅的解决方案。对于某些特定问题，若不采用递归，解决难度将显著增加。 为了更直观地理解上述概念，我们通过一个具体案例进行说明：计算数组中所有数值的总和。

#用for循环的简单函数
def getsum(numlist):
    a=0
    for i in numlist:
        a=i+a
    return a

运行结果如下：

假设目前暂时无法使用 while 循环以及 for 循环，我们该如何计算结果呢？此时，我们可以借鉴加法运算的逻辑，即加法是接受两个参数的函数。基于这一思路，我们将计算一列数之和重新定义为计算两个数字对的和。

注：最内层的括号对 (7 + 9) 无需借助循环或其他特殊语法结构即可直接求解。 伪代码表示如下：

#first(list)返回列表中的第一个元素，rest(list)则返回其余元素。用 Python 可以轻松地实现这个等式，
getsum(list)=first(list)+getsum(rest(list))

具体代码实现如下：

#这是一个递归小案例，这个函数在函数内部自己调用了自listsum(numlist[1:])
def listsum(numlist):
    if len(numlist)==1:#当数组的长度为1时，代表是数组是一个数了
        return numlist[0]
    else:
        return numlist[0] + listsum(numlist[1:])#第一个数加上后面的数，这里自己调用了自己，是数组不断递归的条件

在这段代码中，有两个关键思想值得深入探讨。首先，第 2 行代码检查列表是否仅包含一个元素。这一检查至关重要，它构成了函数的退出条件。对于长度为 1 的列表，其元素之和即为该列表中的唯一数值。其次，listsum 函数在第 5 行调用了自身！这正是我们将 listsum 称为递归函数的原因——递归函数的核心特征在于其会调用自身。

以下是相加过程的演示：

2. 递归三原则

递归算法遵循三个重要原则：

• 递归算法必须包含停止条件
• 递归算法必须改变其状态并向停止条件靠近
• 递归算法必须递归地调用自身

让我们回顾第一个案例，看看它是如何实现这些原则的：

• len(numlist)==1 用于判断停止条件
• numlist[1:] 代表问题的数据以某种方式变得更小
• return numlist[0] + listsum(numlist[1:]) 代表递归地调用自己

递归的逻辑并非简单的循环，而是将问题分解为更小、更易解决的子问题。

2.1 实现任意进制的数据转换

下面展示将 10 进制的 29 转换为 2 进制数的方法。按照此逻辑，可以将 10 进制数转换为任意进制的数。

此处我们使用递归来实现 2 至 16 进制数的转换。

#n代表要转化的10进制数，base代表你要实现的多少进制的数
def toStr(n, base):
    convertString = "0123456789ABCDEF"#取对应位置的字符
    if n < base:#如果10进制数小于你所转换的进制数位数，则直接选择字符
        return convertString[n]
    else:#递归核心，n//base获取结果，然后进行递归
        return toStr(n//base, base) + convertString[n%base]

至此，关于Python数据结构之递归方法讲解的文章介绍完毕。如需了解更多Python递归相关内容，请搜索本站历史文章或继续浏览后续相关文章。希望大家今后多多支持本站！