递归，无法理解输出

为什么我会在输出中获得额外的1 * 1，并且它有点向后？有点初学者在这里递归，会爱上一个详细的答案。递归，无法理解输出

class Program 
{ 

    public static long Factorial(int n) 
    { 
     if (n == 0) 
      return 1; 

     Console.WriteLine("{0} * {1}", n, Factorial(n - 1)); 
     return n * Factorial(n - 1);  
    } 
    static void Main(string[] args) 
    { 
     long a = 0; 
     a = Factorial(3); 
     Console.WriteLine(a); 
    } 
}

输出

来源

2017-06-18 yosu

我投票关闭这一问题作为题外话，因为被调试的帮助：这个代码是如何工作的？ – danihp

@danihp基本上有人（@yosu）犯了一个错误，这也可能发生在其他人身上。所以这甚至可以帮助其他人，有一个类似的问题。它不是那么广泛，它只是调试帮助，这是一个关于递归的相当紧凑的问题。 – MetaColon

@MetaColon代码有一个很大的错误，因为这个输出没有意义。 OP要求忽略这个错误。这是家庭作业。 OP应该为自己做。它们是双递归，应该是简单的。 – danihp

你的下一行递归调用函数两次，一旦输出，然后再次。这就是输出完全混乱的原因，因为你从Console.WriteLine()方法中调用它，然后立即在return声明中再次调用它。

此外，因子零为1，因此我在WriteLine()方法中添加了一点三元语句检查，以便输出在数学上是正确的。

Console.WriteLine("{0} * {1}", n, Factorial(n - 1)); // Calling it once 
return n * Factorial(n - 1); // Calling it again, oops!

这里有一个轻微的调整，这将有助于：

public static long Factorial(int n) 
{ 
    if (n == 0) 
     return 1; 
    Console.WriteLine("{0} * {1}", n, (n>1?n-1:n)); 
    return n * Factorial(n - 1);  
} 

static void Main(string[] args) 
{ 
    long a = Factorial(3); 
    Console.WriteLine(a); 
}

息率

来源

2017-06-18 16:11:17 TomServo

这个问题要求详细的答案。 – MetaColon

这是因为有第二个因子循环在日志输出回事：

Console.WriteLine("{0} * {1}", n, Factorial(n - 1));

这需要计算te因子（n-1）之前它打印任何东西。因为递归的每一步现在都会触发两个递归，所以它比您预期的复杂得多！

所以阶乘（3）：

开始记录 “3 *阶乘（2）” - >但需要制定出阶乘（2）
- 阶乘（2）开始记录“2 *阶乘（1） - >但需要制定出阶乘（1）
  - 阶乘（1）开始记录” 1 *阶乘（0） - >但需要制定出阶乘（0）
    - 阶乘（0）返回1
  - 现在阶乘（1）可打印“1 * 1”（你的第一行输出的。）
  - 现在阶乘（1）需要计算阶乘（0）其返回值...
    - 阶乘（0）返回1
- 阶乘（2）可以登录“2·1”（你的第二行输出。）
- 阶乘（2）现在需要计算阶乘（1）返回
  - 阶乘（1）开始记录“1 *阶乘（0） - >但需要制定出阶乘（0）
  - ...等等，等等

如果将其更改为类似：

Console.WriteLine("{0} * Factorial({1})", n, n - 1);

然后你会得到更像你期待的日志。

（如果你正在学习递归，这可能是有趣的，你通过与调试工作，并看到程序的流程如何去，以及为什么它会导致输出，你看到的。）

来源

2017-06-18 16:24:38

但是，现在您的日志记录朝着错误的方向（如3 * 2; 2 * 1; 1 * 0），这可能会造成混淆。而且，更令人困惑的是，如果您仅对您的日志付款，您将拥有1 * 0，导致1。 – MetaColon

取决于'错误'方向的意思！如果你对函数调用的顺序感兴趣，这是正确的方向 - 但同意它是有争议的。我提出的建议给出了输出'1 * Factorial（0）'而不是'1 * 0' - 但是再一次，记录最清楚的依赖于目的。 –

碰巧，你的错误与递归无关。你的问题是，你调用了一个方法两次，而不是保存它的价值。如果你不打印结果，你甚至不会意识到这一点。作为@JLK指出，你在这个片段中调用它两次：通过代码

Console.WriteLine("{0} * {1}", n, Factorial(n - 1)); 
return n * Factorial(n - 1);

让我们一步，这样我们就可以理解输出：

Factorial (3); 
-> output 3 * {Factorial (2)}   // 3 * 2 (4) 
    -> output 2 * {Factorial (1)}  // 2 * 1 (2) 
     -> output 1 * {Factorial (0)} // 1 * 1 (1) 
     <- 1 
     Factorial (0) 
     <- 2 
     Factorial (1) 
     -> output 1 * {Factorial (0)} // 1 * 1 (3) 
     <- 1 
     Factorial (0) 
     <- 1 
    <- 1 
    Factorial (2) 
    -> output 2 * {Factorial (1)}  // 2 * 1 (6) 
     -> output 1 * {Factorial (0)} // 1 * 1 (5) 
     <- 1 
     Factorial (0) 
     <- 1 
     Factorial (1) 
     -> output 1 * {Factorial (0)} // 1 * 1 (7) 
     <- 1 
     Factorial (0) 
     <- 1 
    <- 2

这可能是一个有点混乱，但这对于递归是正常的。所以基本上所有你需要做的是改变代码片段一点点：

var factorial = Factorial (n - 1); 
Console.WriteLine("{0} * {1}", n, factorial); 
return n * factorial;

输出则是：

如果您想了解更多关于递归，我d建议this网站。这不是关于C＃，但它是一个很好的学习递归的网站。如果你想在递归中做很多事情，我不会推荐C＃，因为它是一种命令式语言。对于递归函数语言更适合。如果你仍然想保持接近C＃，或至少使用.Net框架，我建议使用F#，这是C＃的功能等价物。

C＃和递归的主要问题是，C＃不支持Tail recursion。这可以很容易地导致StackOverflows，当你做更深的递归调用（例如无限递归循环）。这是因为每次你调用一个函数时，你调用该函数的代码地址被压入堆栈。所以每次你做一个递归调用时，代码地址都被推送到堆栈。所以，如果你有例如这样的功能：

void rec() => rec();

你在更短的通过调用它获得的StackOverflow比在C＃中的第二个。尾递归至少部分解决了这个问题：如果递归调用是函数中的最后一次执行，它不会推送调用者的代码地址。因此，在F＃这个一直运行：

let rec r() = 
    r() 
r()

（我不会去深入到F＃的语法，有足够的在线教程）。我说它只解决了部分问题，因为这个：

let rec r() = 
    r() 
    () 
r()

导致StackOverflow再一次。我不知道任何编程语言，如果情况并非如此，那么您只需习惯使用尾递归。

您可以在this后阅读更多关于功能/递归语言。

来源

2017-06-18 16:38:01 MetaColon

你应该向右功课，从记分牌复制。你必须恰克：

Console.WriteLine("{0} * {1}", n, Factorial(n - 1));

通过

Console.WriteLine("{0} * {1}", n, n - 1);

这个错误做出错误的输出。

来源

2017-06-18 16:52:16 danihp

递归，无法理解输出

回答

相关问题