递归

相信在数学中很常见这个概念，实际在编程中也很常见这样的思维。递归通俗的来说，就是通过不断的将当前问题进行分解，向前追溯直到终点然后再反推求解的过程。

通俗解读

案例一 ：看电影不知道在第几排

看电影时不清楚自己在第几排，可以通过问前一排的人来得知，进行加1即可。那么用递归的思路求解代码就是这样的。

  1. function fn = (n) {
  2.     if(n< = 0) return '座位不存在'
  3.     if(n>1) {
  4.     return fn(n-1)+1
  5.     } else {
  6.     return 1
  7.     }
  8. }

案例二 ：走格子有多少走法

一共有n格，每步可以走1格或者2格，问一共有多少走法。
首先分解问题是第n格可以是前面n-1格走的，也可能是n-2格走的。所以fn(n) = f(n-1) + f(n-2)。也要知道终止条件是只有1步，那么只有一步的可能情况是还有1格，也可能是还有2格。

  1. function fn = (n){
  2.   if(n>2){
  3. return fn(n-1) + fn(n-2)
  4. } else if(n==2)   {
  5. return 2
  6. } else {
  7. return 1
  8. }
  9. }

核心要点解析

可以分解为子问题

也就是返回的递归子问题与当前问题的逻辑拆解关系

这个问题与分解之后的子问题，除了数据规模不同，其他都是相同的

也就是子问题的解法与当前问题是完全一致的，不需要区别写法

有终止条件

不再进行递归的判断条件，并且知道临界条件的特殊值是可求的

实际问题

堆栈溢出

当递归层级过深的时候，因为在递归的过程中会一直把临时变量封装为栈压入内存栈，如果一直压入，就会导致溢出导致服务崩溃。通常的解决方案是设置一个递归深度来进行限制。
比如下面的代码：则假定内存深度为1000，超过1000则抛出异常。

  1. let depth = 0 
  2. let f = (n) => {
  3. ++depth
  4. if(depth>1000) throw error()
  5. if(n===1) return 1
  6. return fn(n-1) + 1 
  7. }

说明：这种不是很实用，因为内存一般是动态变化的，用定值没意义，而如果动态获取内存，又小题大做了。

重复计算

还是上面的递归计算走法的案例，不难发现会重复计算一些中间步骤的走法，导致浪费。当然这种问题不一定会有，和问题的分解有关。

优化方式是针对已经得到结果的走法计到Map缓存中直接使用。

  1. let  f  = ( n) => {
  2.   if (n == 1) return 1;
  3.   if (n == 2) return 2;
  4.   // hasSolvedList 可以理解成一个 Map，key 是 n，value 是 f(n)
  5.   if (hasSolvedList.containsKey(n)) {
  6.     return hasSovledList.get(n);
  7.   }
  8.   ley ret = f(n-1) + f(n-2);
  9.   hasSovledList.put(n, ret);
  10.   return ret;
  11. }

无限递归

也就是没有办法找到终止条件的情况要考虑进，主要是避免死循环或者脏数据的影响

总结

本文主要介绍了常见的递归案例，可以用递归的核心点以及递归可能存在的问题。

彩蛋~~ 魔法币挑战

小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。 魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x+1个魔法币 魔法机器2:如果投入x个魔法币,魔法机器会将其变为2x+2个魔法币 小易采购魔法神器总共需要n个魔法币,所以小易只能通过两台魔法机器产生恰好n个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有n个魔法币。 输入描述： 输入包括一行,包括一个正整数n(1 ≤ n ≤ 10^9),表示小易需要的魔法币数量。 输出描述： 输出一个字符串,每个字符表示该次小易选取投入的魔法机器。其中只包含字符’1’和’2’。 比如输入10，返回122

思路解析

递归

得到操作方案首先想到的递归，原因有以下几方面：
每一步的操作与上一步具有直接联系，而需要获得的最终结果显性的是由最后一次全部转化的。向前递归的界限也很明显，就是没有魔法币。
最终方案如下：

  1. var arr=[]
  2. const toOpt = (n)=>{
  3.   if(n>0){
  4.     if(n%2==0){
  5.     n=(n-2)/2
  6.     arr.push('2')
  7.     }else{
  8.       n=(n-1)/2
  9.       arr.push('1')
  10.     }
  11.     return toOpt(n)
  12.   }else{
  13.     let printStr=arr.reverse().join('')
  14.     console.log(printStr)
  15.     arr.length=0
  16.   }
  17. }

用户输入：readline模块

  1. const readline = require('readline');
  2. const rl = readline.createInterface({
  3.   input: process.stdin,
  4.   output: process.stdout
  5. });
  6. rl.question('', (anwser) => {
  7.   // TODO: Log the answer in a database
  8.   console.log(`${anwser}`)
  9.   rl.close();
  10. });

验证：通过所有测试用例

image.png