java - 跟踪递归方法

Question

我发现理解递归的概念非常困惑。我正在尝试跟踪递归函数。有人可以帮我吗？

    public static int h(int n){
        if (n == 0)
            return 0;
        else
            return h(n-1)+1;
    }

当我写作时

int a = h(5);
System.out.println(a)

我不明白产生的结果到底是怎么来的？

Answer 1

首先，如果您对递归的概念理解有困难，我认为以下链接会对您有所帮助:

• Recursion Programming
• Introduction to Recursion and Memoization with Examples:
• Recursion made simple
• Recursion

您可以使用 IDE 上的调试工具来查看它是如何工作的。您可以通过 Google 获取有关如何设置断点和使用调试器单步执行程序的说明。

关于方法h，它将返回您作为输入提供的内容(如果它是正数或0)。大数和负数也会导致 StackOverflowError。要了解工作原理，您可以在方法中使用打印语句。

public static int h(int n) {
    System.out.println("h(" + n + ")");
    if (n == 0) {
        System.out.println("value: 0");
        return 0;
    } else {
        System.out.println("going down");
        int temp = h(n - 1) + 1;
        System.out.println("h(" + n + ") --> " + temp);
        return temp;
    }
}

将输出:

h(5)
going down
h(4)
going down
h(3)
going down
h(2)
going down
h(1)
going down
h(0)
value: 0
h(1) --> 1
h(2) --> 2
h(3) --> 3
h(4) --> 4
h(5) --> 5

可以编辑以上输出以显示工作情况:

h(5)
|    going down
|----h(4)
|    |   going down
|    |---h(3)
|    |   |   going down
|    |   |---h(2)
|    |   |   |  going down
|    |   |   |--h(1)
|    |   |   |  |    going down
|    |   |   |  |----h(0)
|    |   |   |  |    |    value: 0 --> return 0;
|    |   |   |  |    h(1) --> 1 --> h(0) + 1 = 0 + 1 = 1
|    |   |   |  h(2) --> 2          h(1) + 1 = 1 + 1 = 2
|    |   |   h(3) --> 3             h(2) + 2 = 1 + 1 = 3
|    |   h(4) --> 4                 h(3) + 3 = 1 + 1 = 4
|    h(5) --> 5                     h(4) + 4 = 1 + 1 = 5

以下是方法 h 的非递归版本。

public static int nonh(int n) {
    int result = 0;
    for (int i = n; i > 0; i--) {
        result += 1;
    }

    return result;
}

希望对您有所帮助:)