开头的碎碎念

个人认为，递归算法是一种十分优美的算法。它总是能够用十分短小的代码长度来解决许多复杂的问题。前端实际，在看快速傅里叶变换(FFT)时，看到递归算法仅用极小的代码量即可实现复杂的理论，内心感到十分的震撼。

将一个分问题不断拆分成更小的相同问题，其在算法上的特点就是调用自身。

1. 结束条件
2. 减小规模
3. 调用自身

递归调用的实现：函数每次调用将现场数据压入系统调用栈，当函数返回时则从栈顶返回恢复现场。

现场数据：栈保存的一个函数调用所需要维护的信息。
每次调用，压入栈的现场数据成为栈帧。

#python中递归深度的设置(默认为1000)
    import sys
    sys.getrecursionlimit()
    sys.setrecursion(3000)

递归的应用

• 递归数列求和：将问题拆分成两个数相加，当列表长度为1时结束。
• 0-16任意进制的转换：设置convertstring = "0123456789ABCDEF"` 通过除以整除`\\`进制基`base以及对进制基求余数来将整数拆开。当数小于进制基时结束。

    convertstring = "0123456789ABCDEF"
    ......
    else:
        return toStr(n//base,base) + convertstring[n%base]
        #字符串连接；n//base表示整除

• 迷宫：在原位置先向北走一步，如果找不到出口则按北南西东的顺序尝试。（这个实际上随意设置也行）；为了防止艳茹无限递归的死循环，需要加入之前的路径。

• 找零兑换：求兑换最少数量的硬币

  1. 贪心策略：从允许最多数量最大面值的硬币开始，余额则用下一最大面值硬币尽可能多的数量分解。由此直到到达最小面值或余额为0。为了减少算法中的重复计算，可以将中间结果保存在表中。递归之前查表，直接返回。
     2.动态规划法

动态规划

动态规划：从问题的最小规模的最优解开始，逐步扩大问题规模到要解决的问题。

最优化问题能用动态规划解决的必要条件：问题最优解包含和更小规模子问题的最优解。

递归可视化

分形树，谢尔宾斯基三角形，汉诺塔

引用

• 数据结构与算法Python版_中国大学MOOC(慕课)