递归

发表于 | 分类于 | 评论数： | 阅读次数：

推荐注册返佣金的这个功能我想你应该不陌生吧？现在很多 App 都有这个功能。这个功能中，用户 A 推荐用户 B 来注册，用户 B 又推荐了用户 C 来注册。我们可以说，用户 C 的“最终推荐人”为用户 A，用户 B 的“最终推荐人”也为用户 A，而用户 A 没有“最终推荐人”。给定一个用户 ID，如何查找这个用户的“最终推荐人”？

递归是一种应用非常广泛的算法（或者编程技巧）。很多数据结构和算法的编码实现都要用到递归，比如 DFS 深度优先搜索、前中后序二叉树遍历等等。

本文将主要分成三个部分，从理解递归，到经典案例，最后实际业务中的使用。

生活中的递归例子

周末你带着女朋友去电影院看电影，女朋友问你，咱们现在坐在第几排啊？电影院里面太黑了，看不清，没法数，现在你怎么办？别忘了你是程序员，这个可难不倒你，递归就开始排上用场了。于是你就问前面一排的人他是第几排，你想只要在他的数字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也问他前面的人。就这样一排一排往前问，直到问到第一排的人，说我在第一排，然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排，于是你就知道答案了。这就是一个非常标准的递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子，我们用递推公式将它表示出来就是这样的：

1
f(n)=f(n-1)+1 其中，f(1)=1

f(n) 表示你想知道自己在哪一排，f(n-1) 表示前面一排所在的排数，f(1)=1 表示第一排的人知道自己在第一排。有了这个递推公式，我们就可以很轻松地将它改为递归代码，如下：

1
2
3
4
int f(int n) {
  if (n == 1) return 1;
  return f(n-1) + 1;
}

递归需要满足的三个条件

一个问题的解可以分解为几个子问题的解

何为子问题？子问题就是数据规模更小的问题。比如，前面讲的电影院的例子，你要知道，“自己在哪一排”的问题，可以分解为“前一排的人在哪一排”这样一个子问题。

这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样

比如电影院那个例子，你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一样的。

存在递归终止条件

把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。还是电影院的例子，第一排的人不需要再继续询问任何人，就知道自己在哪一排，也就是 f(1)=1，这就是递归的终止条件。

如何编写递归代码

写递归代码最关键的是写出递推公式，找到终止条件，剩下将递推公式转化为代码就很简单了。

假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？如果有 7 个台阶，你可以 2，2，2，1 这样子上去，也可以 1，2，1，1，2 这样子上去，总之走法有很多，那如何用编程求得总共有多少种走法呢？我们仔细想下，实际上，可以根据第一步的走法把所有走法分为两类，第一类是第一步走了 1 个台阶，另一类是第一步走了 2 个台阶。所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法 加上先走 2 阶后，n-2 个台阶的走法。用公式表示就是：

1
f(n) = f(n-1)+f(n-2)

有了递推公式，递归代码基本上就完成了一半。我们再来看下终止条件。当有一个台阶时，我们不需要再继续递归，就只有一种走法。所以 f(1)=1。这个递归终止条件足够吗？我们可以用 n=2，n=3 这样比较小的数试验一下。n=2 时，f(2)=f(1)+f(0)。如果递归终止条件只有一个 f(1)=1，那 f(2) 就无法求解了。所以除了 f(1)=1 这一个递归终止条件外，还要有 f(0)=1，表示走 0 个台阶有一种走法，不过这样子看起来就不符合正常的逻辑思维了。所以，我们可以把 f(2)=2 作为一种终止条件，表示走 2 个台阶，有两种走法，一步走完或者分两步来走。所以，递归终止条件就是 f(1)=1，f(2)=2。这个时候，你可以再拿 n=3，n=4 来验证一下，这个终止条件是否足够并且正确。我们把递归终止条件和刚刚得到的递推公式放到一起就是这样的：

1
2
3
f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)

有了这个公式，我们转化成递归代码就简单多了。最终的递归代码是这样的：

1
2
3
4
5
function f(n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  return f(n - 1) + f(n - 2);
}

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

计算机擅长做重复的事情，所以递归正合它的胃口。而我们人脑更喜欢平铺直叙的思维方式。当我们看到递归时，我们总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去。

对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。很多时候，我们理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。那正确的思维方式应该是怎样的呢？

如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。

递归代码虽然简洁高效，但是，递归代码也有很多弊端。比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等，所以，在编写递归代码的时候，一定要控制好这些副作用。

常见案例

求和

1
2
3
4
function sum(n) {
  if (n === 1) return 1;
  return sum(n - 1) + n;
}

求阶乘

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

斐波拉契数列

斐波拉契数列（当前的值等于前两个数的和）：{1，1， 2， 3， 5， 8， 13， 21， 34 …}

递归公式：fun(n) = fun(n-1) + fun(n-2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function fib(n) {
  if (n === 1 || n === 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

// 非递归方法
function fib(n) {
  let a = 0;
  let b = 1;
  let c = a + b;
  for (let i = 3; i < n; i++) {
    a = b;
    b = c;
    c = a + b;
  }
  return c;
}

深拷贝

1
2
3
4
5
6
7
8
9
10
11
function clone(o) {
  var temp = {}
  for (var key in o) {
    if (typeof o[key] == 'object') {
      temp[key] = clone(o[key])
    } else {
      temp[key] = o[key]
    }
  }
  return temp
}

汉诺塔

汉诺塔

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
function move(n, a, b, c) {
  if (n === 1) {
    console.log(a + "-->" + c);
    return;
  }
  move(n - 1, a, c, b);
  console.log(a + "-->" + c);
  move(n - 1, b, a, c);
}

// 测试：
move(4, "A", "B", "C");
// 结果如下：
// A-->B
// A-->C
// B-->C
// A-->B
// C-->A
// C-->B
// A-->B
// A-->C
// B-->C
// B-->A
// C-->A
// B-->C
// A-->B
// A-->C
// B-->C

详细介绍：https://www.cnblogs.com/HeZhengfa/p/10245109.html，https://blog.csdn.net/xiaoxiao520c/article/details/77620583

业务场景使用

Open Api 应用接口返回字段排序

接口返回值

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
37
38
39
40
41
42
43
// 对象比较函数
function createComparisonFunction(propertyName) {
  return function (object1, object2) {
    var value1 = object1[propertyName];
    var value2 = object2[propertyName];
    if (value1 < value2) {
      return -1;
    } else if (value1 > value2) {
      return 1;
    } else {
      return 0;
    }
  };
}
/**
 * 对象数组根据某个属性排序
 * @param {Array} data 待排序源数据
 * @param {String} propertyName 排序依据的属性名
 */
function sortArray(data, propertyName) {
  // children执行递归
  const doRecursion = (array, propertyName) => {
    if (array && array.length > 0) {
      for (var i in array) {
        let item = array[i];
        let children = item.children;
        if (children && children.length >= 1) {
          item.children = children.sort(createComparisonFunction(propertyName));
          doRecursion(children, propertyName);
        }
      }
    }

    return array;
  };
  // 第一层排序
  let firstLevelData = data.sort(createComparisonFunction(propertyName));

  return doRecursion(firstLevelData, propertyName);
}

// 使用：
// let sortedResult = sortArray(data, 'priority');

类目与面包屑联动

search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 查找类目对象关系链
function findChain(array = [], keyName, keyValue, chainArray = []) {
  for (let i = 0; i < array.length; i++) {
    const item = array[i];

    // chainArray是引用类型，这里要复制值；
    let temp = [...chainArray];
    const { children, ...other } = item;
    temp.push(other);
    if (item[keyName] === keyValue) {
      return temp;
    }
    if (item.children && item.children.length > 0) {
      let result = findChain(item.children, keyName, keyValue, temp);
      if (result) {
        return result;
      }
    }
  }
}

// 使用：
// let result = findChain(categoryList, "catId", "LgUpKAfqNYBr");

附录

附录一

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
const data = [
  {
    id: 10651,
    scope: "response",
    type: "Object",
    pos: 3,
    name: "businessData",
    rule: "",
    value: "",
    description: "Specific business data",
    parentId: -1,
    priority: 3,
    interfaceId: 471,
    creatorId: 1,
    moduleId: 231,
    repositoryId: 31,
    required: false,
    createdAt: "2021-04-19T01:17:08.000Z",
    updatedAt: "2021-05-26T03:25:21.000Z",
    deletedAt: null,
    depth: 1,
    children: [
      {
        id: 10661,
        scope: "response",
        type: "String",
        pos: 3,
        name: "businessMessage",
        rule: "",
        value: "000000",
        description: "Message for business results",
        parentId: 10651,
        priority: 4,
        interfaceId: 471,
        creatorId: 1,
        moduleId: 231,
        repositoryId: 31,
        required: false,
        createdAt: "2021-04-19T01:17:08.000Z",
        updatedAt: "2021-05-26T03:25:21.000Z",
        deletedAt: null,
        depth: 2,
        children: [],
      },
      {
        id: 10671,
        scope: "response",
        type: "String",
        pos: 3,
        name: "businessStatus",
        rule: "",
        value: "Success",
        description: "Status code for business results",
        parentId: 10651,
        priority: 5,
        interfaceId: 471,
        creatorId: 1,
        moduleId: 231,
        repositoryId: 31,
        required: false,
        createdAt: "2021-04-19T01:17:08.000Z",
        updatedAt: "2021-05-26T03:25:21.000Z",
        deletedAt: null,
        depth: 2,
        children: [],
      },
      {
        id: 10681,
        scope: "response",
        type: "Array",
        pos: 3,
        name: "data",
        rule: "",
        value: "",
        description: "Business results",
        parentId: 10651,
        priority: 6,
        interfaceId: 471,
        creatorId: 1,
        moduleId: 231,
        repositoryId: 31,
        required: false,
        createdAt: "2021-04-19T01:17:08.000Z",
        updatedAt: "2021-05-26T03:25:21.000Z",
        deletedAt: null,
        depth: 2,
        children: [
          {
            id: 10701,
            scope: "response",
            type: "String",
            pos: 3,
            name: "categoryId",
            rule: "",
            value: "eFqZvbDJqJVP",
            description: "Category ID",
            parentId: 10681,
            priority: 8,
            interfaceId: 471,
            creatorId: 1,
            moduleId: 231,
            repositoryId: 31,
            required: false,
            createdAt: "2021-04-19T01:17:08.000Z",
            updatedAt: "2021-05-26T03:25:21.000Z",
            deletedAt: null,
            depth: 3,
            children: [],
          },
          {
            id: 10711,
            scope: "response",
            type: "String",
            pos: 3,
            name: "categoryName",
            rule: "",
            value: "Apparel & Accessories > Clothing",
            description: "Category Name",
            parentId: 10681,
            priority: 9,
            interfaceId: 471,
            creatorId: 1,
            moduleId: 231,
            repositoryId: 31,
            required: false,
            createdAt: "2021-04-19T01:17:08.000Z",
            updatedAt: "2021-05-26T03:25:21.000Z",
            deletedAt: null,
            depth: 3,
            children: [],
          },
          {
            id: 10721,
            scope: "response",
            type: "Boolean",
            pos: 3,
            name: "leaf",
            rule: "",
            value: "false",
            description: "Is it a leaf category",
            parentId: 10681,
            priority: 10,
            interfaceId: 471,
            creatorId: 1,
            moduleId: 231,
            repositoryId: 31,
            required: false,
            createdAt: "2021-04-19T01:17:08.000Z",
            updatedAt: "2021-05-26T03:25:21.000Z",
            deletedAt: null,
            depth: 3,
            children: [],
          },
          {
            id: 10731,
            scope: "response",
            type: "Number",
            pos: 3,
            name: "level",
            rule: "",
            value: "4",
            description: "Category Level",
            parentId: 10681,
            priority: 11,
            interfaceId: 471,
            creatorId: 1,
            moduleId: 231,
            repositoryId: 31,
            required: false,
            createdAt: "2021-04-19T01:17:08.000Z",
            updatedAt: "2021-05-26T03:25:21.000Z",
            deletedAt: null,
            depth: 3,
            children: [],
          },
          {
            id: 10741,
            scope: "response",
            type: "String",
            pos: 3,
            name: "parentCategoryId",
            rule: "",
            value: "eFqZvbDJqJVP",
            description: "Parent Category ID",
            parentId: 10681,
            priority: 2,
            interfaceId: 471,
            creatorId: 1,
            moduleId: 231,
            repositoryId: 31,
            required: false,
            createdAt: "2021-04-19T01:17:08.000Z",
            updatedAt: "2021-05-26T03:25:21.000Z",
            deletedAt: null,
            depth: 3,
            children: [],
          },
        ],
      },
    ],
  },
  {
    id: 10691,
    scope: "response",
    type: "String",
    pos: 3,
    name: "responseCode",
    rule: "",
    value: "000000",
    description: "Response Code  000000-Success、999999-Fail",
    parentId: -1,
    priority: 1,
    interfaceId: 471,
    creatorId: 1,
    moduleId: 231,
    repositoryId: 31,
    required: false,
    createdAt: "2021-04-19T01:17:08.000Z",
    updatedAt: "2021-05-26T03:25:21.000Z",
    deletedAt: null,
    depth: 1,
    children: [],
  },
  {
    id: 10751,
    scope: "response",
    type: "String",
    pos: 3,
    name: "responseMessage",
    rule: "",
    value: "Success",
    description: "Response Message",
    parentId: -1,
    priority: 2,
    interfaceId: 471,
    creatorId: 1,
    moduleId: 231,
    repositoryId: 31,
    required: false,
    createdAt: "2021-04-19T01:17:08.000Z",
    updatedAt: "2021-05-26T03:25:21.000Z",
    deletedAt: null,
    depth: 1,
    children: [],
  },
];
let sortedResult = sortArray(data, "priority");
console.log("result", JSON.stringify(sortedResult));

附录二

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
let categoryList = [
  {
    catId: "eAfpULBEoStM",
    catName: "Outdoor",
    catUrl:
      "https://www.doba.com/category/eAfpULBEoStM/dropshipping-outdoor.html",
    children: [
      {
        catId: "jZfKpLqEzIuW",
        catName: "Outdoor Furniture",
        catUrl:
          "https://www.doba.com/category/jZfKpLqEzIuW/dropshipping-outdoor-furniture.html",
        children: [
          {
            catId: "ZqKUpAfJNGOL",
            catName: "Patio Tables",
            catUrl:
              "https://www.doba.com/category/ZqKUpAfJNGOL/dropshipping-patio-tables.html",
            children: [
              {
                catId: "LgUpKAfqNYBr",
                catName: "Bar Tables",
                catUrl:
                  "https://www.doba.com/category/LgUpKAfqNYBr/dropshipping-bar-tables.html",
                children: [],
              },
            ],
          },
        ],
      },
    ],
  },
  {
    catId: "cgfUKVBkWdRh",
    catName: "sports",
    catUrl:
      "https://www.doba.com/category/cgfUKVBkWdRh/dropshipping-sports.html",
    children: [
      {
        catId: "gPpUKLfuBTyC",
        catName: "Airsoft",
        catUrl:
          "https://www.doba.com/category/gPpUKLfuBTyC/dropshipping-airsoft.html",
        children: [
          {
            catId: "aZKpAqfFMabh",
            catName: "Batteries",
            catUrl:
              "https://www.doba.com/category/aZKpAqfFMabh/dropshipping-batteries.html",
            children: [],
          },
        ],
      },
      {
        catId: "UmpfULKPWANr",
        catName: "Cheerleading",
        catUrl:
          "https://www.doba.com/category/UmpfULKPWANr/dropshipping-cheerleading.html",
        children: [
          {
            catId: "ZvUpAgfFNLQr",
            catName: "Mascot Costumes",
            catUrl:
              "https://www.doba.com/category/ZvUpAgfFNLQr/dropshipping-mascot-costumes.html",
            children: [],
          },
        ],
      },
      {
        catId: "OLAUKgfkrsAh",
        catName: "Snowmobiling",
        catUrl:
          "https://www.doba.com/category/OLAUKgfkrsAh/dropshipping-snowmobiling.html",
        children: [
          {
            catId: "kopKAVUPaknM",
            catName: "Parts",
            catUrl:
              "https://www.doba.com/category/kopKAVUPaknM/dropshipping-parts.html",
            children: [
              {
                catId: "dPpfUVAwHOCM",
                catName: "Handlebars",
                catUrl:
                  "https://www.doba.com/category/dPpfUVAwHOCM/dropshipping-handlebars.html",
                children: [],
              },
            ],
          },
        ],
      },
      {
        catId: "foApfBUPhiIr",
        catName: "Water sports",
        catUrl:
          "https://www.doba.com/category/foApfBUPhiIr/dropshipping-water-sports.html",
        children: [
          {
            catId: "VvpAfgUPlBpM",
            catName: "Kneeboarding",
            catUrl:
              "https://www.doba.com/category/VvpAfgUPlBpM/dropshipping-kneeboarding.html",
            children: [
              {
                catId: "cBfApgKcSyUC",
                catName: "Accessories",
                catUrl:
                  "https://www.doba.com/category/cBfApgKcSyUC/dropshipping-accessories.html",
                children: [],
              },
            ],
          },
        ],
      },
    ],
  },
  {
    catId: "gdAfKUpRDHjr",
    catName: "shoe display",
    catUrl:
      "https://www.doba.com/category/gdAfKUpRDHjr/dropshipping-shoe-display.html",
    children: [],
  },
];
let result = findChain(categoryList, "catId", "LgUpKAfqNYBr");
console.log("result", result);
// [
//   {
//     catId: 'eAfpULBEoStM',
//     catName: 'Outdoor',
//     catUrl: 'https://www.doba.com/category/eAfpULBEoStM/dropshipping-outdoor.html'
//   },
//   {
//     catId: 'jZfKpLqEzIuW',
//     catName: 'Outdoor Furniture',
//     catUrl: 'https://www.doba.com/category/jZfKpLqEzIuW/dropshipping-outdoor-furniture.html'
//   },
//   {
//     catId: 'ZqKUpAfJNGOL',
//     catName: 'Patio Tables',
//     catUrl: 'https://www.doba.com/category/ZqKUpAfJNGOL/dropshipping-patio-tables.html'
//   },
//   {
//     catId: 'LgUpKAfqNYBr',
//     catName: 'Bar Tables',
//     catUrl: 'https://www.doba.com/category/LgUpKAfqNYBr/dropshipping-bar-tables.html'
//   }
// ]

参考

https://time.geekbang.org/column/article/41440

https://juejin.cn/post/6844904014207795214