【算法】递归

递归

• 递归
• • 初始递归：数列求和
  • 递归的应用：任意进制转换
  • 递归深度限制
  • 递归可视化：分形树
  • 递归可视化：谢尔宾斯基Sierpinski三角形
  • 递归的应用：汉诺塔
  • 递归的应用：指数级枚举
• • 求细胞数量
  • 递归的应用：探索迷宫
• 分治策略和递归
• 优化问题
• • 兑换最少个数硬币问题
• 贪心策略

递归

递归是一种解决问题的方法，其精髓在于将问题分解为规模更小的相同问题，持续分解，直到问题规模小到可以用飞常简单直接的方式来解决。
递归的问题分解方式非常独特，其算法方面的明显特征就是：在算法流程中调用自身。
递归为我们提供了一种对复杂问题的优雅解决方案。

函数自己调用自己，形如：

int f(int x){
   
	xxxxx
	xxxxx
	xxxxx
	return f(x-1);
}

初始递归：数列求和

问题：给定一个列表，返回所有数的和
列表中数的个数不定，需要一个循环和一个累加变量来迭代求和

既不能用for，也不能用while，对不确定长度的列表求和

def listsum(numList):
	theSum=0
	for i in numList:
		theSum=theSum+i
	return theSum

print(listsum([1,3,5,7,9]))

求和实际上由一次次的加法实现，而加法恰有2个操作数

将问题规模较大的列表求和，分解为规模较小而且固定的2个数求和

数列求和问题首先具备了基本结束条件：当

递归的应用：任意进制转换

整数转换为任意进制
十进制有10个不同符号：convString=“0123456789”
比10小的整数转换成十进制，直接查表：convString[n]
比10大的整数，拆成一系列比10小的整数，逐个查表，如769，拆成7、6、9
递归三定律里，基本结束条件为：小于10的整数；拆解整数的过程就是向“基本结束条件”演进的过程
用整数除，和求余数两个计算将整数一步步拆开
除以“进制基base”：//base
对“进制基”求余数：%base
问题分解为：余数总小于“进制基base”，是基本结束条件，可直接进行查表转换
整数商成为“更小规模”问题，通过递归调用自身解决

def toStr(n,base):
	convertString="0123456789ABCDEF"
	if n<base:
		return convertString[n]
	else:
	return toStr(n//base,base)+convertString[n%base]

print(toStr(1453,16))

当一个函数被调用的时候，系统会把调用时的现场数据压入到系统调用栈
每次调用，压入栈的现场数据称为栈帧
当函数返回时，要从调用栈的栈顶取得返回地址，恢复现场，弹出栈帧，按地址返回

递归深度限制

RecursionError
检查是否忘记设置基本结束条件，导致无限递归。
或者向基本结束条件演进太慢，导致递归层数太多，调用栈溢出

def tell_story():

在Python内置的sys模块可以获取和调整最大递归深度

递归可视化：分形树

Python的海龟作图系统tuetle moudle

import turtle
t=turtle.Turtle()
# 作图开始
for i in range(4):
	t

螺旋

import turtle

t=turtle.Turtle()

def drawSpiral(t,lineLen):
	if lineLen

分形：一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状，即具有自相似的性质

递归可视化：谢尔宾斯基Sierpinski三角形

面积趋于0，周长趋于∞
谢尔宾斯基三角形是由三个尺寸减半的谢尔宾斯基三角形按照品字形拼叠而成
我们无法真正做出谢尔宾斯基三角形，只能做出degree有限的近似图形
在degree有限的情况下，degree=n的三角形，由3个degree=n-1的三角形按品字形拼叠而成，边长均为degree=n的三角形的一半（规模减小）
当degree=0，则就是一个等边三角形，这是递归结束的基本条件

import turtle
def sierpinski(degree,points):
	colormap=['blue','red','green','white','yellow']

递归的应用：汉诺塔

规则：
一次只能移动一个
大盘子不能叠在小盘子上

假设有5个盘子串在1#柱上，需要移到3#柱上

1. 把上面的一摞4个盘子移到2#柱上
2. 把剩下的最大号盘子移到3#柱上
3. 把2#柱上的4个盘子移到3#柱上

如果能有办法把最上面的4个盘子移到2#柱，那么问题就好解决了。接下来的问题就是把4个盘子从1#移到2#，此时问题规模已经减小：

1. 把上面的一摞3个盘子移到3#柱上
2. 把剩下的最大号盘子移到2#柱上
3. 把3#柱上的3个盘子移到2#柱上

移动3个盘子可以分解为上面2个和下面的最大号盘子
移动2个盘子可以分解为上面的盘子和下面的盘子

思路：一定有三个柱子，两个柱子是无法完成的
将盘子从开始柱，经由中间柱，移到目标柱：

1. 将上层N-1个盘子的塔，从开始柱，借助目标柱，移到中间柱；
2. 将最大的（第N个）盘子从开始柱移到目标柱；
3. 将放置在中间柱的N-1个盘子借助开始柱，移到目标柱

基本结束条件（最小规模问题）：1个盘子的移动问题

def moveTower