数学篇 - 递归,复杂问题分解(笔记)
递归与循环
理论上所有递归能做到的循环都能实现.
递归和循环其实都是迭代法的实现,而且在某些场合下,它们的实现是可以相互转化的。
为什么要使用递归
既然递归的函数值返回过程和基于循环的迭代法一致,我们直接用迭代法不就好了,为什么还要用递归的数学思想和编程方法呢?
如何在限定总和的情况下,求所有可能的加和方式?
假设有四种面额的钱币,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,[])
如果是循环解决这样的问题,是不是相对没有这样简洁?
递归的核心思想和数学归纳法类似,并更具有广泛性。这两者的类似之处体现在:将当前的问题化解为两部分:一个当前所采取的步骤和另一个更简单的问题。
递归会使用计算机的函数嵌套调用。而函数的调用本身,就可以保存很多中间状态和变量值,因此极大的方便了编程的处理。
尾巴
是上无难事,只要肯拆分
微信公众号
