Python学习日记：递归Recirision（进制转换、数列求和、汉诺塔详解）
递归Recurision一、什么是递归？
递归是一种解决问题的方法，其精髓在于：
将问题分解为规模更小的相同问题，
持续分解，直到问题规模小到可以用非常简单直接的方式来解决。
递归的问题分解方式非常独特，其算法方面的明显特征就是：在算法流程中调用自身。
递归为我们提供了一种对复杂问题的优雅解决方案，精妙的递归算法常会出奇简单，令人赞叹。
二、递归的算法
递归算法将问题分解为更小规模的问题，并调用自身。
递归“三定律”：
1.递归算法必须有一个基本结束条件：最小规模问题的直接解决。
2.递归算法必须能改变状态向基本结束条件演进：减小问题规模
3.递归算法必须调用自身：解决减小了规模的相同问题
三、递归调用的实现过程
当一个函数被调用的时候，系统会把调用时的现场数据压入到系统调用栈
每次调用，压入栈的现场数据称为栈帧。
当函数返回时，要从调用栈的栈顶取得返回地址，恢复现场，弹出栈帧，按地址返回。
以下方算法问题中的进制转换为例子。
我们在进行递归算法调试的时候会经常碰到一个错误： RecursionError。
这是由于递归的层数太多，系统调用栈容量有限，栈也是要占用内存的。
这个时候我们需要检查程序中是否忘记设置基本结束条件，导致无限递归，或者向基本结束条件演进太慢，导致递归层数太多，调用栈溢出。
在Python内置的sys模块可以获取和调整最大递归深度。
import sys
sys,setrecursionlimit(3000)
sys.getrecursionlimit()# 查看当前递归深度
默认为1000， 我们可以将深度设置为3000。
四、递归的算法问题应用
1. 数列求和：
给定一个列表，返回所有数的和。
分析：求和实际上是由一次次的加法实现的，加法刚好有2个操作数，这个是确定的，可以将问题较大的列表规模求和，分解为规模较小且固定的2个数求和（相加）。
例如：（1+（3+（5+（7+9）））），最内层的（7+9）是可以直接计算的
这样，将问题分解为更小规模的相同问题，数列的和就可以分解为： “首个数” + “余下数列” 的和 ，直到包含的数只剩一个，那么它的和就是这个数。
def listsum(numList):
# 等于1时最小规模
if len(numList) == 1:
return numList
else:
# 减小规模，调用自身
return numList + listsum(numList)
# 25
print(listsum())
递归函数调用和返回过程的链条：
1. 任意进制的转换
任意进制的转换，这个算法我们在栈中讨论并实现过，这次使用递归来解决，因为递归和栈确实有一定的关联。
分析：这次解决2~16进制内的任意转换，以16进制为例分析。
16进制有16个不同的符号： convString = "0123456789ABCDEF"
比16小的整数，转换成16进制，直接查表输出即可，convString。
想办法将比16大的整数，拆成一系列比16小的整数，再逐个查表输出。
可以使用整数除（n//16）和求余数(n%16)两个计算来将整数一步步拆开。
得到的结果就变成了更小规模的问题，通过递归调用自身解决。
基本结束条件：当余数总是小于 进制时（比如16），就可以直接查表转换。
代码：
def toStr(n, base):
convertString = "0123456789ABCDEF"
if n < base:
# 最小规模
return convertString
else:
# 减小规模，调用自身
return toStr(n//base, base) + convertString
print(toStr(9, 2))
# 我们以 10进制数 9 转换成 2进制为例子， 结果为 1001 ，下图是流程图
1. 汉诺塔问题
汉诺塔问题是法国数学家Edouard Lucas于1883年，根据传说提出来的。
传说在印度教寺庙里，有3根柱子，其中一根套着由64个由小到大的黄金盘片，僧侣们的任务就是要把这一叠黄金盘子从一根柱子搬到另一根柱子上，但是有两个规则：
1. 一次只能搬1个盘子
2.大盘子不能叠在小盘子上
神的旨意说一旦这些盘子完成迁移，寺庙将会坍塌，世界将会毁灭！
若要搬完这64个盘子：需要移动的次数为 2^{64} - 1 = 18446744073709551615次
如果每秒钟搬一次盘子，需要584942417355年（即五千亿年！）
分析：
根据递归三定律： 最小问题规模（基本结束条件）、如何减小规模、调用自身。
假设有三个柱子，x，y，z ；有5个盘子，穿在 x 柱子上，需要挪到 z 柱子：
若能把上面的四个盘子挪到 y 柱子上，问题就简单了。
把最下面的最大号盘子直接从 x 柱子挪到 z柱子即可
再用同样的办法把 y柱子上的四个盘子，挪到 z 柱子，就完成了。
即 把 n-1 个盘子从x经过z挪到 y ， 把 n 盘子从 x 到 z ，剩下的 n-1 从 y 经过x到 z 。
直到剩下1个盘子，直接挪到 z 。
def moveTower(height, fromPole, withPole, toPole):
if height >= 1:
# 当盘子数量大于1时
# 将 n-1 个盘子从 x（fromPOle） 移动到 y(withPole), 经过 z(toPole)
moveTower(height - 1, fromPole, toPole, withPole)
# 打印盘子移动过程
moveDisk(height, fromPole, toPole)
# 将 n - 1 个盘子从 y（withPole）移动到 z（toPole） ，经过 x（fromPole）
moveTower(height - 1, withPole, fromPole, toPole)
def moveDisk(disk, fromPole, toPole):
print(f'移动{disk}号盘子，从{fromPole}到{toPole}。')
moveTower(3, 'x', 'y', 'z')
# 移动1号盘子，从x到z。
# 移动2号盘子，从x到y。
# 移动1号盘子，从z到y。
# 移动3号盘子，从x到z。
# 移动1号盘子，从y到x。
# 移动2号盘子，从y到z。
# 移动1号盘子，从x到z。
"""Leetcode:汉诺塔问题，用栈将所有盘子从第一根柱子移动到最后一根。"""
class Solution:
def hanota(self, A: List, B: List, C: List) -> None:
n = len(A)
self.move(n, A, B, C)
def move(self, n, A, B, C):
if n == 1:
C.append(A.pop())
else:
self.move(n - 1, A, C, B)
C.append(A.pop())
self.move(n - 1, B, A, C)
下方是程序执行过程，此时以盘子数量为3来为例，蓝色是语句一层一层调用的过程，红色的打印过程：
五、递归可视化：图示
1. Python的海龟作图系统turtle module
"""
爬行：forward(n);backward(n)
转向：left(a);right(a)
抬笔放笔：penup();pendown
笔属性：pensize(s);pencolor(c)
"""
# 递归例子
import turtle
t = turtle.Turtle()
def drawSpiral(t, lineLen):
if lineLen > 0:
# 最小规模，0直接退出
t.forward(lineLen)
t.right(90)
drawSpiral(t, lineLen - 5)
# 减小规模，边长减5 且 调用自身
drawSpiral(t, 100)
turtle.done()
# 递归例子2 分形树
import turtle as t
def tree(branch_len):
if branch_len > 5:
# 树干太短不画，即递归结束条件
# 画树干
t.forward(branch_len)
# 右倾斜 20度
t.right(20)
# 递归调用，画右边的小数，树干减15
tree(branch_len - 15)
# 向左回40度，即左倾斜20度
t.left(40)
# 递归调用，画左边的小树，树干减15
tree(branch_len - 15)
# 向右20度，即回正
t.right(20)
# 海龟退回原位置
t.backward(branch_len)
t.left(90)
t.penup()
t.backward(100)
t.pendown()
t.pencolor('green')
t.pensize(2)
tree(75)
# 画树干长度为75的二叉树
t.hideturtle()
t.done() 代码都是应该在代码块里的，有的代码显示有问题，预览的时候好好的:rggrg 学习学习，感谢
页:
[1]