介绍了在 javascript 中利用 arguments.callee 来实现匿名递归的方式.
递归是一种常见的编程技巧, 实名递归相信大家都不陌生, 但如果想要实现匿名递归呢? 比如想要返回一个匿名递归函数, 又或者是定义一个匿名递归函数并直接调用它, 该怎样去做呢? 本文将来探讨一下它的实现.
我们还是先从实名递归说起吧, 还是用那个最简单的求阶乘的例子:
function fact(n) {
if (n < 2) {
return n;
} else {
return n * fact(n - 1);
}
}
console.log(fact(5));
递归要求自己调用自己, 如果函数有名字, 这就太简单不过了.
摘要: 关于递归表达能力的一个总结.
前面为了保持叙述的流畅, 没有做太多的引申, 把总结推迟到了后面.
补上一些总结, 以防止出现 "下面呢? 下面没有了" 的尴尬.
虽然题目在一开始就暗示了这一点, 但首先, 我们还是要问, 它能用递归解决吗?
有点怀疑精神是好的, 既要低头走路, 更要抬头看路, 以防止发生方向性错误, 导致缘木求鱼的后果.
说这个问题能用递归解决, 这种信心或者判断的依据来自于哪呢?
有人可能知道了, 换零钱这个问题在<<计算机程序的构造和解释>>(SICP: Structure and Interpretation of Computer Programs)一书有这个例子, 而在书上是用递归来解决的.
摘要: 递归解决换零钱问题的具体代码实现, 提供了两种实现, 一种面向对象式, 一种面向过程式, 使用 Java 语言.
在上一篇中, 经过深入分析, 已经得出一个能够递归的形式化的结果, 现在则准备给出一个具体实现.
前述结果如下:
caseOfChange(amount, cashList) {
// base case
if (amount.isNegative()) { // 负数
return 0;
}
if (amount.isZero()) { // 0元
return 1;
}
if (cashList.containsOnlyOneCash()) { // 只有一种零钱时
if (amount.canBeChangedWith(cashList.getTheOnlyOneCash())) { // 能换时, 即能整除
return 1;
} else {
return 0;
}
}
// recursive case
return caseOfChange(amount.subtractBy(cashList.getFirstCash()), cashList)
+ caseOfChange(amount, cashList.newCashListWithoutFirstCash());
}
其实已经大体 OK 了, 基本就差确定一下类型就差不多了.
摘要: 用递归方式解决求换零钱种数的问题.
以下是我们的问题:
把 100 元用 50 元, 20 元, 10 元, 5 元, 1 元去换, 总共有几种换法?
为了简化叙述, 把问题记为 coc(100, [50, 20, 10, 5, 1]).
coc: case of change 或者 count of change(change 在英文中有零钱的意思)
为使问题更具有一般性, 参数化具体值, 得到:
caseOfChange(amount, cashList)
其中 amount 为金额, cashList 为零钱列表.
摘要: 用递归的方式来实现的冒泡排序程序.
冒泡排序是种很简单的排序方式. 如果用循环方式, 通常就是两层循环.
由于两层循环都是与元素个数 N 线性相关, 所以可以简单估算出它的时间复杂度是 O(N2), 通常而言, 这是较糟糕的复杂度.
当然, 这也几乎是所有简单方式的宿命, 想简单就别想效率高!
前面篇章说到递归也是一种循环, 所以普通循环能解决的问题, 用递归也能解决. 我们来看看怎么写出它来.