递归（Recursion）递归与回溯的关系密不可分：递归的基本本质是函数调用。在处理问题的时候，递归往往是一个大问题不断变小再推导的过程。回溯是利用递归的性质，从问题的起点出发，不断尝试，回溯一步甚至多步，做出选择，直到最终到达终点的过程。递归算法思想递归算法是一种调用自身函数的算法（二叉树的许多性质按定义满足递归）。汉诺塔问题有A、B、C三座塔，一开始在A塔上放了n个盘子，按照从大到小的顺序从下往上叠放。现在要求把A塔的所有盘子都移到C塔，让你把移动的步骤打印出来。在搬运过程中，一次只能移动一个盘子。另外，任何时候，无论在哪个塔上，大盘都不能放在小盘上面。汉诺塔问题的解决从最终结果开始。要在C塔上按大小顺序堆放n块板，需要将A塔底部最大的一块板移到C塔；除了最大的盘子以外的所有盘子都放在B塔上。从上面可以看出，原来的问题大小从n盘变成了n-1盘，也就是n-1盘被转移到B塔上。如果一个函数可以在B塔的帮助下将n个板块从A塔移动到C塔。那么，这个函数也可以用来在C塔的帮助下将n-1个板块从A塔移动到B塔。同理，保持减少问题的规模。当n为1时，即只有1个plate时，直接打印出步骤。汉诺塔问题代码示例//汉诺塔问题consthano=function(A,B,C,n){if(n>0){hano(A,C,B,n-1)move(A,C)hano(B,A,C,n-1)}}constmove=function(p,c){consttemp=p.pop()c.push(temp)}consta=[1,2,3,4,5]constb=[]constc=[]hano(a,b,c,a.length)console.log('----after----')console.log('a:',String(a))//console.log('b:',String(b))//console.log('c:',String(c))//1,2,3,4,5通过上面总结了递归算法的思想，就是把一个问题的规模缩小，然后用小规模问题得到的结果，结合当前的值或者情况，得到最终的结果。通俗地说，把要实现的递归函数看成已经实现了，直接用它来解决一些子问题，那么需要考虑的是如何根据子问题的解和现在的情况。这种算法也称为自上而下（Top-Down）算法。数字解码题LeetCode第91题，解码的方法。包含字母A-Z的消息按以下方式编码：'A'->1'B'->2…'Z'->26给定一个仅包含数字的非空字符串，计算解码方法的总数。解决数字解码问题的思路是例子中的第二个例子。假设编码后的信息是字符串“226”，如果解码“22”有m种可能，则在最后加一个“6”，相当于在最终解密的字符串中多了一个“F”字符，并且整体解码还是只有m。对于“6”，如果前面有“1”或“2”，那么它可能是“16”、“26”，所以再往前看一个字符，就会发现是“26”。而前面的解码组合是k，然后在k个解出的码上加上一个“Z”，所以总共解码的次数是m+k。数字解码代码实现constnumDecoding=function(str){if(str.charAt(0)==='0')return0constchars=[...str]returndecode(chars,chars.length-1)}//将字符串转为字符组，使用递归函数decode，从最后一个字符串开始向前递归constdecode=function(chars,index){if(index<=0)return1letcount=0letcurr=chars[index]letprev=chars[index-1]//如果当前字符大于`0`，直接使用它之前的字符串得到的结果if(curr>'0'){count=decode(chars,index-1)}//前一个字符和当前字符组成的数字，值必须在1到26之间，否则无法编码if(prev==='1'||(prev=='2'&&curr<='6')){count+=decode(chars,index-2)}returncount}console.log('count:',numDecoding('1213'))//count:5递归解题templatepassed以上为例子，总结一下解题模板of递归函数。解题步骤判断当前情况是否不合法，不合法则立即返回。此步骤也称为健全性检查。比如检查当前处理的情况是否越界，是否有不符合条件的情况。通常，这部分代码是先写的。判断是否满足递归结束条件。这一步处理的基本上是一些推导过程中定义的初始情况。要减小问题的大小，请递归调用。在合并排序和快速排序中，我们将问题大小减少了一半，而在汉诺塔和解码示例中，我们将问题大小减少了一个。利用小题中的答案，结合当前的数据得出最终答案。递归解题模板代码实现函数fn(n){//第一步：判断输入或状态是否非法？如果（输入/状态无效）{返回；}//第二步：判断递归是否应该结束？if(匹配条件){返回一些值;}//Step3:缩小问题的规模result1=fn(n1)result2=fn(n2)...//Step4:Combineresultsreturncombine(result1,result2)}中心对称数问题LeetCode第247题：找出所有长度为n的中心对称数。范例输入：n=2输出：["11","69","88","96"]中心对称数解题思路当n=0时，应输出空字符串：""。当n=1时，即长度为1的中心对称数为：0、1、8。当n=2时，长度为2的中心对称数为：11、69、88、96。注：00不是一个有效的结果。当n=3时，只需在长度为1的合法中心对称数的基础上，两边连续相加11、69、88、96即可。[101、609、808、906、111、619、818,916,181,689,888,986]随着n不断增长，我们只需要在长度为n-2的中心对称数两边分别加上11,69,88,96就够了。中心对称数问题代码实现consthelper=function(n){debugger//Step1:判断输入或状态是否非法if(n<0){thrownewError('illegalargument')}//Step2:判断递归是否结束if(n===0){return['']}if(n===1){return['0','1','8']}//第三步:缩小问题的规模constlist=helper(n-2)//第四步：整合结果constres=[]for(leti=0;i
