我将如何打印出这样的递归跟踪？

Question

所以我试图打印出斐波那契数列递归函数的踪迹。

我的输出应该是这样的：

但是，我不确定如何格式化它。我真的不知道从哪里开始。我试过这个：

private static int fibCount;

public static long fibonacci(int n) {
    fibCount++;
    long result;
    if (n == 0 || n == 1) {
        result = n;
        System.out.printf("fib(%s)-->%s%n", n, result);
    } else {
        result = fibonacci(n - 1) + fibonacci(n - 2);
        System.out.printf("fib(%s)%n", n);
    }
    return result;
}

public static void main(String args[]) {
    fibonacci(5);
}

打印出来

fib(1)-->1
fib(0)-->0
fib(2)
fib(1)-->1
fib(3)
fib(1)-->1
fib(0)-->0
fib(2)
fib(4)
fib(1)-->1
fib(0)-->0
fib(2)
fib(1)-->1
fib(3)
fib(5)

我觉得我需要使用那个 fibCount 变量（我之所以这样做只是因为我认为缩进会依赖它），但我不知道我是否应该或如何使用。

Answer 1

您应该保留一种缩进计数器，每次您输入斐波那契函数时它都会递增，每次离开它时递减。

然后，打印时，在实际打印之前放置与该计数器当前值一样多的空格。为了更好的观看，你可以放两倍的空间，但这只是个人选择。

Answer 2

您需要在每次调用时传入缩进级别。每次追索都可以增加缩进。

public static long fibonacci(int n) {
    return fibonacci(n, 1);
}

public static long fibonacci(int n, int indent) {
    System.out.printf("%"+indent+"s", "");
    long result;
    if (n == 0 || n == 1) {
        result = n;
        System.out.printf("fib(%s)-->%s%n", n, result);
    } else {
        result = fibonacci(n - 1, indent + 2) + fibonacci(n - 2, indent + 2);
        System.out.printf("fib(%s)%n", n);
    }
    return result;
}

Answer 3

尝试以下操作：

拆分你的递归调用（这样你就可以在两者之间打印当前调用）
传递一个 depth 参数来跟踪缩进量

public static long fibonacci(int depth, int n) {
    String indent = new String(new char[depth]).replace('[=10=]', ' ');
    long result;
    if (n == 0 || n == 1) {
        result = n;
        System.out.printf(indent + "fib(%s)-->%s%n", n, result);
    } else {
        long first = fibonacci(depth+1, n - 1);
        System.out.printf(indent + "fib(%s)%n", n);
        long second = fibonacci(depth+1, n - 2);
        result = first + second;
    }
    return result;
}

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

输出：

    fib(1)-->1
   fib(2)
    fib(0)-->0
  fib(3)
   fib(1)-->1
 fib(4)
   fib(1)-->1
  fib(2)
   fib(0)-->0
fib(5)
   fib(1)-->1
  fib(2)
   fib(0)-->0
 fib(3)
  fib(1)-->1

Answer 4

我假设在现实世界中，您只会放入这样的跟踪（尤其是使用静态变量的跟踪）作为临时调试措施，并在将其投入生产之前删除代码.如果您想将其保留在生产代码中，我会寻找不同的解决方案。

首先，如果您要为此使用静态变量，则需要确保每次递归调用之后都能恢复其值。最好在 finally 块中执行此操作，以确保恢复始终发生，即使代码中某处隐藏了 return（或在出现异常的情况下）：

public static long fibonacci(int n) {
    int saveFibCount = fibCount;
    fibCount++;
    try {
        fibCount++;
        long result;
        if (n == 0 || n == 1) {
            result = n;
            System.out.printf("fib(%s)-->%s%n", n, result);
        } else {
            result = fibonacci(n - 1) + fibonacci(n - 2);
            System.out.printf("fib(%s)%n", n);
        }
        return result;
    } finally {
        fibCount = saveFibCount;
    }
}

其次，将其放入您的缩进中：不幸的是，Java 没有内置方法来 return 一串 n 空格。您可以很容易地编写一个（或者使用 Apache Commons 中可用的方法，我认为），并以这种方式使用它们：

        if (n == 0 || n == 1) {
            result = n;
            System.out.printf("%sfib(%s)-->%s%n", blanks(4*fibCount), n, result);
        } else {
            result = fibonacci(n - 1) + fibonacci(n - 2);
            System.out.printf("%sfib(%s)%n", blanks(4*fibCount), n);
        }

其中 blanks(b) return 是一串 b 空格。您可以使用 StringBuilder 来创建空白字符串，或者类似于：

String blanks = String.format("%" + numOfBlanks + "s", "");

[注意： 根据对另一个答案的评论，如果 numOfBlanks 为 0，则此方法无效。]

或者您可以将 fibCount 替换为 String fibIndent，而不是 fibCount++ 使用

fibIndent += "    ";

保存之前的版本后。

另一件需要考虑的事情：如果这是生产代码，我建议将另一个参数传递给递归例程，而不是使用静态变量。即使在单线程程序中，尝试使用递归例程处理静态变量也很麻烦且容易出错。递归参数应该是一个值参数或一个不可变对象，每次调用都会在将其传递给下一个调用之前复制它。在这种情况下，"recursive depth"（您的 fibCount）可能是参数。我不建议传递对所有递归调用共享的对象的引用，因为这几乎与使用静态变量一样容易出错（尽管更线程安全）。

[注意：我职业生涯的大部分时间都在研究递归下降编译器，所以其中很多问题对我来说都非常熟悉。]

[最后：我知道这只是为了练习，但不要使用递归来计算斐波那契数列。这样做会给你一个指数算法，而不是像一个简单的循环那样的线性算法。这是因为递归算法执行大量冗余工作，对同一参数计算结果多次。]

我将如何打印出这样的递归跟踪？

How would I make a recursive trace print out like this?

java

recursion