[算法系列] 搞懂递归, 看这篇就够了 !! 递归设计思路 + 经典例题层层递进 |
您所在的位置：网站首页 › 书签设计思路怎么写好 › [算法系列] 搞懂递归, 看这篇就够了 !! 递归设计思路 + 经典例题层层递进 |
|
[算法系列] 搞懂递归, 看这篇就够了 !! 递归设计思路 + 经典例题层层递进
从学习写代码伊始, 总有个坎不好迈过去, 那就是遇上一些有关递归的东西时, 看着简短的代码, 怎么稀里糊涂就出来了. 今天我们就来好好好探讨递归这个东西. 本文结合他的相关概念,引出有关递归程序设计的一些例子,并加以说明, 其旨在更好地理解递归,使用递归. 0 什么是递归?很多文章对于递归有很深刻的字面上的解释, 比如一个函数重复调用自身, 什么递过去再调回来之类的. 下面, 我们从自身调用来谈起吧 : def f(i): f(i-1) f(5)在f()定义中自身调用了f , 并将之前的参数i - 1 传入f . 因此不难知道 f(5)运行时是这样的 : f(5) --> f(4) --> f(3) --> f(2) --> ... f(-∞)不断地调用自身, 并且参数减1. 单纯地这样调用实际上并不满足递归, 当然, 我们的问题也不可能得以解决的哦. 回到设计程序初 : 我们设计程序时, 这个传入参数 i 是我们为解决眼前问题时的规模 , i - 1 是小一号的问题的规模 . 比如: 我们令f(i) 为 某人花掉 i 元钱 . 那么f(i) 在自身 调用f(i - 1) 时相当于 自己先花掉1 元后 ,将剩下的 i - 1元钱给另一个人用. 显然, 钱不可能为负, 因此总有被花光的时刻(i = 0 时应当终止), 相应的, 重复自身调用也有终止的一刻 , 也即是说, 递归要有出口 : def f(i): if i == 0 : return f(i - 1)在花钱函数中增加了一个判断 , 如果i =0 了 ,就return. 这就表示当一个人拿到钱的数目为0 , 他得上报(return)给之前调用给他的那个人,然后层层上报, 报给最初的那个人. 与此同时, 我们在缩减问题规模时, 可能并不是像上述例程那样, 什么都不做就直接i - 1 , 而是会"花一块钱" , 这其实就是我们所说的递归的 副作用. 注意, 这是我们在问题规模减小时所加的副作用, 当钱用光了,层层上报时 , 能不能也有副作用呢? 答案是显然是肯定的. 我喜欢把这两种副作用称之为 递过去过程中的副作用 和 归回来过程中的副作用 上述部分说明了: 什么是递归 ----- 函数自己调用自己. 注意死循环 ------ 递归要有出口 递归往往有副作用 ----- 递过去途中 的 和 归来途中, 其中递过去往往是问题规模缩小的过程, 归来过程是已经触及到出口后的返回知道了什么是递归那么我们怎么来设计递归呢? 找重复, 思考问题规模如何缩小 找变化 找边界, 就是递归出口了下面为了更好地体会下递归并说明上述三条 , 将下列问题用递归方式表达 求n的阶乘 找重复: n的阶乘 = n * (n - 1的阶乘), 那么 求 "n - 1的阶乘"就是原问题的重复 – 子问题 找变化: 这里就是n的量越变越小 – 变化的量往往作为参数 找边界: 出口, 找一个数的阶乘, 不可能小于1 def jiecheng(n): if(n == 1 ): return 1 return n * jiecheng(n - 1) 顺序打印 i 到 j ( i j): return print(i) print_i_j(i +1 , j)我们再看看这个递归写法: 在没到达出口条件时: 先打印出i , 再调用 小一号规模的问题. 下面是调用结果: print_i_j(1,10) #1 2 3 4 5 6 7 8 9 10 倒序打印 i 到 j ( i j): return print_i_j(i +1 , j) print(i, end=" ")现在来分析下print(i)放在下一次调用之前 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |