递归算法入门（Java）

今天学习了简单的递归算法，参考书籍为 Building Java Programs--A Back to Basics Approach (Stuart Reges | Marty Stepp, University of Washington)。

依书中所说，递归算法可以理解为普通迭代算法的另一种实现，其中：

Iteration (Iterative): A programming technique in which you describe actions to be repeated using a loop.

Recursion (Recursive): A programming technique in which you describe actions to be repeated using a method that calls itself.

实现方面，理论上任何一个普通的迭代算法都能够转化成递归的形式，例如打印星号算法：

public static void writeStars(int n) {        // 迭代实现
    for (int i = 1; i <= n; i++) {
        System.out.print("*");
    }
    System.out.println();
}

public static void writeStars(int n) {        // 递归实现
    if (n == 0) {
        System.out.println();
    } else {
        System.out.print("*");
        writeStars(n – 1);
    }
}

在对迭代实现进行改写时，个人认为只需要把握两个要点即可：
1、找到循环的一般实现单元
2、找到循环的跳出条件
书中将这两个要点称为：

Base Case: A case within a recursive solution that is so simple that it can be solved directly without a recursive call.

Recursive Case: A case within a recursive solution that involves reducing the overall problem to a simpler problem of the same kind that can be solved by a recursive call.

一个稍微复杂一点的递归实现例子是最大公约数求解算法（这里只考虑了部分情况，且输入参数 x > y）

public static int gcd(int x, int y) {
    if (x < 0 || y < 0) {
        // recursive case with negative value(s)
        return gcd(Math.abs(x), Math.abs(y));
    } else if (y == 0) {
        // base case with y == 0
        return x;
    } else {
        // recursive case with y > 0
        return gcd(y, x % y);
    }
}

然而，使用递归实现并不是在所有情况下都是最优的，它具备下列优缺点：
(转自https://blog.csdn.net/wangzhenling/article/details/59702845)

优点：表达简洁，实现简单，开发人员只需要考虑解决一个复杂问题所需的两个递归算法实现要素即可。

缺点：效率存疑，过深的方法调用堆栈会产生栈溢出等问题。

因此，结合实际情况进行考虑之后，只有在递归算法实现简单程度明显优于迭代算法时（树的前序，中序，后序遍历算法或者最短路径算法等）才需要考虑进行递归实现。普通的代码使用迭代实现不但没有效率损失，还可以增强可读性，不会被同事嫌弃。