递归转尾递归

尾递归 == 伪递归, 只有递, 没有归…

不是所有的递归都可以转成尾递归, 例如回溯的递归实现就不行, 因为回溯是每一次执行都有 n (n > 1) 种状态, 即在递归的每一层都会有多个递归调用.

递归 (回溯除外) 是一种特殊的隐式图 DFS, 其每一次状态转换都只有一条路径.

通常, 如果规模为 n 的问题, 可由 n 的子集 (n-1, n/2 等) 的解推导出时, 考虑使用递归.

本质是数学中的归纳法, 即证明一个规模为 n 的问题, 分下面两步:

1. 证明当 n=1 时命题成立
2. 假设命题对于 n 成立, 证明在此假设下, 命题对于 n+1 也成立

关键就是找状态映射 (n -> n+1).

其它的可优化递归大致分为两种:

• 无返回值的递归
• 有返回值的递归

无返回值的递归转尾递归很简单, 就是调下位置, 参考二叉树的前中后遍历.

而在有返回值的递归中, 当前层的执行需要用到余下层递归的状态 (返回值):

// 求 x 的 n 次方, 非递归
func expr(x, n int) int {
  result = 1
    for i := 0; i < n; i++ {
    result = result * x
    }
  return result
}

// 递归
func expr_2(x, n int) int {
  if n == 0 {
    return 1
  }
  return x * expr_2(x, n - 1)
}

可以看到 expr_2(x, n) 的解依赖于下一层调用 expr_2(x, n - 1) 的状态 (返回值).

尾递归优化的方法就是打破这种依赖关系:

// 尾递归优化, 关键在参数上
func expr_3(x, n, result int) int {
  if n == 0 {
    return result
  }
  return expr_3(x, n - 1, result * x)
}

通过对比可以看到, 在正常递归版本中, n 的解依赖于 n-1 的解, 最终结果是在”归”的过程中累积; 而在尾递归优化中, 是 n-1 的解依赖于 n 的解, 最终结果是在”递”的过程中累积. 这也是尾递归 == 伪递归的原因.

不是所有的状态 (返回值) 都需要移到参数中, 只考虑被依赖项.