第二天：递归 & 尾递归

学生：早啊方，今天讲什么？

方：今天讲递归和尾递归吧

学生：数据不可变什么时候讲呀？

方：不急，数据不可变是贯穿始终的，不用特别去讲它。

学生：哦……

方：我先写一个递归形式的阶乘：

f = n => {
  if(n<=1) {
    return 1
  } else {
    return n * f(n-1)
  } 
}

然后用「代入法」来计算一下 f(4)：

f(4) 
= 4 * f(3)
= 4 * (3 * f(2))
= 4 * (3 * (2 * f(1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24

注意计算的「形状」，看起来像是一个大于号（>）：

方：先递进，后回归，这就是递归，英文叫做 recursion。

学生：原来还可以这么理解递归。那我可不可以认为：「递」是调用栈压栈的过程，「归」是弹栈的过程。

方：可以，但不够全面，我之前说过，有些语言是没有调用栈的，所以压栈弹栈只是递归的一种实现方式而已，尽管这种方式很主流。

学生：那伪递归是怎么回事呢？

方：还是先给例子，比阶乘还简单

print = (n) => {
  if(n===0){return}
  console.log(n)
  return print(n-1) // 此处 return 可以省略不写，因为没有返回值
}

然后使用「代入法」来计算 print(4)：

print(4)
= print(3) 
= print(2) 
= print(1) 
= 结束