java - 数据结构: how do I draw recursion trees?

Question

我有一个问题，不知道如何开始。有人能解释一下如何做这个递归树吗？有没有办法在 Java 上做到这一点？

对于下面定义的递归方法fnc(n,k)，画出调用fnc(3,5)的递归树。

Your diagram should include the return values for all calls to method fnc(n,k).

public static int fnc(int n, int k) {
    if ( (n <= 1) || (k <= 1) ) {
        return n+k; } else {
        return fnc(n-1,k) + fnc(n,k-2);
    }
}

Answer 1

如果我理解正确，您只需要跟踪递归的级别并使用它来控制缩进...

• 单次进入单次退出可能会有所帮助，因此只需要一个打印语句即可返回
• String.format() 对于输出多个值非常方便
• pad() 方法创建重复字符串 - 请参阅 Simple way to repeat a String in java替代方案

示例

static int fnc(int n, int k, int level) {
    System.out.println(String.format("%sfnc(%d, %d)", pad(level), n, k));
    int result;
    if ((n <= 1) || (k <= 1)) {
        result = n + k;
    } else {
        result = fnc(n - 1, k, level + 1) + fnc(n, k - 2, level + 1);
    }
    System.out.println(String.format("%s<== %d", pad(level), result));
    return result;
}

private static String pad(int level) {
    String pad = "";
    for (int i = 0; i < level; i++) {
        pad += "  ";
    }
    return pad;
}

public static void main(String[] args) {
    fnc(3, 5, 0);
}

输出

fnc(3, 5)
  fnc(2, 5)
    fnc(1, 5)
    <== 6
    fnc(2, 3)
      fnc(1, 3)
      <== 4
      fnc(2, 1)
      <== 3
    <== 7
  <== 13
  fnc(3, 3)
    fnc(2, 3)
      fnc(1, 3)
      <== 4
      fnc(2, 1)
      <== 3
    <== 7
    fnc(3, 1)
    <== 4
  <== 11
<== 24