你应该如何处理递归？

Question

我目前在学校学习递归,当有很多递归调用时,我很难考虑方法.我只想问你应该如何考虑递归,因为我知道每一步跟踪方法调用都会变得太乏味.

我们简要介绍的不是跟踪每个递归调用,而是考虑通过归纳进行递归,但我遇到的问题是如何将归纳法应用于数学以外的情境.就像有一个方法递归打印出这样的数字:

public void blah(int n)
{
    for (int i = 0; i < n; i++)
      blah(i);
    System.out.print(n);
}

我无法考虑打印出来的内容,我无法看到感应在这里是如何相关的(原谅我的无知,如果它可以在任何地方使用).

但我想我真正的问题是如何在不必跟踪每个方法调用的情况下解决递归问题？最好的做法只是看看基本案例和倒退工作吗？(但即便如此,我认为我对发生的事情感到模糊).

Answer 1

你可以在这里找到关于Thinking Recursively的一个很好的解释

从链接

• 编写递归函数的原型.

• 写一个描述函数功能的注释.

• 确定基本情况(可能有多个)及其解决方案.

• 确定要解决的较小问题(或问题).如果它使您更容易遵循,将解决方案保存
  到局部变量的较小问题(例如,sum()示例中的小).ASSUME递归调用工作原理

• 使用较小问题的解决方案来解决更大的问题.(如果这样做
  不正确,较小问题的解决方案也将被错误计算,因此,
  上一步骤中的假设将失败).

Answer 2

如何处理递归而不必跟踪每个方法调用？

“理解”递归程序有多种方法 - 一种是将递归调用视为黑匣子，另一种需要“演示”一些情况并猜测模式。

第一种方法假设递归方法已经编写，并且它做了一些已知的事情。当您考虑递归下降解析器时，这很有用；对于产生输出（而不是消耗输入）的程序（例如您的程序）来说，这并不是那么好。

第二种方法更适用于与您的示例类似的程序。针对值 0、1、2 和 3 进行计算。

0 - 0
1 - 0 1
2 - 0 0 1 2
3 - 0 0 1 0 0 1 2 3

你注意到这个模式了吗？的输出N列出了先前项目的输出N-1，并N在最后打印。一旦您认为可以继续该模式，您就知道您已经了解了递归程序。