你应该如何处理递归？ [英] How should you approach recursion?

问题描述

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

I am currently studying recursion in school, and I have trouble thinking about methods when there are many recursive calls. I just want to ask how you should think about recursion because I know tracing the method calls by each step will become too tedious.

我们简单介绍的不是跟踪每个递归调用，而是考虑通过归纳进行递归，但我遇到的问题是如何将归纳应用于除了数学。就像有一种方法递归打印出这样的数字：

Instead of tracing each recursive call, the thing we briefly covered was thinking about recursion by induction, but the problem I have is seeing how induction can be applied to situations other than math. Like if there is a method that recursively prints out numbers like this:

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

我无法考虑打印出什么，我看不清楚感应在这里可能是相关的（原谅我的无知，如果它可以在任何地方使用）。

I have trouble thinking about what prints out, and I can't see how induction could be relevant here (pardon my ignorance if it can be used everywhere).

但我想我真正的问题是如何处理递归而不必追踪每一个方法调用？最好的做法只是看看基本情况和倒退工作吗？ （但即便如此，我认为我对发生的事情感到困惑）。

But I guess my real question is how you can tackle recursion without having to trace every single method call? Is the best thing to do just to see the base case and sort of work backwards? (But even then I think I get fuzzy about what happens).

推荐答案

你如何解决递归而不必跟踪每一个方法调用？

how you can tackle recursion without having to trace every single method call?

有几种方法可以理解递归程序 - 一种涉及考虑递归调用一个黑盒子，另一个需要播放一些案例并猜测模式。

There are several ways of "understanding" recursive programs - one involves thinking of a recursive call as a black box, and the other requires "playing out" a few cases and guessing the pattern.

第一种方法假设已经编写了递归方法，并且它做了一些已知的事情。当你想到递归下降解析器时，这很有用;对于生成输出的程序（与消费输入相反），例如你的程序，它不是那么好。

The first method assumes that the recursive method is already written, and that it does some known thing. This is useful when you think of recursive descent parsers; it is not that good for programs that produce output (as opposed to consuming input), such as yours.

第二种方法更适用于与您的示例类似的程序。播放值为0,1,2和3.

The second method is more applicable to programs similar to your example. Play it out for values 0, 1, 2, and 3.

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

<你有没有注意到这种模式？ N 的输出列出 N-1 之前项目的输出，并打印 N 最后。一旦您认为可以继续使用该模式，就会知道您对递归程序有所了解。

Did you notice the pattern? The output for N lists outputs for N-1 prior items, and prints N at the end. Once you think that you can continue the pattern, you know that you have an understanding of your recursive program.

这篇关于你应该如何处理递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！