递归(Recursion)

定义：

函数自身直接或间接调用自身，是一种常用的变成技巧。

生活中的递归现象：

• 从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。
  • 老和尚讲：从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。
    • 老和尚讲：从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。
    • …

• GNU
  • GNU is Not Unix.
  • GNU is Not Unix is Not Unix.
    • Gnu is Not Unix isNot Unix.
      • Gnu is Not Unix is Not Unix is Not Unix.
        • …

• 假设A坐在电影院，想知道自己坐在第几排。
  • A懒得数数，他就问他前边的B坐在那一排。 B的排数 + 1 = A的排数
    • B也懒得数数，他就问他前边的C坐在那一排。 C的排数 + 1 = B的排数
      • C也懒得数数，他就问他前边的C坐在那一排。 D的排数 + 1 = C的排数
        • D也懒得数数，他就问他前边的C坐在那一排。 E的排数 + 1 = D的排数
          • …
            • 直到第一排，说我在第一排
          • …
        • D就知道了, D的排数 = E的排数 + 1
      • C也知道了， C的排数 = D的排数 + 1
    • B也知道了， B的排数 = C的排数 + 1
  • A也知道了，A的排数 = B的排数 + 1

函数的调用过程：

函数的调用过程，就是讲函数依次入栈，执行完毕的函数出栈。

函数的递归调用过程：

• 如果函数调用没有终止，则会一直消耗栈空间
  • 最终导致栈溢出 (StackOverflow)
• 所以必须有明确结束递归的条件
  • 也叫递归边界条件，递归基

递归的基本思想

• 拆解问题
  • 把规模大的问题拆解成规模小的同类型问题
  • 规模较小的问题，又能不断拆解成更小的问题
  • 规模小到一定程度，可以直接求出它的解
• 求解
  • 由规模小的问题得出规模大的问题的解
  • 由较大规模的解不断的出更大规模的解
  • 最终得出原问题的解
• 凡是可以使用上述思路解决的问题都可以使用递归
  • 很多链表，二叉树相关的问题都可以使用递归来解决
    • 因为链表，二叉树本身就是递归的结构(链表中包含链表，二叉树中包含二叉树)

递归的使用套路

• 明确函数的功能
  • 先不要去考虑函数中代码如何实现，首先先搞清楚这个函数是做什么的，能完成什么功能。
• 明确原问题和子问题的关系
  • 寻找 f(n) 和 f(n-1) 的关系
• 明确递归基(边界条件)
  • 递归过程中，子问题规模在不断减小，当减小到一定程度，可以直接求出子问题的解
  • 寻找递归基，相当于找最小的子问题的答案。

尾调用(Tail Call)

• 尾调用 ： 一个函数最后一个动作是调用函数
  • 如果一个函数最后一个动作是调用自身，成为尾递归，是尾调用的特殊情况
• 一些编译器，对尾调用进行优化，以达到节省栈空间的目的。

尾调用优化(Tail Call Optimization)

• 尾调用优化，也叫尾调用消除
  • 如果当前栈帧上的局部变量等都不需要了，当前栈帧经过适当的改变后可以直接当作被尾调用函数的栈帧使用，然后程序可以jump到被尾调用的函数代码。
  • 生成栈帧改变代码以及jump，被称为尾调用消除或尾调用优化
• 消除尾递归里的尾调用比消除一般函数里的尾调用简单的多
  • 因为尾递归 每次调用函数，栈帧都一致，不会变化。
  • 所以我们在学递归代码时，要尽量使用尾递归。