0%

递归 & 回调

发表于 更新于 分类于

严于律己，宽以待人。

真的想不起来以前是怎么学习的，现在是学什么忘什么，好沮丧。

递归和回调明明都是以前学过的，可是书到用时方恨少啊。

递归

别说曾经，我现在也还迷递归。我只知道自己调用自己，再给个结束条件就算完了。可是当我自己着手写递归的时候，就会遇到很多很多问题。

我曾在很多地方找过递归的解释

[知乎]什么是递归

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。递归函数不能定义为内联函数。

数学定义: 对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

递归的执行形状看起来就像这样，从 1 到 5，再从 5 到 1.

1
2
3
4
5
6
7
8
9
1
  2
    3
      4
        5
      4
    3
  2
1

或许实在上高中的时候，我们就该学过斐波那契数列，时隔四年，也实在是想不起来，只记得定义是这样的：设有 f(x) 在取值范围内从第三项开始，每一项都是前两项的和。用数学表达式可以这样写 f(x) = f(x-1) + f(x-2)。

斐波那契可以简单表示为：[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …]

这样的问题，通常使用递归就很简单了，但是，不会递归的我们只能用循环了。

1
2
3
4
5
6
7
8
function fb(num) {
  let arr = [1, 1];
  if (num.length <= 2) return arr
  for(let i = 2; i <= num; i++) {
    arr[i] = arr[i-1] + arr[i-2]
  }
  return arr
}

这个函数写出来的瞬间，我怎么觉得我凉了呢？？？这个函数其实很简单，不过就是把第三项之后的值通过计算存入数组。但是我们需要的只是数组最后一个值，所以这样就显得累赘。

后来，学了递归之后，就可以开始使用递归写了，就像一开始所说，调用当前函数不断执行下去，直到停止条件后开始一层一层返回数据。

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

回调

回调跟递归有一个类似的地方，就是在函数内执行一个函数。但是递归调用的是自己，而回调是调用其他函数。

1
2
3
4
5
6
7
8
function fun(cb) {
  let name = "sheeep";
  cb(name)
}
function cb(name) {
  console.lob(name)
}
fun(cb) // "sheeep"

其中回调函数也可以用匿名函数，箭头函数表示。

我们常见的许多js原生函数都是需要回调函数来执行的比如：

1
2
3
4
5
let arr = [1,2,3,4,5,6,7,8,9]
let newArr = arr.map((item) => {
  return item*2
})
consoel.log(newArr) // [2, 4, 6, 8, 10, 12, 14, 16, 18]

关于尾递归和尾调用优化

“尾”这个字突出了它的位置。关于这个函数的位置就是在函数的最尾部。

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

factorial(5) // 120

尾调用或者尾递归都必须是在最尾部，如上面例子不算是尾递归，因为在 return 之后还会执行 n * factorial(n - 1)。

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用帧，因为调用位置，内部变量等信息不会再使用了，直接用内函数的调用帧取代外层函数即可

尾递归的优化，每次执行时栈内只有一个帧，将大大的节省内存。

参考

尾调用优化-阮一峰