递归对于一部分初学者来说是一个门槛也有很多人讲怎么学递归出于怎么能让学生学会递归的角度跟着学了很多。个人觉得学习递归还是要知其然知其所以然当然这个所以然要有一个度咱要是拿出来调试工具去跟踪那一定不是教初学编程的人但是这个度太浅似乎也不行如果只罗列一些结论那么这些知识可能不如不讲。个人觉得要让学生“感觉”嘿我懂了它是这么回事……这样他们在现阶段的知识就有“基石”什么时候他们去真的深究到底CPU这么处理这些数据流、内存中表现是如何的、我咋能挂个钩子……之类的东西的时候可能这些“基石”才会真正垫在底下。但在这之前虚的基石让他们觉得这个事我清楚它背后的原理我不用但是我懂……其实也不懂那么他们可能就能以“更高的视角”、“至少不畏惧”的心态上把上层的、代码层面的递归学得更好一些。个人观点就像尊该尊之老爱可爱之幼一样传授知识也一样——造可造之才。内动力才是最重要的学生想学会是最大的前提。个人观点学递归之前还是要把函数的定义、调用、返回这些基础知识学牢靠。一、举例子先对递归这个东西有点赶脚什么是递归呢就像用递归形式定义的阶乘公式nn*(n-1)!。就像1、查字典来理解一个词A但是这些解释里面有一个词B不懂啊咋办2、查字典来理解一个词B但是这些解释里面有一个词C不懂啊咋办3、恭喜你都会抢答了4、直到某一次例如D这个词的解释里面没有不理解的词了。这时候咋整呢5、依据D的解释理解了C这个词6、依据C的解释理解了B这个词7、依据B的解释理解了A这个词至此完成了理解词A这个任务。这个过程就是递归1→3就是递、5→7就是归。4呢它是一个比较特殊的过程递进到4的时候马上就回归了。二、从另一个角度来看一下可能这个过程不是对于每个人都是必要的。但有一部分人依靠这个过程可以更好的理解递归。放下递归不管我们写一堆函数这些函数就是我们做的事情意思意思如上图所示FnA()会沿着红线调用FnB()FnB()调用FnC()FnC()调用FnD()FnD直接返回结果、无调用FnC()执行完对FnD()的调用返回给FnB()同样的FnB()执行完对FnC()的调用返回给FnA()FnA()执行结束返回。现在我们来看一下FnA()、FnB()、FnC()做的事情调用一个函数获得结果加工后返回——功能一样代码相同但FnD()不一样——因为查字典的时候D的解释中没有不懂的词所以不用调用类似FnA()它们的过程。那么代码是指令它们存在于可执行内存不会因执行而改变这段划掉由于代码相同所以我们把FnA()、FnB()、FnC()保留一个就可以了——因为C会保证我们调用时不会出现混乱它处理的方式很简单函数就在那里就像一个工厂数据进来之后就像原材料被加工成产品再出来那么当这一批产品没生产完下一批来了怎么办先加工新来的这一批才能保证顺序不混乱那之前加工的或未加工的数据怎么办多数情况下新一批产品加工完还需要继续加工这时我们按照一定规则把它们保存起来就可以C的做法是把它们一层一层摞起来拿的时候从上面依次拿下来。所以写一个函数Fn()来完成所有任务是没有问题的如果我们把FnD()也写进来这个函数功能看起来就完整了只需要if一下当不需要调用Fn()时直接返回结果即可。三、稍微专业点FnD()的特殊性在于它是边界——查找的时候我们遇到了简单情况可以直接返回结果的情况。很多递归函数都存在显式边界。其他情况都需要进行递归调用——未到达边界时使用新的数据来调用Fn()函数。根据我们之前的分析1、虽然我们没有编写完Fn()函数但它的功能就是在字典里查一个词然后返回其释义。所以不要忘了这个函数是做什么的——当你需要这个功能就调用这个函数。当然如果你已经有把大问题分解为小问题在适合的地方使用函数来表达的基本功这很简单——你经常把功能实现留下来一个空函数不是吗2、前面的描述中Fn()缺点什么呢它的功能就是在字典里查一个词然后返回其释义。所以我们需要一个参数——因为查字典至少要直到查哪个单词。四、总结一下1、首先明确函数功能是做什么的——你需要处理什么回到最初的例子处理递归形式定义的阶乘我要求一个数的阶乘。2、连带的参数是什么我要求一个数的阶乘至少要知道这个数。3、什么时候递归呢需要的时候^ ^别别别吐芬芳……它确实是这么个事但和另一面——边界紧密相关什么时候不需要再递归了呢到达边界时。边界在哪以递归形式定义的阶乘为例随着计算进行每次传入的数越来越小定义中规定1的阶乘为1——不需要计算了直接返回即可。4、返回回归的时候回归的是什么呢思考一下看看混乱了没有……每次调用最初的时候我们有很多函数是干什么的很简单呀把计算传进来的那个数的阶乘返回呀函数不就是这个功能吗五、上代码int Jc(int x){ if(x1){ //边界1!1 return 1; }else{ //x!x*(x-1)! return x*Jc(x-1); } }C会自动维护一个栈——后进先出先进后出的集合来确保函数调用不会导致混乱。每次调用时先把当前状态保存进去然后进入新的函数——取得所需参数然后运行——运行结束回到之前保存的状态。这个过程可以嵌套即新函数再调用其他函数时也做相同的事情。六、一些表示法如前所述我们使用了一个流程图把递归调用展开但其实这不是个好办法。个人认为对于初学者来说应该从工厂加工产品角度来看这个东西即只关注当前函数在干什么而不跟踪调用——如果跟踪很容易糊了。但有些方法值得我们学习1、用树来表示调用……呃有点那什么哈2、用树……对用类似于括号化定理的那个结构——把它展开一下就可以写更多东西而且还很直观这个结构容易嵌套并且有助于把过程写清楚。七、强化一下据我所知都做过数字翻转。代码大概长这样int main(){ int x; cinx; int ans0; while(x){ ansans*10x%10; x/10; } coutans; return 0; }那么下面哪些代码会输出翻转的数字呢void Function(int x){ if(x0){ return; }else{ coutx%10; Function(x/10); } }void Function(int x){ if(x0){ return; }else{ Function(x/10); coutx%10; } }void Function(int x){ if(x10){ coutx; return; }else{ coutx%10; Function(x/10); } }void Function(int x){ if(x10){ coutx; return; }else{ Function(x/10); coutx%10; } }若x的值包含0在内应该只有一个正确。若包含负数呢思考之后自己测试一下吧。