算法笔记·4-递归

开头的碎碎念

个人认为,递归算法是一种十分优美的算法。它总是能够用十分短小的代码长度来解决许多复杂的问题。前端实际,在看快速傅里叶变换(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.动态规划法

动态规划

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

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

递归可视化

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

引用

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇