C++抽象编程——递归简介(1)——递归范式
最近看了递归,看得我头⽪发⿇,⽯乐志。所以就个时间把所学都总结整理⼀下。所有的都是学⾃《programming abstraction in C++》. ⼤多数的⽤来解决编程的算法策略都有不在计算领域的计算部分。当我们重复完成⼀个任务的时候,我们通常考虑的是循环。当我们做某项界定的时候,我们通常考虑的是条件控制语句。⽤的最多的就是 if while还有for语句了。在你解决更多问题之前,你得学会⼀项强⼤的解决问题的策略跟⼯具。这个策略就是我们的递归策略。递归,就是定义为⼀种把⼤问题通过分割到含有同样形式的⼩问题的⼀种策略。(That strategy, called recursion, is defined as any solution technique in which large problems are solved by reducing them to smaller problems of the same form)。递归是⼀种新的思考问题的⽅式,对初学者来说,很难,想学好就要多练习,多理解。
7.1 A simple example of recursion(递归例⼦)
为了更好的理解递归,我们最好就举个实际的例⼦。试想⼀下。你被任命为基⾦组织的协助者,在为⼀个志愿者很多,但是资⾦缺乏的组织⼯作,你的任务是筹集$1,000,000⽤于捐赠。
当然,如果你认识哪个⼤款肯给你出这笔钱,问题就变得很简单了。但是这样的⼏率⼏乎为0. 那么怎么实现这个⽬标呢?在这⾥,我们可以尝试把要筹的款的账⽬适当降低,⽐如每个⼈出100,这样如果你有10,000个朋友就能完成⽬标。但是你⼜可能没那么多个朋友,那么我们可以换个思路。你是基⾦的负
责⼈,我们说了,你的⾃愿者很多,你可以10个志愿者⼩组的组长,向他们每个⼈要100,000,然后他们通过同样的⽅式向下属要10,000,...... 直到每个⼈的⼿中都可以⽀付起100的时候,就任务完成。那么我们⽤伪代码(pseudocode)的形式表⽰就是:
void collectContributions(int n) {
if (n <= 100) {
Collect the money from a single donor.
} else {
Find 10 volunteers.
Get each volunteer to collect n/10 dollars.
Combine the money raised by the volunteers.
}
}
这个翻译我就不写了。这⾥的重点是这⼀句
Get each volunteer to collect n/10 dollars.
这⼀步直接就是把钱缩⼩了10倍,接下来的步骤都是⼀样,向接下来的10个⼈筹钱,唯⼀不同的就是,n每次都缩⼩10倍。这时候我们可以很轻松的写出这⼀⾏的代码了:
collectContributions(n / 10);
当然,在这⾥要记住,n<=100的时候,说明每个⼈都是可以筹齐100的,就没有必要再向接下来的10个⼈筹款,也就是说,不⽤再调⽤
collectContributions(n / 10);
直接执⾏ if ⾥⾯的语句。
上⾯的例⼦结构是⼀个很典型的递归的结构例⼦,⼀般的递归函数结构都含有⼀下的结构组成
if (test for simple case) {
Compute a simple solution without using recursion.
} else {
Break the problem down into subproblems of the same form.
Solve each of the subproblems by calling this function recursively.
Reassemble the subproblem solutions into a solution for the whole.
}
上⾯是递归函数的模板,我们称之为 递归范式(recursive paradigm)。注意,if ⾥⾯是simple cases,就是说这部分内容不含递归的部分,也可以看做是递归的边界,以后会很经常看到它,这个很重要。也可以理解为数学中的特殊例⼦
当问题满⾜了以下的⼀些特点时,我们可以考虑使⽤递归
1. You must be able to identify simple cases for which the answer is easily determined.
2. You must be able to identify a recursive decomposition that allows you to break any complex instance of the problem into simpler problems of the same form.
也就是说,问题能区分出我们的simple cases,并且能将问题递归分解为更⼩的含有同样形式的函数。
编程递归函数在上叙述的问题中,原始的问题通过将问题分成了更⼩的⼦问题,这些⼩问题都是跟原始问题是同种的形式。这样的解决问题的递归⽅法,我们称之为分治算法。这是我⾃⼰的理解翻译的,我也不知道专业术语是不是这样的。(Because the solution depends on dividing hard problems into simpler instances of the same problem, recursive
solutions of this form are often called divide-and-conquer algorithms)
这⾥先提到递归的主要形式,接下来就会提到具体递归的原理跟调⽤过程。先这样,晚上再写(2)。纯⼿写,就是我翻译得可能太差,毕竟没有中⽂版...
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论