# 你应该如何处理递归？ [英] 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.

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.