将华氏温度转化成摄氏温度是一个简单公式,它可以由一个简单的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)
在求解一个问题的同一实例时,切勿在不同的递归调用中做重复性的工作