Liawn's blog

# 递归

# 理解递归

    递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。简单来说就是程序调用自身。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。     构成递归需要两个条件：1.子问题须与原始问题为同样的事，且更为简单；2.不能无限制地调用本身，须有个出口（边界条件），化简为非递归状况处理。     递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。——百度百科“递归” (opens new window)

# 计算一个数的阶乘

数 n 的阶乘，定义为 n!，表示从 1 到 n 的整数的乘积。

# 迭代阶乘

/**
 * 迭代方法求阶乘
 */
export function factorialIterative(number: number) {
  if (number < 0) {
    return undefined;
  }
  let total = 1;
  for (let n = number; n > 1; n--) {
    total *= n;
  }
  return total;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 递归阶乘

/**
 * 递归方法求阶乘
 */
export function factorial(n: number): number {
  if (n < 0) {
    return undefined;
  }
  if (n === 1 || n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12

# 斐波那契数列

斐波那契数列 (opens new window)又称黄金分割数列，指的是这样的数列：1、1、2、3、5、8、13、21、34...，从第 3 项开始，每一项都等于前两项之和。

    与黄金分割的关系，当 n 趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割 0.618（或者说后一项与前一项的比值小数部分越来越逼近 0.618）。

    斐波那契数列有一些特性，1.当前项的平方与前后项的乘积总是相差 1，正负性跟 n 有关。2.第一项到第 n 项，每项的平方相加等于第 n 项和第 n+1 项的乘积。类似特性还有很多 (opens new window)。

# 迭代求斐波那契数列

/**
 * 迭代求斐波拉契数，迭代方法会比递归方法快，但代码多
 */
export function fibonacciIterative(n: number) {
  if (n < 1) {
    return 0;
  }
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) {
    // n >= 2
    fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 递归求斐波那契数列

/**
 * 递归求斐波拉契数，代码少容易理解，但运行慢耗内存
 * 但es6有尾调用优化能大部分解决消耗问题，可以经常使用递归解决问题
 */
export function fibonacci(n: number): number {
  if (n < 1) {
    return 0;
  }
  if (n <= 2) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 记忆化求斐波那契数列

/**
 * 迭代求斐波拉契数（记忆化，用数组缓存结果），运行较快（但还是比迭代慢）
 */
export function fibonacciMemoization(n: number) {
  if (n < 1) {
    return 0;
  }
  const memo = [0, 1];
  const fibonacciMem = (num: number): number => {
    if (memo[num] != null) {
      return memo[num];
    }
    return (memo[num] = fibonacciMem(num - 1) + fibonacciMem(num - 2));
  };
  return fibonacciMem(n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 尾调用优化

    es2015 有尾调用优化(tail call optimization) (opens new window)，函数内的最后一步操作是调用函数，会通过“跳转命令”而不是“子程序调用”。

    我们把递归改写成尾调用形式，再根据浏览器的要求（有些需要严格模式）就可以完美使用递归了，这样就可以避免栈溢出，相对节省内存。

← 8.树 →