递归与循环

理论上所有递归能做到的循环都能实现.

递归和循环其实都是迭代法的实现，而且在某些场合下，它们的实现是可以相互转化的。

为什么要使用递归

既然递归的函数值返回过程和基于循环的迭代法一致，我们直接用迭代法不就好了，为什么还要用递归的数学思想和编程方法呢？

如何在限定总和的情况下，求所有可能的加和方式？

假设有四种面额的钱币，1 元、2 元、5 元和 10 元，要奖励别人10元，那可以奖赏 1 张 10 元，或者 10 张 1 元，或者 5 张 1 元外加 1 张 5 元等等。最终会有多少种方案?

如何把复杂的问题简单化？

// 面额
var rewards = [1, 2, 5, 10];


  /**
    * @Description:  使用函数的递归（嵌套）调用，找出所有可能的奖赏组合
    * @param totalReward-奖赏总金额，result-保存当前的解
    * @return void
    */
function get(totalReward,result){

  // 如果所有奖励全部给完
  if (totalReward == 0) { 
      // 拿到复合条件的结果,输出
    console.log(result); 
    return; 
  }

  // 如果奖励的钱超过当初设想的奖励(钱给多了),
  // 则不是我们想要的结果
  if (totalReward < 0) { return; }

        //根据不同面额触发,让他们开始递归
        for (let i = 0; i < rewards.length; i++) {
          let newResult = [].concat(result)  // 由于有4种情况，需要clone当前的解并传入被调用的函数
          newResult.push(rewards[i]);  // 记录当前的选择

          // totalReward - rewards[i]相当于还有多少钱没有给
          // 交给下一个递归去解决该给多少钱的问题
          get(totalReward - rewards[i], newResult);    // 剩下的问题，留给嵌套调用去解决
        }
}

// 给出10块钱的不同方案
get(10,[])

如果是循环解决这样的问题,是不是相对没有这样简洁?

• 递归的核心思想和数学归纳法类似，并更具有广泛性。这两者的类似之处体现在：将当前的问题化解为两部分：一个当前所采取的步骤和另一个更简单的问题。

• 递归会使用计算机的函数嵌套调用。而函数的调用本身，就可以保存很多中间状态和变量值，因此极大的方便了编程的处理。

尾巴

是上无难事,只要肯拆分

微信公众号

本文链接：