blocks|key|1451438|text|您可以找到关于在here上进行递归思考的一个很好的解释|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1451439|从链接|1451440|为递归function.|1451441|Write写一个原型，一个注释，描述什么函数does.|unordered-list-item|1451442|
|1451443|Determine基本情况(可能有多个)，以及它的solution(s).|1451444|1451445|Determine什么小问题(或多个问题)要解决。如果这使您更容易理解，请将解决方案保存到较小的|1451446|1451447|局部变量的问题(例如，.ASSUME()示例中的小问题)|1451448|使用较小问题的解决方案来解决较大问题。(如果此操作不正确，则较小的|1451449|1451450|问题也会被错误地计算，因此，假设|1451451|上一步将失败)。|1451452|entityMap|0|LINK|mutability|MUTABLE|url|http://www.cs.umd.edu/class/fall2002/cmsc214/Tutorial/recursion2.html^0|8|4|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|19|8|@]|9|@$A|1A|B|1B|1|1C]]|C|$]]|$1|D|3|E|5|6|7|1D|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|1E|8|@]|9|@]|C|$]]|$1|H|3|I|5|J|7|1F|8|@]|9|@]|C|$]]|$1|K|3|L|5|6|7|1G|8|@]|9|@]|C|$]]|$1|M|3|N|5|J|7|1H|8|@]|9|@]|C|$]]|$1|O|3|L|5|6|7|1I|8|@]|9|@]|C|$]]|$1|P|3|Q|5|J|7|1J|8|@]|9|@]|C|$]]|$1|R|3|-4|5|6|7|1K|8|@]|9|@]|C|$]]|$1|S|3|T|5|6|7|1L|8|@]|9|@]|C|$]]|$1|U|3|V|5|J|7|1M|8|@]|9|@]|C|$]]|$1|W|3|-4|5|6|7|1N|8|@]|9|@]|C|$]]|$1|X|3|Y|5|6|7|1O|8|@]|9|@]|C|$]]|$1|Z|3|10|5|6|7|1P|8|@]|9|@]|C|$]]|$1|11|3|-4|5|6|7|1Q|8|@]|9|@]|C|$]]]|12|$13|$5|14|15|16|C|$17|18]]]]

You can find a nice explanation about Thinking Recursively over <a href="http://www.cs.umd.edu/class/fall2002/cmsc214/Tutorial/recursion2.html" rel="noreferrer">here</a>

From the link

<ul>
<li>Write a prototype for the recursive function.</li>
<li>Write a comment that describes what the function does.</li>
<li>Determine the base case (there may be more than one), and its
solution(s).</li>
<li>Determine what smaller problem (or problems) to solve. If it makes it
easier for you to follow, save the solutions to the smaller 
problems to local variables (e.g., small in the sum() example).ASSUME
the recursive call works </li>
<li>Use the solutions of the smaller problem to solve the larger problem.
(If this is done INCORRECTLY, the solutions of the smaller 
problems will also be computed incorrectly, thus, the assumption in 
the previous step will fail).</li>
</ul>

blocks|key|5492891|text|下面是我对递归的看法。实际上，这很简单。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5492892|5492893|我需要做什么才能停止？这就是所谓的基础case.|unordered-list-item|offset|length|style|BOLD|5492894|What+do+I+do+if+I+not+not+do？|5492895|5492896|以经典的递归问题为例:+F(n)+=+n！0!定义为1，任何大于0的值都定义为n*F(n-1)|5492897|在这个例子中，我满足了我的两个条件-当我达到0！时停止，并且我将我拥有的任何值乘以第(n-1)个值。|5492898|我使用的另一种方法是:如果它可以递归完成，那么它就可以迭代完成。这就是说，如果我可以编写一个循环来执行相同的任务，那么我也可以编写一个递归方法来执行该任务。递归地考虑某些问题通常更容易(例如Ackermann's+Function)，而其他问题则更容易迭代(例如遍历链表)。|5492899|您可能希望在最适合您的地方使用迭代。|5492900|entityMap|0|LINK|mutability|MUTABLE|url|http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CDUQFjAA&url=http%253A%252F%252Fen.wikipedia.org%252Fwiki%252FAckermann_function&ei=0GFyT72UKsG2gwf3ruVc&usg=AFQjCNFymhVZJFqhmnGEky9rM6vsicMoFg&sig2=UsDEWYZwIX5pOiSNTDl0Qw^0|0|0|H|7|0|0|0|0|0|2N|K|0|0|H|1|0^^$0|@$1|2|3|4|5|6|7|12|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|13|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|14|8|@$F|15|G|16|H|I]]|9|@]|A|$]]|$1|J|3|K|5|E|7|17|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|18|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|19|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|1A|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1B|8|@]|9|@$F|1C|G|1D|1|1E]]|A|$]]|$1|S|3|T|5|6|7|1F|8|@$F|1G|G|1H|H|I]]|9|@]|A|$]]|$1|U|3|-4|5|6|7|1I|8|@]|9|@]|A|$]]]|V|$W|$5|X|Y|Z|A|$10|11]]]]

Here's the way I think about recursion. It's pretty simple, actually.

<ul>
<li>What do I need to do in order to stop? This is known as your base case.</li>
<li>What do I do if I'm not done yet?</li>
</ul>

Take, for example, the classical recursive problem: F(n) = n!. 0! is defined to be 1, and anything else greater than 0 is defined to be n*F(n-1)

In this example, I meet my two conditions - I stop when I hit 0!, and I multiply whatever value I have by the (n-1)th value.

Another approach I use: if it can be done recursively, then it can be done iteratively. This is to say, if I can write a loop to perform the same task, then I can write a recursive method to perform the task as well. It is often easier to think of certain problems recursively (e.g. <a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;ved=0CDUQFjAA&amp;url=http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FAckermann_function&amp;ei=0GFyT72UKsG2gwf3ruVc&amp;usg=AFQjCNFymhVZJFqhmnGEky9rM6vsicMoFg&amp;sig2=UsDEWYZwIX5pOiSNTDl0Qw" rel="nofollow">Ackermann's Function</a>), and others iteratively (e.g. walking down a linked list).

You would want to use iteration where it suits you best.

blocks|key|1451543|text|您的示例将打印出来|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1451544|0+0+1+0+0+1+2+0+0+1+0+0+1+2+3+4|code-block|syntax|javascript|1451545|如果用blah(4)调用。|1451546|一般来说，在递归时，我会确保首先处理基本情况。在这之后，处理递归的状态，然后逻辑就可以来了。|1451547|在本例中，基本大小写控件是i+<+n，它将首先出现在0+<+0处，这是不正确的，并中断了打印输出0的for循环。然后运行下一次迭代out，这是从i+=+0+to+1+<+1开始的，在调用i=+0+<0之后再次打印出0。然后，它完成循环并打印1。然后就轮到2秒了，哈哈。沿着这条线往下走，直到每个数字都轮到它。|offset|length|style|CODE|1451548|entityMap^0|0|0|0|0|D|5|Q|5|20|E|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|V|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|W|8|@$M|X|N|Y|O|P]|$M|Z|N|10|O|P]|$M|11|N|12|O|P]]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|13|8|@]|9|@]|A|$]]]|R|$]]

Your example will print out 

<pre><code>0 0 1 0 0 1 2 0 0 1 0 0 1 2 3 4
</code></pre>

If called with blah(4).

In general when recursing I make sure to handle the base case first. After that, handle the state of the recursion, then the logic can come.

In this example, the base case control is <code>i &lt; n</code> and will occur first at <code>0 &lt; 0</code> which is untrue and breaks the for loop printing out 0. Then the next iteration out will run, which was to go from <code>i = 0 to 1 &lt; 1</code> which again prints out 0 after calling i = 0 &lt; 0. Then it finishes the loop and the 1 is printed. Then it is 2s turn, lol. And so on down the line back out until each number has had it's turn.

blocks|key|5493030|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5493031|如何处理递归而不必跟踪每个方法调用？|blockquote|5493032|5493033|5493034|有几种“理解”递归程序的方法--一种是将递归调用看作一个黑盒，另一种则需要“演绎”几种情况并猜测其模式。|5493035|第一个方法假设递归方法已经编写，并且它做了一些已知的事情。当您想到递归下降解析器时，这很有用；它对于生成输出(与消耗输入相反)的程序来说并不是那么好，比如您的程序。|5493036|第二种方法更适用于与您的示例类似的程序。对值0、1、2和3进行播放。|5493037|0+-+0
1+-+0+1
2+-+0+0+1+2
3+-+0+0+1+0+0+1+2+3|code-block|syntax|javascript|5493038|你注意到这个模式了吗？N的输出列出了N-1之前项目的输出，并在最后打印N。一旦你认为你可以继续这个模式，你就知道你已经理解了你的递归程序。|offset|length|style|CODE|5493039|entityMap^0|0|0|0|0|0|0|0|0|B|1|I|3|Z|1|0^^$0|@$1|2|3|-4|4|5|6|Y|7|@]|8|@]|9|$]]|$1|A|3|B|4|C|6|Z|7|@]|8|@]|9|$]]|$1|D|3|-4|4|5|6|10|7|@]|8|@]|9|$]]|$1|E|3|-4|4|5|6|11|7|@]|8|@]|9|$]]|$1|F|3|G|4|5|6|12|7|@]|8|@]|9|$]]|$1|H|3|I|4|5|6|13|7|@]|8|@]|9|$]]|$1|J|3|K|4|5|6|14|7|@]|8|@]|9|$]]|$1|L|3|M|4|N|6|15|7|@]|8|@]|9|$O|P]]|$1|Q|3|R|4|5|6|16|7|@$S|17|T|18|U|V]|$S|19|T|1A|U|V]|$S|1B|T|1C|U|V]]|8|@]|9|$]]|$1|W|3|-4|4|5|6|1D|7|@]|8|@]|9|$]]]|X|$]]

<blockquote>
 how you can tackle recursion without having to trace every single method call?
</blockquote>

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.

<pre><code>0 - 0
1 - 0 1
2 - 0 0 1 2
3 - 0 0 1 0 0 1 2 3
</code></pre>

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

blocks|key|1979921|text|我不确定如何告诉你去思考它，但我认为这可能会帮助你掌握流程是什么样子的。在你编写了一段时间之后，你会对它有一种感觉，但很多人只是避免使用它，因为它让他们觉得很讨厌。我很抱歉它不是用Java编写的，但它不是关于代码的，而是关于它打印的内容，所以只要在任何Linux机器或cygwin上运行它就行了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1979922|+perl+-e+'sub+foo+{my+$n+=shift;my+$depth=shift;print+"\t"x$depth;print+"blah($n)\n";for(my+$i=0;$i<$n;$i%2B%2B){foo($i,$depth%2B1)};print+"\t"x$depth;print+$n,"\n"};foo(shift);'++5|code-block|syntax|javascript|1979923|在arg为3的情况下调用，如下所示：|1979924|++++blah(3)
++++++++++++blah(0)
++++++++++++0
++++++++++++blah(1)
++++++++++++++++++++blah(0)
++++++++++++++++++++0
++++++++++++1
++++++++++++blah(2)
++++++++++++++++++++blah(0)
++++++++++++++++++++0
++++++++++++++++++++blah(1)
++++++++++++++++++++++++++++blah(0)
++++++++++++++++++++++++++++0
++++++++++++++++++++1
++++++++++++2
++++3|1979925|我试着像其他人说的那样，把它可视化成更小的组件。也就是说，除了递归，函数还能做什么。在这种情况下，函数从0计数到某个数字。现在考虑到递归所做的事情。对于每个计数，它开始一个新的计数，直到它已经达到的数量。我经常发现，将它分解成多个函数有助于将它真正做的事情封装起来，并将递归分开，但这会使递归不那么明显。|1979926|我认为这也有助于使用现实世界的问题，例如遍历目录层次结构或其他树结构。|1979927|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|V|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

Not sure exactly how to tell you to think of it but I think this might help you to grasp what the flow looks like. You get a feel for it after you code it for a while, but a lot of people just avoid it because it makes them feel icky. I apologize that it isnt coded in Java, but its not about the code its about what it prints so just run it on any Linux box or cygwin.

<pre><code> perl -e 'sub foo {my $n =shift;my $depth=shift;print "\t"x$depth;print "blah($n)\n";for(my $i=0;$i&lt;$n;$i++){foo($i,$depth+1)};print "\t"x$depth;print $n,"\n"};foo(shift);' 5
</code></pre>

Called with an arg of 3 this is what it looks like:

<pre><code> blah(3)
 blah(0)
 0
 blah(1)
 blah(0)
 0
 1
 blah(2)
 blah(0)
 0
 blah(1)
 blah(0)
 0
 1
 2
 3
</code></pre>

I try like someone else said to visualize it in smaller components. I.E. What is the function doing besides the recursion. In this case the function is counting from 0 to some number. Now factor in what the recursion does. For each count it starts a new count up to the number it has reached. Often I find that it helps to break it up into more than one function such that the what it really does is encapsulated, and the recursion separate, but this makes the recursion less obvious. 

I think it also helps to use real world problems, such as traversing a directory hierarchy or other tree structure.

blocks|key|1974706|text|所以我将在这里直截了当地说，你要么得到递归，要么得不到递归，这绝对没有错。这只是将程序员(sad+but+true+according+to+Joel)分开的其中一件事。现在，为了解释递归，就像你只有五岁，任务就变得有点模糊了。假设你有四(4)个苹果，每次我让你数一数，你就拿一个苹果给我。我第一次和你说话的时候，你会告诉我你有四个苹果，然后把一个递给我。现在我们继续这个过程，直到你有了零个苹果，这将类似于其他人所说的base+case或exit+statement，这确保了你的函数将会终止。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1974707|现在，你不再是5岁了，如果我要求你证明所有的N实例都是有效的，你会怎么做呢？这就是你的教授所说的通过归纳法解决问题的意思。一个如何通过归纳解决问题的例子如下:我的办公桌上有六罐Mountain+Dew，我正在喝其中的一罐。我说：“哇，这罐露水尝起来像一道电虹。”我会用归纳法说，其他五个罐头，以及所有的山露罐头，尝起来都像是电子彩虹。因此，在递归的情况下，您可以使用相同的过程来证明函数将终止并且是正确的。|1974708|它可能有助于解决问题的“琐碎”实例，例如blah(0)+and+blah(1)+and+blah(2)这将向您展示解决方案在您预期的方向上的趋势，以及您可以使用归纳来说明给定任何输入N时此过程将终止的事实。|1974709|entityMap|0|LINK|mutability|MUTABLE|url|http://www.joelonsoftware.com/articles/GuerrillaInterviewing3.html^0|5U|9|64|E|19|U|0|0|M|1|0|K|V|2J|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@$9|S|A|T|B|C]|$9|U|A|V|B|C]]|D|@$9|W|A|X|1|Y]]|E|$]]|$1|F|3|G|5|6|7|Z|8|@$9|10|A|11|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|12|8|@$9|13|A|14|B|C]|$9|15|A|16|B|C]]|D|@]|E|$]]|$1|J|3|-4|5|6|7|17|8|@]|D|@]|E|$]]]|K|$L|$5|M|N|O|E|$P|Q]]]]

So I will be the blunt one here, you will either get recursion or you wont and there is absolutely nothing wrong with that. It is just one of those things that separates programmers (<a href="http://www.joelonsoftware.com/articles/GuerrillaInterviewing3.html" rel="nofollow">sad but true according to Joel</a>). Now to explain recursion like you are five is where the task becomes a little murky. Imagine you have four (4) apples and every time I ask you to count them you take one of your apples and give it to me. The first time I talk to you you will tell me you have four apples and hand one to me. Now we continue this process until you have zero apples this will be analogous to what others have called the <code>base case</code> or <code>exit statement</code> which ensures that your function will terminate. 

Now, you are no longer five, if I asked you to prove that for all instances of <code>N</code> that this would work how would you do that? This is what your professor is getting at when he states to solve a problem via induction. An example of how to solve by induction would be the following: I have six cans of Mountain Dew on my desk and I am in the process of drinking one of them. I say "Wow this can of Mountain Dew tastes like an electric rainbow." I would use induction to say that the other five cans and by extension all cans of Mountain Dew taste like electric rainbows. So in the case of recursion, you prove that a function will both terminate and be correct utilizing the same process. 

It may help to solve a "trivial" instance of the problem such as <code>blah(0) and blah(1) and blah(2)</code> this will show you that the solution trends in the direction that you anticipate as well as the fact you can use induction to say this process will terminate given any input <code>N</code>.

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:

<pre><code>public void blah(int n)
{
 for (int i = 0; i &lt; n; i++)
 blah(i);
 System.out.print(n);
}
</code></pre>

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 should you approach recursion?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我目前在学校学习递归，当有许多递归调用时，我很难思考方法。我只想问你应该如何看待递归，因为我知道跟踪每一步的方法调用会变得太单调乏味。不是跟踪每个递归调用，我们简要介绍的是通过归纳来思考递归，但我遇到的问题是如何将归纳应用于数学以外的情况。例如，如果有一个方法可以像这样递归地打印数字：public void blah(...

问您应该如何处理递归？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问您应该如何处理递归？EN