java中递归的澄清

Question

所以这段时间我一直认为递归的问题是理解案例。事实证明，我的问题是理解递归案例的值。例如，向后打印数组的一部分。

原始尝试

    public static void printBackwards(int i, int j, char[] A){
        if(i == j){
            System.out.println(A[i]); 
        }
        else{
            printBackwards(i+1,j,A);
        }

    }

一次有效的尝试

    public static boolean printBackwards(int i, int j, char[] A){
    if(i == j){
            System.out.println(A[i]);
            return true;
    }
    else{
            if(printBackwards(i+1,j,A) == true){
                System.out.println(A[i]);
                return true;
            }
            else{
                printBackwards(i+1,j,A);
            }
    }
    return false;
    }

然而，这是一种高效的递归吗？还是有更好的办法？这是我从写出来的时候看出来的唯一方法。

Answer 1

以下是以相反顺序打印数组的Java代码：

public class TestProgram {

    private int[] a = {4, 2, 7, 1, 9, 5, 8};

    public static void main(String[] args) {
        TestProgram p = new TestProgram();
        p.print(a.length - 1);
    }

    public void print(int i) {
        // the anchor of the recursive method
        // it indicates that we are done printing array
        if (i < 0) 
            return;

        // print the current value
        System.out.printf("%d ", a[i]);

        // recursively call print() method
        print(i - 1);
    }
}

Answer 2

首先问“我什么时候可以立即解决问题（没有递归调用）？”。在这种情况下，当区域只有一个元素时——这是基本情况。

当这不是真的时，您需要将问题分解成一个较小的版本（可以通过调用printBackwards来解决）以及完成问题所需的任何东西。您已经有一个调用将打印A[i 1... j]（用于i的原始值）。因此，剩下的就是打印A[i]。弄清楚它应该在数组的其余部分之前还是之后打印，然后就万事俱备了。

Answer 3

在我看来，解决这个问题不需要使用递归。你可以用简单的循环来做。

public class PrintBackwards {

    public static void main(String[] args) {
        char[] a = new char[] {'A', 'B', 'C', 'D'};

        for(int i = a.length - 1; i >= 0; i--) {
            System.out.println(a[i]);
        }
    }
}

这背后有什么理由使用递归吗？如果没有，则按照上面的示例更快地执行。

如果你想使用递归，我希望这个例子能让你比你的更容易理解。

public class PrintBackwards {

    private static char[] a = new char[]{'A', 'B', 'C', 'D'};

    public static void main(String[] args) {
        printBackwards(0);
    }

    public static void printBackwards(int i) {
        if (i < a.length) {
            printBackwards(++i);
            System.out.println(a[i - 1]);
        }
    }
}