如何通过 GCD 递归将其输出

Question

这就是它应该是什么样子

Calling: gcd(20,12) 
  Calling: gcd(12,8) 
    Calling: gcd(8,4) 
      Calling: gcd(4,0) 
        Returning: 4 from gcd(4,0) 
      Returning: 4 from gcd(8,4) 
    Returning: 4 from gcd(12,8) 
  Returning: 4 from gcd(20,12) 
Returning: 4 from gcd(12,20)

这是我的输出

Calling: gcd(10,16)
  Calling: gcd(16,10)
    Calling: gcd(10,6)
      Calling: gcd(6,4)
        Calling: gcd(4,2)
          Returning: 2 from gcd(2,0)

这是我的代码

public static int gcd(int x, int y, String indent) {
        if (y == 0) {
            System.out.println(indent + "Returning: " + x + " from gcd(" + x + "," + y + ")");
            return x;
        } else {
            System.out.println(indent + "Calling: gcd(" + x + "," + y + ")");
            indent = indent + "  ";
            return gcd(y, x % y, indent);
        }

    }

Answer 1

您的代码的问题是您只在y为零时打印“返回”。这只发生一次。您要做的是，对于每个“调用”，它必须与一个“返回”配对。

换句话说，您需要在方法体的开头打印“calling ”,在return语句之前打印“returning”。

    public static int gcd(int x, int y, String ind){
       System.out.println(ind + "Calling: gcd(" + x + "," + y + ")");  //<<
       int max = Math.max(x,y), min = Math.min(x,y);
       int result = (min == 0 ? max : gcd(max%min,min,ind+ind));
       System.out.println(ind + "Returning: gcd(" + x + "," + y + ")"); //<<
       return result;
    }