递归

什么是递归


函数递归就是在函数中调用自身

递归的能力在于用有限的语句来定义对象的无线集合

递归需要有边界条件、递归前进段和递归返回段
当边界条件不满足时，递归前进
当边界条件满足时，递归返回

function doA(n) {
    ...
    doA(n-1);
}

例子

想象一下，你是一家公司的话务员。
由于公司业务繁忙，你的座机连接多条线路，每条线路上对应一个接收器按钮，当有来电时，该按钮闪烁。
你到达公司开始工作时，发现有四条线对应按钮正在闪烁，你需要接听这些电话。

你接听线路一，并告诉他”请稍等”；然后接听线路二，并告诉他”请稍等”；接着，接听线路三，告诉他”请稍等”；最后接听电话四，并与其通话交谈。
当你结束了线路四的通话后，你回过头来接听线路三，当你结束与线路三通话后，你接听了线路二，最后你接听了线路一

这个例子中每一通电话就像某函数中的一个递归调用。
当你接到一个电话不能立即处理时，这个电话将被搁置；当你有一个不需要立即触发的函数调用时，他将停留在调用栈上。
当你可以接听这个电话时，这个线路会被接通；当你的代码能够触发一个函数调用时，它会从调用栈中弹出

单你看到代码有些发懵时，请回想一下这个比喻



常见递归操作


递归求和（1 + 2 + 3 … + n 的值）

function sum(d) {
  if (d <= 1) {
    return 1;
  } else {
    return sum(d - 1) + d;
  }
}

/* 执行过程 */

sum(4); //递归前进
4 + sum(3); //递归前进
4 + (3 + sum(2)); //递归前进
4 + (3 + (2 + sum(1))); //递归前进
4 + (3 + (2 + (1 + sum(0)))); //递归返回
4 + (3 + (2 + (1 + 0))); //递归返回
4 + (3 + (2 + 1)); //递归返回
4 + (3 + 3); //递归返回
4 + 6; //递归返回
10; //递归返回


递归实现阶乘函数（1 * 2 * 3 … * n 的值）

function factorial(d) {
  if (d <= 1) {
    return 1;
  } else {
    return factorial(d - 1) * d;
  }
}

先递进，在回归



斐波那契数列

1，1，2，3，5，8，13……即从第三项起，每一项的值是前两项值的和。求第 n 项的值。

function fibona(n) {
  if (n === 1 || n === 2) {
    //如果求第一项或者第二项，则直接返回1
    return 1;
  } else {
    //否则的话，返回前两项的和
    return fibona(n - 1) + fibona(n - 2);
  }
}
console.log(fibona(10));

首先设置终止条件，n=1 或 n=2 时返回 1，否则就重新调用自身

即第 n 项的值是第 n-1 和 n-2 的和，同理可得第 n-1 项的值是 n-1-1 和 n-1-2

通过递归，最终转化成了 f(1)和 f(2)的值相加


递归处理数据

var tree = {
  name: "电脑",
  children: [
    {
      name: "F盘",
      children: [
        {
          name: "照片",
          children: [],
        },
        {
          name: "文件",
          children: [
            {
              name: "工作文件",
              children: [
                {
                  name: "报告",
                  children: [],
                },
              ],
            },
          ],
        },
      ],
    },
    {
      name: "E盘",
      children: [
        {
          name: "视频",
          children: [
            {
              name: "js教程",
              children: [],
            },
          ],
        },
      ],
    },
  ],
};

let i = 0;
function dg(d) {
  if (d.children && d.children.length > 0) {
    let child = [];
    d.children.map((e, e1) => {
      child.push(dg(e));
    });
    i++;
    return {
      id: i,
      name: d.name,
      child,
    };
  } else {
    i++;
    return {
      name: d.name,
      child: [],
      id: i,
    };
  }
}
console.log(dg(tree));


小结



参见