[数据结构与算法]python数据结构——（4）递归及其应用

递归概念

递归（recursion）:就是将问题分解为规模更小的相同的问题。

特征：在算法流程中调用自身，不用for、while循环。

举个简单的例子，计算 1+3+5+7+9。

上式可以写成：(1+(3+(5+(7+9))))，总结如下： 数列的和 = 首个数 + 余下数列的和

用代码表示如下：

def listsum(numlist):
	if len(numlist) == 1:
		return numlist[0]
	else:
		return numlist[0] + listsum(numlist[1:])

递归算法三定律：（必须同时成立才能调用递归算法）

1、必须有一个结束条件；
2、算法状态必须能向基本结束条件演进，即该事件能无限拆成类似自己的小事；
3、在分成的小事件中调用自身。

递归应用

应用一：进制转换

问题描述：将一个十进制数转换成任意进制。

十进制转换成二进制，我们可以用“栈”来实现。具体参考：pthon数据结构——（1）栈及其应用

这里我们用递归的方法实现。

首先说明一个问题，十进制数 234，为什么能用这样表示呢？ 十进制的话，每一位的取值范围都是[0~9]，将234用10除，234 ÷ 10 = 23······4。商是23，余数是4。继续计算，23 ÷ 10 = 2······3，商是2，余数是3。2 ÷ 10 = 0······2，商是0，余数是2。我们发现将三个余数组合起来，即为十进制表示。因为，我们我们也可以将 所给值value除以进制，得到商和余数，再用商不断的重复计算。这里就用到了递归算法。

在这里，我们假设转换的最高进制为16进制，实现代码如下：

def toStr(n, base):
	# n：被转进制的数  
	# base: 进制是几
    convertString = "0123456789ABCDEF"
    if n < base:
        return convertString[n]
    else:
        return toStr(n//base, base) + convertString[n % base]

测试代码：

print(toStr(1453, 16))

结果：(计算器亲测没问题)

5AD

应用二：汉诺塔

问题描述：如上图，有三根柱子，分别标记为A、B、C，在柱子A上有N个盘子，并且从上往下依次增大，现在要将全部的盘子移动到C柱子上，使得C柱子上的盘子排列与移动前的A完全一致，遵循的规则如下：1、一次只能移动一个盘子；2、大盘子不能在小盘子上面。问：该怎么移动，移动的次数是多少？

思路：（从A，经过B, 移动到C）

1. 将A中上面的N-1个盘子，经过C，移动到B；(此时C空)
2. 将A中的最后一个盘子移动到C；（此时A空，C相当于空）
3. 将B中的N-1个，经过C，移动到A。(复原状态，此时A中有N-1个盘子)

基本结束条件：一个盘子的移动问题。

实现代码如下：

def moveTower(height, fromPole, withPole, toPole):
    if height >= 1:
        # 从 fromPole 移到 withPole 经过了 toPole
        moveTower(height-1, fromPole, toPole, withPole)
        moveDisk(height, fromPole, toPole)
        moveTower(height-1, withPole, fromPole, toPole)
        
def moveDisk(disk, fromPole, toPole):
    print(f"moving disk[{disk} from {fromPole} to {toPole}]")

测试代码：（以3个为例）

moveTower(3, "A", "B", "C")

结果：

moving disk[1 from A to C]
moving disk[2 from A to B]
moving disk[1 from C to B]
moving disk[3 from A to C]
moving disk[1 from B to A]
moving disk[2 from B to C]
moving disk[1 from A to C]

我们总结出，N个盘子，最后的移动次数为：(2^N) - 1。

（这个问题据说是西方的一个故事，据说谁能将N=64的汉诺塔移动成功，世界末日就会来临。以每秒移动一次来计算，太阳的生命结束，也不可能移动成功，所以世界末日可不会来临）

我是Raymond_桐，欢迎各位批评指正，一起交流学习。