21.递归

[neptoo]

递归简介

函数间接或直接调用自身的一种方法称为递归。

以阶乘为例：

function factorial(n) {
    if (n == 1) return n;
    return n * factorial(n - 1)
}

console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120

斐波那契数列

function fibonacci(n){
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(5)) // 1 1 2 3 5

当执行一个函数的时候，就会创建一个执行上下文，并且压入执行上下文栈，当函数执行完毕的时候，就会将函数的执行上下文从栈中弹出。在上面例子中，JavaScript 会不停的创建执行上下文压入执行上下文栈。

尾递归

• 尾递归是指函数内部的最后一个动作是函数调用自身。该调用的返回值，直接返回给函数。
• 是通过设置一个累加参数，并且每一次都将当前的值累加上去，然后递归调用。

function factorial(n, total) {
    if (n == 1) return total;
    return factorial(n - 1, n * total)
}

console.log(factorial(4, 1)) // 24
// factorial(3, 4) 
// factorial(2, 12) 
// factorial(1, 24)

调用栈不再需要多次对factorial进行压栈处理，因为每一个递归调用都不在依赖于上一个递归调用的值。

原文链接

JavaScript专题之递归

JavaScript中的递归

[neptoo]

题目

1.这是一道大题目，把考点拆成了4个小项；需要侯选人用递归算法实现（限制15行代码以内实现；限制时间10分钟内完成）：查看原题

a) 生成一个长度为5的空数组arr。
b) 生成一个（2－32）之间的随机整数rand。
c) 把随机数rand插入到数组arr内，如果数组arr内已存在与rand相同的数字，则重新生成随机数rand并插入到arr内[需要使用递归实现，不能使用for/while等循环]
d) 最终输出一个长度为5，且内容不重复的数组arr。

解答

// 法一 Github @likeke1997
function buildArr(arr, length, min, max){
  const random = Math.floor(Math.random() * (max - min + 1)) + min;
  if(!arr.includes(random)){ arr.push(random); }
  return arr.length === length ? arr : buildArr(arr, length, min, max);
}
buildArr([], 5, 2, 32);

// 法二 Github @linghucq1
function buildArr(arr, i = 0, min = 2, max = 32){
  var rand = Math.floor(Math.random() * 31) +2;
  if(!arr[length-1]){
    if(!arr.includes(rand)){
      arr.push(rand);
      arr[i++] = rand;
    }
    return buildArr(arr, i);
  }
  return arr;
}
const arr0 = new Array(5);
buildArr(arr0);