2.自顶向下和自底向下-灵析社区

2.1使用「递归」与「循环」实现的求阶乘函数对比

我们实现一个函数，输入 n ，输出 n 的阶乘。为了简化描述，我们不考虑输入为负整数，且输出发生整型溢出的情况。也就是说，我们假设输入是合法的，并且计算阶乘得到的结果的整数在 32 位整型范围之内。

使用递归计算 5!

代码如下：

Java

public int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

注意：在递归方法调用返回以后，还能够做一些事情。就以上面的代码为例：factorial(n - 1) 返回以后，我们将返回的结果值和 n 相乘。以上的代码等价于下面这段代码：

Java

public int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    int res = factorial(n - 1);
    // 在这里还能够执行一次操作，实现「分治思想」里「合并」的逻辑
    return n * res;
}

这种「能够在递归调用返回的时候做一些事情」对应于「分治思想」的第 3 步「合并」的过程。「在上一层「递归」调用结束以后，我们可以实现一些逻辑」这一点是我们在学习递归的过程当中容易被忽略的，要重视这个细节的理解，才能够更好地理解，并且应用递归。

使用尾递归计算 5!（了解即可）

相比较上面这种递归的写法，有一种递归调用的模式称为「尾递归」。尾递归是指一个函数里的 return 语句是返回一个函数的调用结果的情形，即最后一步调用的函数返回值被当前函数作为结果返回。

「尾递归」不是我们需要熟练掌握的编写代码的技巧，并且初学的时候可能会觉得难理解，大家暂时不去理解它问题不大。

尾递归的特点是：return 这一行直接实现递归调用，而不进行额外的操作（最后一个 return 语句是单纯函数），也就是说没有「合并」的过程。例如上面的阶乘的计算，我们可以把它写成：

Java

/**
  * @param n
  * @param res 递归函数上一层的结果，由于求的是阶乘，一开始需要传入 1
  * @return
  */
public int factorial(int n, int res) {
    if (n == 1) {
        return res;
    }
    return factorial(n - 1, n * res);
}

执行 factorial(n, 1); 计算 n 的阶乘，这里 res 初始的时候需要传入 1。可以通过下面这张函数调用图，理解 res 为什么需要传入 1 以及「尾递归」方式实现的求 5 的阶乘的过程。

「尾递归」在返回以后没有做任何事情，这样的过程就等价于「自底向上」递推地解决问题。事实上，一些编程语言会检测到我们编辑的代码当中「尾递归」的语法现象，然后优化。但是具体细节取决于具体运行环境。

使用循环计算 5!

如果我们知道了一个问题最开始的样子，就可以通过递推的方式一步一步求解，直到得到了我们想要的问题的解，相对于递归而言，这样的思考方向是「自底向上」的，计算 5! 我们还可以使用循环实现。代码如下：

Java

public int factorial(int n) {
    int res = 1;
    for (int i = 2; i <= n; i++) {
        res *= i;
    }
    return res;
}

友情提示：如果大家学习过「动态规划」的朋友就会知道，动态规划有两个思考的方向：一个是记忆化递归，另一个是递推。记忆化递归对应了「自顶向下」的解决问题的方向，递推对应了「自底向上」的逐步求解问题的方向。

很明显：「自底向上」思考问题的方向直接从一个问题的「源头」开始，逐步求解。相比较于「自顶向下」而言：

少了一层一层拆分问题的步骤；
也不需要借助一个数据结构（栈）记录拆分过程中的每一个子问题。

2.2递推与递归

我们通过「递归」向大家介绍了我们解决问题的两种思考的路径：「自顶向下」和「自底向上」。

「自顶向下」与「递归」

「自顶向下」是直接面对我们要解决的问题，逐层拆分，直到不能拆分为止，再按照拆分的顺序的逆序逐层解决，直至原问题得到了解决，这是「递归」。

「自底向上」与「递推」

如果我们非常清楚一个问题最开始的样子，并且也清楚一个问题是如何从它最开始的样子逐步演变成为我们想要求解的问题的样子，我们就可以通过「递推」的方式，从小规模的问题开始逐步「递推」得到最终要解决的大问题的解。

2.3总结与练习

「自顶向下」与「自底向上」分别对应了我们解决问题的两种思考路径：

自顶向下：直接面对问题，直接解决问题；
自底向上：从这个问题最开始的样子出发，一点一点「逐步演化」成我们最终想要解决的问题的样子。