递归简论

/ 0评 / 0

将华氏温度转化成摄氏温度是一个简单公式,它可以由一个简单的C函数直接表达: C = 5 * (F - 32) / 9
然而有时候数学函数以不太标准的形式进行定义。例如,在非负整数集上定义一个函数F,它满足F(0) = 0且F(X) = 2 * F(X - 1) + X * X;
这个公式可以用js表示成

function recursive(x) {
    if(x == 0) {
        return 0;
    } else {
        return 2 * recursive(x - 1) + x * x;
    }
}
recursive(0);//0
recursive(1);//1
recursive(2);//6
recursive(3);//21

通过上面的函数我们可以总结出递归有两个基本法则:
1)基准情形(base case)
基准情形是递归必有要素。F(0) = 0就是这个函数的基准情形,它不用递归就能求解。
2)不断推进(making progress)
需要递归求解的情形,递归会不断朝向基准情形推进。因为只有基准情形才是不需要递归就能求解的!

在这个过程中,我们又开始思考一个问题,是不是递归就是循环逻辑(circular logic)呢?
答案是否定的。虽然我们定义一个函数用的是这个函数本身,但是我们并没有用函数本身定义该函数的一个特定的实例。

除此之外递归还有另外两条基本法则:
3)设计法则
假设所有递归调用都能运行
4)合成效益法则(compound interest rule)
在求解一个问题的同一实例时,切勿在不同的递归调用中做重复性的工作

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注