追踪递归方法

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 搜索有关如何设置断点并使用调试器单步执行程序的说明。

关于方法

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

的值会减少 1。当您深入调用几个级别时，单击调用堆栈上的不同项目。它会将您带到呼叫站点（即

return h(n-1)+1

）。您将能够在堆栈的这一层检查

n

的值。

Answer 3

尝试记录。或者，好吧，只是调试打印：

public static int h(int n){
    System.out.println("called h(" + n + ")");
    if (n == 0) {
        System.out.println("we know the result for 0, returning 0");
        return 0;
    } else {
        System.out.println("we don't know the result, calling for " + (n-1));
        int t = h(n-1);
        System.out.println("Found the result for " + (n-1) + 
                           ", calculating the result for " + n);
        return t + 1;
    }
}

对于

n = 4

，您将得到：

called h(4)
we don't know the result, calling for 3
called h(3)
we don't know the result, calling for 2
called h(2)
we don't know the result, calling for 1
called h(1)
we don't know the result, calling for 0
called h(0)
we know the result for 0, returning 0
Found the result for 0, calculating the result for 1
Found the result for 1, calculating the result for 2
Found the result for 2, calculating the result for 3
Found the result for 3, calculating the result for 4

希望它能给你一个线索——尝试不同的算法，看看会发生什么。

此外，请尝试致电

h(-1)

——玩得开心！

Answer 4

有两件事需要弄清楚：

• 递归中接下来调用什么（您在问题标题中询问的内容）
• 如何使用下一个值来构建当前值。 （你没有问，但是能够看到东西也很有帮助）

递归中接下来调用什么：

专业提示：如果您在代码中添加打印和日志，通常会变得过于混乱。

您可以做的就是在纸上描绘它。示例：

从

h(5)

开始，然后缩进下一个拨出的呼叫。依此类推，直到达到基本情况为止。

h(5)
   h(4)
      h(3)
         h(2)
            h(1)
               h(0)
                  0

如何使用下一个值来构建我的当前值：

在您的情况下，它是

h(n-1)+1

，这意味着

previous + 1

，如

h(3) = h(2) + 1

在更复杂的设置中，跟踪可能类似于：

h(5)
   f(4)
      k(3) + k(2)
        k(2)    k(1)    
           k(1)     k(0)
             k(0)      0
               0

上面的复杂性来自于：

• 在每次递归调用时，我们都没有进行相同的处理
• 对于

  f(4)

  ，因为需要逻辑，分叉，然后聚合结果