递归、遍历、尾递归

[oakland]

之前喜欢用递归的方式处理问题，后来看到一句话：

The old recruiting practice says, "Never hire a developer who computes the factorial using Recursion".

所以又去看了一下 SICP 中递归和尾递归的章节，重新领悟了一番，重新复习了一下递归转遍历

// 题目：斐波那契数列求第n项的值
// 递归的方式是最简单的

// 递归
function fibRecursive(n) {
  if(n === 1) {
    return 1;
  }

  if(n === 2) {
    return 1;
  }

  return fibRecursive(n - 1) + fibRecursive(n - 2)
};

// 能不能用遍历的方式实现呢？
// 遍历
function fibIterative(n) {
  let counter = 2;
  let prev = 1;
  let next = 1;

  while(counter < n) {
    let temp = next;
    next = prev + next
    prev = temp;
    // 下面这样是不是也可以？
    // [prev, next] = [next, prev+next]
    counter++;
  }

  return next;
};

// 能不能用尾递归的方式实现呢？
function fibIterativeTail(n) {
  function fibIter(prev, next, counter) {
    if(counter >= n) return next;
    return fibIter(next, prev + next, ++counter);
  }
  return fibIter(0, 1, 1);
}

console.log(fibRecursive(20));
console.log(fibIterative(20));
console.log(fibIterativeTail(20));

// 树形结构同样可以用递归和遍历两种方式实现
const root = {
  name: 'a',
  children: [
    {
      name: 'b',
      children: [
        {
          name: 'd',
          children: []
        },
        {
          name: 'e',
          children: []
        }
      ]
    },
    {
      name: 'c',
      children: [
        {
          name: 'f',
          children: []
        },
        {
          name: 'g',
          children: []
        }
      ]
    }
  ]
}

function traverseRecursive() {
  console.log(root.name);
  root.children.forEach(child => traverseRecursive(child));
}

function traverseIterative(root) {
  const stack = [];
  stack.push(root);
  while(stack.length) {
    const node = stack.pop();
    console.log(node.name);
    node.children.forEach(child => stack.unshift(child));
  }
}

traverseRecursive(root);
traverseIterative(root);

// 阶乘用递归和遍历两种方式实现
function factorialRecursive(n) {
  if(n === 1) return n;
  return n * factorialRecursive(n - 1)
}

function factorialIterative(n) {
  let result = n;
  while(n > 1) {
    result = result * (n - 1);
    n--;
  }
  return result;
}

factorialRecursive(5);
factorialIterative(5);

什么是尾递归

对于如何定义尾递归，其实在我的脑海里有个心里模型，但是我又很难精确地描述出来。但是看到知乎有个回答说的特别好，一针见血。

尾递归，比线性递归多一个参数，这个参数是上一次调用函数得到的结果；

所以，关键点在于，尾递归每次调用都在收集结果，避免了线性递归不收集结果只能依次展开消耗内存的坏处。

递归快排转遍历

大部分的递归转遍历用的都是 factorial 的例子，还有一部分用的是 fibnacci，这两个在 sicp 中都有非常好的论述。但是很少有人用其他的递归来做示例，这个问答里有一个回答用的就是快排这个递归转遍历，感觉让人眼前一亮啊。

[oakland]

在查找相关相关资料的时候，还看到了这个网站replaceRecursionWithIteration，可以看看这个主页，感觉好像就是重构的作者自己写的页面，应该还可以吸取一些养分

[oakland]

关于递归转尾递归和遍历，应该也算一个主题，目前就研究到这里，感觉也够用了，搜了一些资料放在我的 oneTab 里了，后续想研究再拿出来看看。

[oakland]

尾递归的本质就是后面的项是由前面的项推演出来的，尾递归的初始参数是前面推演的 n 项和从推演开始的序号 n，比如 sicp 中 exercise 1.11 的例子就是 iter(2, 1, 0, 2)，前三个参数是推演的起始值：2、1、0，最后一项 2 是计数器，counter 表示从满足条件的最后一项开始，也就是 2。然后第 3 项就是可以从前 3 项推演出来。