愿卿一路好风景

此心安处是吾乡

0%

尾递归

发表于

一、递归

在函数的内部，可以调用其它的函数，如果一个函数在内部调用自身，这个函数就是递归函数

1
2
3
4
5
6
7
function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

二、尾递归

在函数的尾部直接调用自身。在递归调用的过程中系统为每一层的返回点、局部变量等开辟了栈来存储，递归次数过多容易造成栈溢出。而采用尾递归时，函数所有的递归调用都出现在函数的末尾，只存在一个调用记录，所以永远不会发生栈溢出错误。

通常的递归

1
2
3
4
5
6
7
8
9
function factorial(n) {
  if (n === 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(3)); //6

尾递归

尾递归一般需要初始化一个参数

1
2
3
4
5
6
7
8
9
function factorial(n, init = 1) {
  if (n === 1) {
    return init; //返回的条件变了
  } else {
    return factorial(n - 1, init * n);
  }
}

console.log(factorial(3)); //6

三、应用场景

数组求和

1
2
3
4
5
6
7
8
9
function sumArray(arr, total = 0) {
 if (arr.length === 0) {
  return total;
 }
 return sumArray(arr, total + arr.pop());
}

let arr = [1, 3, 4, 5];
console.log(sumArray(arr));

求斐波那契数列

1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N* ）

正常递归

1
2
3
4
5
6
7
8
9
10
11
12
13
let a = 1; //相当与第n-2的值
let b = 1; //相当与第n-1的值
let sum = 1; //相当与前两项的和,也是n的值
function fn(n) {
  if (n < 3) {
    sum = 1;
  }
  for (i = 3; i <= n; i++) {
    return fn(n - 2) + fn(n - 1);
  }
  return sum;
}
console.log(fn(8)); //21

尾递归

1
2
3
4
5
6
7
8
function factorial2(n, start = 1, total = 1) {
  if (n <= 2) {
    return total;
  } else {
    return factorial2(n - 1, total, start + total);
  }
}
console.log(factorial2(4)); //3

数组扁平化

1
2
3
4
5
6
7
8
9
10
11
12
let arr = [1, 2, 3, [4, 5, 6, [7, 8, 9]]];
function flat(arr, result = []) {
  arr.forEach((value) => {
    if (Array.isArray(value)) {
      result = result.concat(flat(value, []));
    } else {
      result.push(value);
    }
  });
  return result;
}
console.log(flat(arr)); //[1, 2, 3, 4, 5,6, 7, 8, 9]

数组对象格式化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//数组对象格式化
let obj = {
  a: '1',
  b: {
    c: '2',
    D: {
      E: '3',
    },
  },
};

function nameTo_(object) {
  let regObj = new RegExp('([A-Z]+)', 'g');
  for (let i in object) {
    if (object.hasOwnProperty(i)) {
      let temp = object[i];
      if (regObj.test(i.toString())) {
        temp = object[
          i.replace(regObj, function (result) {
            return '_' + result.toLowerCase();
          })
        ] = object[i];
        delete object[i];
      }
      if (
        typeof temp === 'object' ||
        Object.prototype.toString.call(temp) === '[object Array]'
      ) {
        nameTo_(temp);
      }
    }
  }
  return object;
}

console.log(nameTo_(obj));