JS函数:递归
递归是什么?
我们的第一个主题是 递归(recursion)。当一个函数解决一个任务时,在解决的过程中函数会调用自身,这就是所谓的 递归。递归是一种编程模式,在一个任务可以自然地拆分成多个相同类型但更简单的任务的情况下非常有用。
如果你不是刚接触编程,你可能已经很熟悉它了,那么你可以跳过这一章。
两种思考方式
让我们写一个函数 pow(x, n),它可以计算 x 的 n 次方。换句话说就是,x 乘以自身 n 次。
pow(2, 2) = 4 pow(2, 3) = 8 pow(2, 4) = 16
有两种实现方式。
1、迭代思路:使用 for 循环:
function pow(x, n) { let result = 1; // 再循环中,用 x 乘以 result n 次 for (let i = 0; i < n; i++) { result *= x; } return result; } alert( pow(2, 3) ); // 8
2、递归思路:简化任务,调用自身:
function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); } } alert( pow(2, 3) ); // 8
递归变体在本质上是不同的。
当 pow(x, n) 被调用时,执行分为两个分支:
if n==1 = x / pow(x, n) = \\ else = x * pow(x, n - 1)
1、如果 n == 1,所有事情都会很简单,这叫做 基础 的递归,因为它会立即产生明显的结果:pow(x, 1) 等于 x。
2、否则,我们可以用 x * pow(x, n - 1) 表示 pow(x, n)。在数学里,可能会写为 xn = x * xn-1。这叫做 一个递归步骤:我们将任务转化为更简单的行为(x 的乘法)和更简单的同类任务的调用(带有更小的 n 的 pow 运算)。接下来的步骤将其进一步简化,直到 n 达到 1。
我们也可以说 pow 递归地调用自身 直到 n == 1。
比如,为了计算 pow(2, 4),递归变体经过了下面几个步骤:
pow(2, 4) = 2 * pow(2, 3) pow(2, 3) = 2 * pow(2, 2) pow(2, 2) = 2 * pow(2, 1) pow(2, 1) = 2
得到结果的过程:
最后的pow(2, 1)能得到2的结果,它将会被返回到上一个步骤pow(2, 2) = 2 * pow(2, 1)中,应为pow(2, 1)=2所以得到pow(2, 2) = 2 * 2=4;然后返回到pow(2, 3) = 2 * pow(2, 2)中得到pow(2, 3) = 2 * 4=8;最后返回到pow(2, 4) = 2 * pow(2, 3)得到pow(2, 4) = 2 * 8=16,这个时候,输出结果。
因此,递归将函数调用简化为一个更简单的函数调用,然后再将其简化为一个更简单的函数,以此类推,直到得出结果。
递归通常更短
递归解通常比迭代解更短。
在这里,我们可以使用条件运算符 ? 而不是 if 语句,从而使 pow(x, n) 更简洁并且可读性依然很高:
function pow(x, n) { return (n == 1) ? x : (x * pow(x, n - 1)); }
最大的嵌套调用次数(包括首次)被称为“递归深度”。在我们的例子中,它正好等于 n。
最大递归深度受限于 JavaScript 引擎。对我们来说,引擎在最大迭代深度为 10000 及以下时是可靠的,有些引擎可能允许更大的最大深度,但是对于大多数引擎来说,100000 可能就超出限制了。
在很多任务中,递归思维方式会使代码更简单,更容易维护,但是使用递归函数一定要注意,处理不当就会进入死循环。
更多递归实例-计算阶乘:
<script type="text/javascript"> function f(num){ if(num<1){ return 1; }else{ return f(num-1)*num; } } alert("10!的结果为:"+f(10)); </script>
递归还能做更多的事情,这就需要你自己去思考了,总体来说,递归必定会包含分支,一个直接输出结果,一个调用自身,在执行输出直接结果之前,将一直保持在递归中。