递归中比较常见的例子是斐波那契数列、汉诺塔。
使用递归实现斐波那契数列其实很浪费,f(n) = f(n-1) + f(n-2)。在进一步计算 f(n-1) = f(n-2) + f(n-3),会发现 f(n-2) 被重复计算。
下面是通过循环实现的斐波那契数列:
function Fibonacci(number) { var i, list = new Array(); list[0] = 0; list[1] = 1; for (i = 1; i < number; i++) { list[i + 1] = list[i] + list[i - 1]; } return list[number]; }
获取完整的斐波那契数列:
function Fibonacci(number, full) { var i, list = new Array(); list[0] = 0; list[1] = 1; for (i = 1; i < number; i++) { list[i + 1] = list[i] + list[i - 1]; } if (full) { return list; } return list[number]; }