ES6的JavaScript数据结构实现之递归

目的：ES6标准下的JS数据结构的一些实现代码。（作为记录和启发）

内容：递归。（递归会使得操作树和图数据结构变得更简单。所以要理解递归。）（未完成，待继续）

所有源码在我的Github上（如果觉得不错记得给星鼓励我哦）：ES6的JavaScript数据结构实现之递归

一、递归基础应用

1、计算一个数的阶乘

1.1迭代阶乘（循环实现）

 1 function factorialIterative(number) {
 2   if (number < 0 ) {
 3     return undefined;
 4   }
 5   let total = 1;
 6   for (let n = number; n > 1; n--) {
 7     total = total * n ;
 8   }
 9   return total;
10 }
11 
12 console.log(factorialIterative(5)); //120

1.2递归阶乘（使用递归时，要找到原始问题和子问题是什么。例如factorial(5)=5*factorial(4)）

1 function factorial(n) {
2   
3   if (n === 1 || n === 0) {
4     return 1;
5   }
6   return n * factorial(n - 1);
7 }
8 
9 console.log(factorial(5));//120

2、斐波那契数列。（斐波那契数列是另一个可以用递归解决的问题。）

2.1迭代求斐波那契数

 1 function fibonacciIterative(n) {
 2   let fibNMinus2 = 0;
 3   let fibNMinus1 = 1;
 4   let fibN = n;
 5   for (let i = 2; i <= n; i++) {
 6     fibN = fibNMinus1 + fibNMinus2;
 7     fibNMinus2 = fibNMinus1;
 8     fibNMinus1 = fibN;
 9   }
10   return fibN;
11 }
12 
13 console.log(fibonacciIterative(0));
14 console.log(fibonacciIterative(1));
15 console.log(fibonacciIterative(2));
16 console.log(fibonacciIterative(3));
17 console.log(fibonacciIterative(4));

2.2递归求斐波那契数

 1 function fibonacci(n) {
 2   if (n < 1) return 0;
 3   if (n <= 2) return 1;
 4   return fibonacci(n - 1) + fibonacci(n - 2);
 5 }
 6 console.log(fibonacciIterative(0));
 7 console.log(fibonacciIterative(1));
 8 console.log(fibonacciIterative(2));
 9 console.log(fibonacciIterative(3));
10 console.log(fibonacciIterative(4));

2.3记忆化斐波那契数

//注：记忆化是一种保存前一个结果的值的优化技术，类似于缓存。

 1 function fibonacciMemoization(n) {
 2   const memo = [0, 1];
 3   const fibonacci = (n) => {
 4     if (memo[n] != null) return memo[n];
 5     return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
 6   };
 7   return fibonacci(n);
 8 }
 9 console.log(fibonacciMemoization(2));
10 console.log(fibonacciMemoization(3));
11 console.log(fibonacciMemoization(4));