python数据结构|python数据结构——递归recursion python数据结构|python

什么是递归递归是一种解决问题的方法，它把一个问题分解为越来越小的子问题，直到问题的规模小到可以被很简单直接解决。通常为了达到分解问题的效果，递归过程中要引入一个调用自身的函数。乍一看，递归算法并没有什么特别的地方，但是，利用递归我们能够写出极为简明的解决问题的方法，而且如果不用递归，这些问题将具有很大的编程难度。
计算数字列表的和我们先从一个简单的问题开始我们的探究，这个问题不需要递归也可以解决。假如你想对一个数字列表进行求和（例如[1,3,5,7,9]），代码所示的是一个通过迭代函数（for 循环）求和的程序。这个函数用一个变化着的“累加器”变量（theSum）对列表里面所有的数进行累加求和，也就是从 0 开始，依次加上列表中的每个数。

def list_sum(num_list): the_sum = 0 for i in num_list: the_sum = the_sum + i return the_sum print(list_sum([1,3,5,7,9]))

现在，假设我们不能使用 while 循环或者 for 循环，那么你会如何对数字列表中的数进行求和呢？如果你是个数学家，那么你首先想到的也许是：按照定义，加法是一个有两个参数——两个数字——的函数。为了将数字列表的问题重新定义为对两个参数求和的问题，我们可以利用全括号的表达式来重新表示列表，就像这种形式：(1+(3+(5+(7+9))))。
我们注意到最内层的括号中是（7+9),这是不需要任何循环或者特殊的结构就能解决的。事实上，我们可以用以下一系列简化后的式子来计算最终的加和。那么我们怎样将这个思想转化为 Python 代码呢？首先让我们从 Python 列表的角度来重新叙述这个问题。由于数字列表的和是列表中的第一个元素（numList[0]）和剩下所有的元素（numList(1:)）之和的和，求和问题可以归纳成以下的式子：listSum(numList)=first(numList)+listSum(rest(numList))
在这个等式中，first 代表列表中的第一个元素，而 rest 代表的是列表中除了第一个元素以外
的其他所有元素。此式很容易在 Python 中用代码表示出来。

def list_sum(num_list): if len(num_list) == 1: return num_list[0] else: return num_list[0] + list_sum(num_list[1:]) print(list_sum([1,3,5,7,9]))

在这个代码中，有一些关键点需要注意。首先，在第二行中，我们检查这个列表中是否只有一个元素。这个检查非常关键，因为它是函数能结束运行的必要条件。对一个长度为 1 的列表来说，它的和显然只是这个列表中的数，其次，在第五行中，函数调用了自身！这就是我们把后一个计算程序称为“递归”的原因。递归函数就是一种调用自身的函数。
递归三大定律

递归算法必须有个基本结束条件
递归算法必须改变自己的状态并向基本结束条件演进
递归算法必须递归地调用自身

将整数转化成任意进制表示的字符串形式假设你想要将一个整数转化为二进制到十六进制之间任意进制的字符串形式。例如，把整数 10转换为十进制表示的字符串“10”，或二进制表示的字符串“1010”。尽管有很多算法可以解决这个问题，包括在”栈”的章节中讨论的算法，但用递归的思想解决该问题还是非常简洁优雅的。
下面我们将以十进制的 769 为例看一个具体的问题。
假设我们有一个字符序列来对应前 10 个数字，形如 convString=“0123456789”。通过在字符串中检索，很容易将小于 10 的整数转换成对应的字符串。例如，如果数字是 9，那么字符串是 convString[9]或"9"。如果我们可以将数字 769 拆成三个单独的数字 7、6 和 9，然后很容易地将它转换成字符串。小于 10 的整数看起来是个不错的基本结束条件。
确定进位数之后整个算法将包含 3 个部分：

将原始整数分解为一连串的单个数字。
通过在字符序列中检索将单个数字转换成字符串。
将这些单个数字的字符串连接起来，形成最终的结果。

下一步就是要解决如何改变状态，使其向基本结束条件演进。既然我们正在讨论关于整数的问题，那么就让我们考虑一下什么数学运算会把一个数字分解。最有可能的运算是除法和减法。虽然减法可以实现，但我们并不清楚应该减去多少。整数的除法取余的运算给了我们一个明确的的方向。让我们来看看如果把试图转换的数字除以进位数会发生什么。
用整数的除法将 769 除以 10，我们得到 76 余 9。这给了我们两个好的结果。首先，余数是一个小于进位数的数字，通过检索，它可以直接转换成一个字符
第二，我们得到了一个小于初始数字的新数字"76"，它能让我们向着“找到小于进位数的单个数字”的基本结束条件演进。现在我们的任务是再将 76 转换为它的字符串形式。我们将再一次使用除法取余得运算，这样分别得到 7 和 6.最后，我们将问题简化为转换数字 7 为字符串形式，因为它满足基本结束条件“n

def to_str(n, base): convert_string = "0123456789ABCDEF" if n < base: return convert_string[n]# 检测基本结束条件 else: return to_str(n // base, base) + convert_string[n % base] #10//3=3，10%3=1 #实现递归调用自身，并且减小问题规模print(to_str(17, 16))

请注意，在第 3 行我们检查进位数 base，当 n 小于 base 时我们才会进行转换。当我们检测到基本结束条件时，我们会停止递归过程并且仅仅从 convertString 序列中返回字符串。在第 6 行里，我们在满足递归第二、三条定律的基础上，通过运用除法，做到了递归算法调用自身和减小问题规模这两点。
在第 6 行先使用递归调用to_str(n // base, base)，然后添加了字符串表示的余数convert_string[n % base]。如果我们把这两个顺序调换，先返回 convertString 的查找
结果再返回 toStr 调用，生成的字符串将会反向！但通过递归调用返回结果后再进行连接操作，结果是正确的。
栈帧：实现递归如果不是按上文“toStr()”那样通过递归调用将所得的单个字符连在一起输出得到结果，而是通过修改算法，以类似于递归执行时的先后顺序，把这些字符压入一个栈中来得出结果，会是如何呢？修改后的代码如下所示：

# 使用栈的方法递归调用 class Stack: def __init__(self): self.item=[]def isEmpty(self): return self.item==[]def push(self,item): self.item.append(item)def pop(self): return self.item.pop()r_stack = Stack() def to_str(n, base): convert_string = "0123456789ABCDEF" while n > 0: if n < base: r_stack.push(convert_string[n]) else: r_stack.push(convert_string[n % base]) n = n // base res = "" while not r_stack.isEmpty(): res = res + str(r_stack.pop()) return res print(to_str(17, 16))

【python数据结构|python数据结构——递归recursion】这个例子能够是我们了解 Python 是如何执行递归函数的调用的：
在 Python 中，当一个函数被调用时，系统会分配一个栈帧去处理函数中的那些局部变量。当执行完函数，并得到了一个返回值时，这个值会被留在栈顶等待被调用的函数来处理。

文章图片

图示递归

#图示递归，用海龟做一个螺线 import turtle myTurtle = turtle.Turtle()#创建一只海龟 myWin = turtle.Screen()#创建一个作图的窗口 def drawSpiral(myTurtle, lineLen):#drawSpiral函数的基本结束条件是linLen减小到0 if lineLen > 0: myTurtle.forward(lineLen)#使海龟前进linLen myTurtle.right(90)#使海龟右转90度 drawSpiral(myTurtle,lineLen-5)#出现递归drawSpiral(myTurtle,100)myWin.exitonclick()#使海龟待机，单击窗口才会清空

#画分形树 import turtle def tree(branchLen,t): if branchLen > 5: t.forward(branchLen) t.right(20) tree(branchLen-15,t) t.left(40) tree(branchLen-15,t) t.right(20) t.backward(branchLen) def main(): t = turtle.Turtle() myWin = turtle.Screen() t.left(90) t.up() t.backward(100) t.down() t.color("green") tree(75,t) myWin.exitonclick()main()