跟踪递归方法

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

首先,如果您难以理解递归的概念,我认为以下链接将帮助您:

• 递归编程
• 通过示例介绍递归和记忆:
• 递归变得简单
• 递归

您可以使用IDE上的调试工具来查看它的工作方式.您可以在Google上获取有关如何设置beakpoints并使用调试器逐步完成该程序的说明.

关于该方法h,它将返回您给出的输入(如果它是正数或0).大数字和负数也会导致StackOverflowError.要了解工作原理,您可以在方法中使用print语句.

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;
}

希望有帮助:)

Answer 2

要在调试器中跟踪此递归调用，请在语句上设置断点if，然后运行程序。当到达断点时：

• 检查 的值n，
• 查看调用堆栈窗口。

调用堆栈上的项目数量会随着每次递归调用而增加；的值n将减少一。当您深入调用几个级别时，单击调用堆栈上的不同项目。它会将您带到呼叫站点（即return h(n-1)+1）。您将能够检查n堆栈此级别的值。