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

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

尝试以下操作:

• 拆分您的递归调用(以便您可以在两者之间打印当前调用)
• 传入一个depth参数来跟踪缩进量

public static long fibonacci(int depth, int n) {
    String indent = new String(new char[depth]).replace('\0', ' ');
    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