我在学校里很难理解递归。每当教授谈论它时，我似乎都明白了，但是当我自己尝试时，它完全让我大吃一惊。
我整晚都在试图解决河内塔问题，完全让我大吃一惊。我的教科书只有大约 30 页的递归，所以它不是太有用。有谁知道可以帮助澄清这个话题的书籍或资源？
Confused
问问题
88548 次
20 回答
633
你如何清空一个装有五朵花的花瓶？
答：如果花瓶不是空的，你就拿出一朵花，然后你倒空一个装有四朵花的花瓶。
你如何清空一个装有四朵花的花瓶？
答：如果花瓶不是空的，你取出一朵花，然后倒空一个装有三朵花的花瓶。
你如何清空一个装有三朵花的花瓶？
答：如果花瓶不是空的，你就取出一朵花，然后你倒空一个装有两朵花的花瓶。
你如何清空一个装有两朵花的花瓶？
答：如果花瓶不是空的，则取出一朵花，然后将一个装有一朵花的花瓶倒空。
你如何清空一个装有一朵花的花瓶？
答：如果花瓶不是空的，你取出一朵花，然后你把一个没有花的花瓶倒空。
你如何清空一个没有鲜花的花瓶？
答：如果花瓶不是空的，你拿出一朵花，但花瓶是空的，你就完成了。
那是重复的。让我们概括一下：
你如何清空一个装有N朵花的花瓶？
答：如果花瓶不是空的，则取出一朵花，然后将一个装有N-1朵花的花瓶倒空。
嗯，我们可以在代码中看到吗？
void emptyVase( int flowersInVase ) {
if( flowersInVase > 0 ) {
// take one flower and
emptyVase( flowersInVase - 1 ) ;
} else {
// the vase is empty, nothing to do
}
}
嗯，我们不能在 for 循环中完成吗？
为什么，是的，递归可以用迭代代替，但递归通常更优雅。
让我们谈谈树木。在计算机科学中，树是由节点组成的结构，其中每个节点都有一定数量的子节点，这些子节点也是节点，或者为空。二叉树是由恰好有两个孩子的节点组成的树，通常称为“左”和“右”；再次，孩子可以是节点，也可以是空的。根是不是任何其他节点的子节点的节点。
想象一个节点，除了它的孩子之外，还有一个值，一个数字，并想象我们希望对某棵树中的所有值求和。
要对任何一个节点的值求和，我们会将节点本身的值添加到其左孩子的值（如果有）和其右孩子的值（如果有）。现在回想一下，孩子们，如果他们不为空，也是节点。
因此，要对左子节点求和，我们会将子节点本身的值与其左子节点的值（如果有）和右子节点的值（如果有）相加。
因此，要对左孩子的左孩子的值求和，我们会将子节点本身的值加上它的左孩子的值（如果有的话）和它的右孩子的值（如果有的话）。
或许你已经预料到我会用这个去哪里，并且想看一些代码？好的：
struct node {
node* left;
node* right;
int value;
} ;
int sumNode( node* root ) {
// if there is no tree, its sum is zero
if( root == null ) {
return 0 ;
} else { // there is a tree
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
}
}
请注意，我们不是显式测试子节点以查看它们是 null 还是节点，而是让递归函数为 null 节点返回零。
假设我们有一棵看起来像这样的树（数字是值，斜杠指向子节点，@ 表示指针指向 null）：
5
/ \
4 3
/\ /\
2 1 @ @
/\ /\
@@ @@
如果我们在根（值为 5 的节点）上调用 sumNode，我们将返回：
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;
让我们就地展开它。在我们看到 sumNode 的任何地方，我们都将其替换为 return 语句的扩展：
sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;
return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + sumNode(null ) + sumNode( null )
+ sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + sumNode(null ) + sumNode( null )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 + sumNode(null ) + sumNode( null ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 + 0 + 0 ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 ;
return 5 + 4
+ 2 + 0 + 0
+ 1
+ 3 ;
return 5 + 4
+ 2
+ 1
+ 3 ;
return 5 + 4
+ 3
+ 3 ;
return 5 + 7
+ 3 ;
return 5 + 10 ;
return 15 ;
现在看看我们如何通过将其视为复合模板的重复应用来征服任意深度和“分支”的结构？每次通过我们的 sumNode 函数，我们只处理一个节点，使用一个 if/then 分支，以及两个几乎直接从我们的规范中编写出来的简单 return 语句？
How to sum a node:
If a node is null
its sum is zero
otherwise
its sum is its value
plus the sum of its left child node
plus the sum of its right child node
这就是递归的力量。
上面的花瓶示例是尾递归的示例。尾递归意味着在递归函数中，如果我们递归（也就是说，如果我们再次调用该函数），那是我们做的最后一件事。
树的例子不是尾递归的，因为即使我们做的最后一件事是递归右孩子，在我们这样做之前我们递归了左孩子。
事实上，我们调用子节点的顺序以及添加当前节点的值根本不重要，因为加法是可交换的。
现在让我们看一下顺序确实很重要的操作。我们将使用节点的二叉树，但这次保存的值将是一个字符，而不是一个数字。
我们的树将有一个特殊的属性，即对于任何节点，它的字符在其左孩子所持有的字符之后（按字母顺序）和在其右孩子所持有的字符之前（按字母顺序）。
我们要做的是按字母顺序打印树。考虑到树的特殊属性，这很容易做到。我们只打印左孩子，然后是节点的字符，然后是右孩子。
我们不只是想随意打印，所以我们将传递给我们的函数一些东西来打印。这将是一个带有 print(char) 函数的对象；我们不需要担心它是如何工作的，只要调用 print 时，它会在某个地方打印一些东西。
让我们在代码中看看：
struct node {
node* left;
node* right;
char value;
} ;
// don't worry about this code
class Printer {
private ostream& out;
Printer( ostream& o ) :out(o) {}
void print( char c ) { out << c; }
}
// worry about this code
int printNode( node* root, Printer& printer ) {
// if there is no tree, do nothing
if( root == null ) {
return ;
} else { // there is a tree
printNode( root->left, printer );
printer.print( value );
printNode( root->right, printer );
}
Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );
除了现在很重要的操作顺序之外，这个例子还说明我们可以将事物传递给递归函数。我们唯一要做的就是确保在每次递归调用中，我们继续传递它。我们将节点指针和打印机传递给函数，并且在每次递归调用时，我们将它们“向下”传递。
现在，如果我们的树看起来像这样：
k
/ \
h n
/\ /\
a j @ @
/\ /\
@@ i@
/\
@@
我们将打印什么？
From k, we go left to
h, where we go left to
a, where we go left to
null, where we do nothing and so
we return to a, where we print 'a' and then go right to
null, where we do nothing and so
we return to a and are done, so
we return to h, where we print 'h' and then go right to
j, where we go left to
i, where we go left to
null, where we do nothing and so
we return to i, where we print 'i' and then go right to
null, where we do nothing and so
we return to i and are done, so
we return to j, where we print 'j' and then go right to
null, where we do nothing and so
we return to j and are done, so
we return to h and are done, so
we return to k, where we print 'k' and then go right to
n where we go left to
null, where we do nothing and so
we return to n, where we print 'n' and then go right to
null, where we do nothing and so
we return to n and are done, so
we return to k and are done, so we return to the caller
因此，如果我们只看我们打印的行：
we return to a, where we print 'a' and then go right to
we return to h, where we print 'h' and then go right to
we return to i, where we print 'i' and then go right to
we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
we return to n, where we print 'n' and then go right to
我们看到我们打印了“ahijkn”，它确实是按字母顺序排列的。
我们只需知道如何按字母顺序打印单个节点，就可以按字母顺序打印整个树。这只是（因为我们的树具有将值按字母顺序排列在后面的值的左侧的特殊属性）知道在打印节点的值之前打印左孩子，并在打印节点的值之后打印右孩子。
这就是递归的力量：能够通过只知道如何做整体的一部分（以及知道何时停止递归）来完成所有的事情。
回想一下，在大多数语言中，运算符 || ("or") 在其第一个操作数为真时短路，一般递归函数为：
void recurse() { doWeStop() || recurse(); }
卢克 M 评论：
所以应该为这种答案创建一个徽章。恭喜！
谢谢，卢克！但是，实际上，因为我对这个答案进行了四次以上的编辑（添加最后一个示例，但主要是为了更正拼写错误并润色它——在一个小的上网本键盘上打字很难），我不能再得到任何分数了. 这在某种程度上阻止了我在未来的答案中投入尽可能多的精力。
于 2009-04-04T21:19:46.340 回答
37
你的大脑爆炸了，因为它进入了无限递归。这是一个常见的初学者错误。
信不信由你，你已经理解了递归，你只是被一个常见但错误的函数隐喻拖累：一个装着进出东西的小盒子。
思考而不是任务或过程，例如“在网上了解有关递归的更多信息”。这是递归的，你没有问题。要完成此任务，您可以：
a) 阅读 Google 的“递归”结果页面 b) 阅读后，点击第一个链接，然后... a.1）阅读关于递归的新页面 b.1）一旦您阅读了它，请点击它的第一个链接并... a.2）阅读关于递归的新页面 b.2）一旦您阅读了它，请点击上面的第一个链接并...
如您所见，您长期以来一直在做递归的事情，没有任何问题。
你会继续做这个任务多久？永远直到你的大脑爆炸？当然不是，只要你相信你已经完成了任务，你就会停在一个给定的点上。
当要求您“了解有关网络递归的更多信息”时，无需指定这一点，因为您是人类，您可以自己推断。
计算机无法推断出杰克，所以你必须包含一个明确的结尾：“在网上找到更多关于递归的信息，直到你理解它或者你最多阅读了 10 页”。
您还推断您应该从 Google 的“递归”结果页面开始，这也是计算机无法做到的。我们递归任务的完整描述还必须包括一个明确的起点：
“在网上了解有关递归的更多信息，直到您理解它或您已阅读最多 10 页并从 www.google.com/search?q=recursion 开始”
为了了解整个事情，我建议您尝试以下任何书籍：
- Common Lisp：符号计算的简单介绍。这是递归最可爱的非数学解释。
- 小谋士。
于 2009-04-04T21:05:36.173 回答
26
要了解递归，您所要做的就是查看洗发水瓶的标签：
function repeat()
{
rinse();
lather();
repeat();
}
这样做的问题是没有终止条件，递归将无限重复，或者直到你用完洗发水或热水（外部终止条件，类似于吹你的堆栈）。
于 2009-04-04T21:18:31.413 回答
12
如果你想要一本能很好地用简单的术语解释递归的书，可以看看道格拉斯·霍夫施塔特的Gödel, Escher, Bach: An Eternal Golden Braid，特别是第 5 章。除了递归之外，它还很好地解释了递归以易于理解的方式解释计算机科学和数学中的许多复杂概念，一种解释建立在另一种之上。如果你以前没有接触过这些概念，那它可能是一本非常令人兴奋的书。
于 2009-04-04T20:45:23.320 回答
9
这更像是一个抱怨而不是一个问题。您对递归有更具体的问题吗？就像乘法一样，它不是人们经常写的东西。
说到乘法，想想这个。
问题：
a*b 是什么？
回答：
如果 b 为 1，则为 a。否则，它是 a+a*(b-1)。
什么是 a*(b-1)？有关解决问题的方法，请参见上述问题。
于 2009-04-04T20:19:53.583 回答
9
我认为这个非常简单的方法应该可以帮助您理解递归。该方法将调用自身，直到某个条件为真，然后返回：
function writeNumbers( aNumber ){
write(aNumber);
if( aNumber > 0 ){
writeNumbers( aNumber - 1 );
}
else{
return;
}
}
此功能将打印出从您输入的第一个数字到 0 的所有数字。因此：
writeNumbers( 10 );
//This wil write: 10 9 8 7 6 5 4 3 2 1 0
//and then stop because aNumber is no longer larger then 0
基本上发生的事情是 writeNumbers(10) 将写入 10 然后调用 writeNumbers(9) 将写入 9 然后调用 writeNumber(8) 等。直到 writeNumbers(1) 写入 1 然后调用 writeNumbers(0) 将写入 0 butt 不会调用 writeNumbers(-1);
此代码与以下代码基本相同：
for(i=10; i>0; i--){
write(i);
}
那么为什么要使用递归，你可能会问，如果 for 循环本质上是相同的。好吧，当您必须嵌套 for 循环但不知道它们嵌套多深时，您通常会使用递归。例如，当从嵌套数组中打印出项目时：
var nestedArray = Array('Im a string',
Array('Im a string nested in an array', 'me too!'),
'Im a string again',
Array('More nesting!',
Array('nested even more!')
),
'Im the last string');
function printArrayItems( stringOrArray ){
if(typeof stringOrArray === 'Array'){
for(i=0; i<stringOrArray.length; i++){
printArrayItems( stringOrArray[i] );
}
}
else{
write( stringOrArray );
}
}
printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'
这个函数可以接受一个可以嵌套到 100 层的数组，而你编写一个 for 循环则需要你嵌套它 100 次：
for(i=0; i<nestedArray.length; i++){
if(typeof nestedArray[i] == 'Array'){
for(a=0; i<nestedArray[i].length; a++){
if(typeof nestedArray[i][a] == 'Array'){
for(b=0; b<nestedArray[i][a].length; b++){
//This would be enough for the nestedAaray we have now, but you would have
//to nest the for loops even more if you would nest the array another level
write( nestedArray[i][a][b] );
}//end for b
}//endif typeod nestedArray[i][a] == 'Array'
else{ write( nestedArray[i][a] ); }
}//end for a
}//endif typeod nestedArray[i] == 'Array'
else{ write( nestedArray[i] ); }
}//end for i
如您所见，递归方法要好得多。
于 2009-04-04T21:04:21.387 回答
9
实际上，您使用递归来降低手头问题的复杂性。您应用递归，直到达到可以轻松解决的简单基本情况。有了这个，您可以解决最后一个递归步骤。并通过所有其他递归步骤解决您的原始问题。
于 2009-04-04T21:04:37.110 回答
7
我将尝试用一个例子来解释它。
你知道什么！方法？如果没有：http ://en.wikipedia.org/wiki/Factorial
3！= 1 * 2 * 3 = 6
这里有一些伪代码
function factorial(n) {
if (n==0) return 1
else return (n * factorial(n-1))
}
所以让我们尝试一下：
factorial(3)
n 是 0 吗？
不！
所以我们用我们的递归深入挖掘：
3 * factorial(3-1)
3-1 = 2
是 2 == 0？
不！
所以我们更深入！3 * 2 * 阶乘(2-1) 2-1 = 1
是 1 == 0？
不！
所以我们更深入！3 * 2 * 1 * 阶乘(1-1) 1-1 = 0
是 0 == 0？
是的！
我们有一个小案例
所以我们有 3 * 2 * 1 * 1 = 6
我希望对你有帮助
于 2009-04-04T20:46:23.800 回答
5
递归
方法 A，调用方法 A 调用方法 A。最终，这些方法 A 中的一个不会调用并退出，但它是递归，因为某些东西会调用自己。
我想打印出硬盘上的每个文件夹名称的递归示例：（在 C# 中）
public void PrintFolderNames(DirectoryInfo directory)
{
Console.WriteLine(directory.Name);
DirectoryInfo[] children = directory.GetDirectories();
foreach(var child in children)
{
PrintFolderNames(child); // See we call ourself here...
}
}
于 2009-04-04T20:22:59.270 回答
5
递归函数只是一个函数，它可以根据需要多次调用自身。如果您需要多次处理某事，这很有用，但您不确定实际需要多少次。在某种程度上，您可以将递归函数视为一种循环。但是，就像循环一样，您需要指定要中断进程的条件，否则它将变为无限。
于 2009-04-04T20:50:01.030 回答
4
构建递归函数的真正数学方法如下：
1：假设你有一个函数对 f(n-1) 是正确的，构建 f 使得 f(n) 是正确的。2：构建 f，使得 f(1) 是正确的。
这就是你如何证明这个函数在数学上是正确的，它被称为Induction。相当于有不同的基本情况，或者对多个变量有更复杂的函数）。也等价于想象 f(x) 对所有 x 都是正确的
现在举一个“简单”的例子。构建一个函数，它可以确定是否有可能有 5 美分和 7 美分的硬币组合来赚取 x 美分。例如，2x5 + 1x7 可能有 17 美分，但不可能有 16 美分。
现在假设你有一个函数告诉你是否可以创建 x 美分，只要 x < n。调用此函数 can_create_coins_small。想象如何为 n 制作函数应该相当简单。现在构建你的函数：
bool can_create_coins(int n)
{
if (n >= 7 && can_create_coins_small(n-7))
return true;
else if (n >= 5 && can_create_coins_small(n-5))
return true;
else
return false;
}
这里的诀窍是要意识到 can_create_coins 适用于 n 的事实，意味着您可以用 can_create_coins 代替 can_create_coins_small，给出：
bool can_create_coins(int n)
{
if (n >= 7 && can_create_coins(n-7))
return true;
else if (n >= 5 && can_create_coins(n-5))
return true;
else
return false;
}
最后要做的一件事是有一个基本案例来停止无限递归。请注意，如果您尝试创建 0 美分，则可以通过没有硬币来实现。添加此条件给出：
bool can_create_coins(int n)
{
if (n == 0)
return true;
else if (n >= 7 && can_create_coins(n-7))
return true;
else if (n >= 5 && can_create_coins(n-5))
return true;
else
return false;
}
可以证明此函数将始终返回，使用一种称为无限下降的方法，但这不是必需的。你可以想象 f(n) 只调用较低的 n 值，并且最终总是会达到 0。
要使用此信息来解决您的河内塔问题，我认为诀窍是假设您具有将 n-1 个平板电脑从 a 移动到 b 的功能（对于任何 a/b），尝试将 n 个表从 a 移动到 b .
于 2009-04-05T11:49:26.330 回答
4
你用的是哪本书？
真正优秀的算法标准教科书是 Cormen & Rivest。我的经验是它很好地教授递归。
递归是编程中较难掌握的部分之一，虽然它确实需要直觉，但它是可以学习的。但它确实需要一个好的描述、好的例子和好的插图。
此外，一般来说 30 页很多，单一编程语言的 30 页令人困惑。在您从一般书籍中了解递归之前，不要尝试学习 C 或 Java 中的递归。
于 2009-04-04T20:14:05.267 回答
4
http://javabat.com是一个有趣且令人兴奋的递归练习场所。他们的示例从相当简单的开始，并且经过广泛的工作（如果您想走那么远）。注意：他们的方法是通过练习来学习。这是我编写的一个递归函数，用于简单地替换 for 循环。
for 循环：
public printBar(length)
{
String holder = "";
for (int index = 0; i < length; i++)
{
holder += "*"
}
return holder;
}
这是做同样事情的递归。（注意我们重载了第一个方法以确保它像上面一样使用）。我们还有另一种方法来维护我们的索引（类似于上面 for 语句为您所做的方式）。递归函数必须维护自己的索引。
public String printBar(int Length) // Method, to call the recursive function
{
printBar(length, 0);
}
public String printBar(int length, int index) //Overloaded recursive method
{
// To get a better idea of how this works without a for loop
// you can also replace this if/else with the for loop and
// operationally, it should do the same thing.
if (index >= length)
return "";
else
return "*" + printBar(length, index + 1); // Make recursive call
}
长话短说，递归是编写更少代码的好方法。在后面的 printBar 中，请注意我们有一个 if 语句。如果我们的条件已经达到，我们将退出递归并返回上一个方法，然后返回上一个方法，等等。如果我发送一个 printBar(8)，我得到 ********。我希望通过一个与 for 循环执行相同操作的简单函数的示例，这可能会有所帮助。不过，您可以在 Java Bat 上进行更多练习。
于 2009-04-04T20:54:21.050 回答
3
Common Lisp中的简单递归示例：
MYMAP 将函数应用于列表中的每个元素。
1）空列表没有元素，所以我们返回空列表 - () 和 NIL 都是空列表。
2)将该函数应用于第一个列表，为列表的其余部分调用 MYMAP（递归调用）并将两个结果合并到一个新列表中。
(DEFUN MYMAP (FUNCTION LIST)
(IF (NULL LIST)
()
(CONS (FUNCALL FUNCTION (FIRST LIST))
(MYMAP FUNCTION (REST LIST)))))
让我们看看跟踪的执行。在输入函数时，会打印参数。退出函数时，将打印结果。对于每个递归调用，输出将按级别缩进。
此示例对列表 (1 2 3 4) 中的每个数字调用 SIN 函数。
Command: (mymap 'sin '(1 2 3 4))
1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
| 3 Enter MYMAP SIN (3 4)
| | 4 Enter MYMAP SIN (4)
| | 5 Enter MYMAP SIN NIL
| | 5 Exit MYMAP NIL
| | 4 Exit MYMAP (-0.75680256)
| 3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)
这是我们的结果：
(0.841471 0.9092975 0.14112002 -0.75680256)
于 2009-04-04T21:43:31.353 回答
3
孩子隐含地使用递归，例如：
前往迪斯尼世界的公路旅行
我们到了吗？（没有）
我们到了吗？（很快）
我们到了吗？（几乎……）
我们到了吗？(SHHHH)
我们到了吗？（！！！！！）
这时候孩子睡着了...
这个倒计时功能是一个简单的例子：
function countdown()
{
return (arguments[0] > 0 ?
(
console.log(arguments[0]),countdown(arguments[0] - 1)) :
"done"
);
}
countdown(10);适用于软件项目的霍夫施塔特定律也是相关的。
根据乔姆斯基的说法，人类语言的本质是有限大脑产生他认为是无限语法的能力。他的意思不仅是我们可以说的内容没有上限，而且我们的语言的句子数量没有上限，任何特定句子的大小都没有上限。乔姆斯基声称，构成人类语言所有这些创造力的基本工具是递归：一个短语在同一类型的另一个短语中重复出现的能力。如果我说“John's Brother's house”，我有一个名词“house”，它出现在一个名词短语“brother's house”中，而该名词短语出现在另一个名词短语“John's Brother's house”中。这很有意义，而且它
参考
于 2012-08-30T23:26:04.577 回答
3
要向 6 岁的孩子解释递归，先向 5 岁的孩子解释，然后再等一年。
实际上，这是一个有用的反例，因为您的递归调用应该更简单，而不是更难。向 5 岁的孩子解释递归会更加困难，虽然你可以在 0 处停止递归，但你没有简单的解决方案来向 0 岁的孩子解释递归。
要使用递归解决问题，首先将其细分为一个或多个可以以相同方式解决的更简单问题，然后当问题简单到无需进一步递归即可解决时，您可以返回到更高级别。
事实上，这是一个关于如何用递归解决问题的递归定义。
于 2011-09-17T05:10:51.513 回答
2
哎哟。去年我试图弄清楚河内塔。TOH 的棘手之处在于它不是一个简单的递归示例——你有嵌套的递归，它也会在每次调用中改变塔的角色。我能让它变得有意义的唯一方法是在我的脑海中想象出环的运动，并用语言表达递归调用将是什么。我会从一个戒指开始，然后是两个，然后是三个。我实际上在互联网上订购了游戏。我大概花了两三天的时间才得到它。
于 2009-04-05T00:09:24.467 回答
2
在使用递归解决方案时，我总是尝试：
- 首先建立基本情况，即在阶乘解中 n = 1 时
- 尝试为所有其他情况提出一般规则
还有不同类型的递归解决方案，分和征服方法对分形和许多其他方法很有用。
如果您可以先解决更简单的问题以掌握其中的窍门，那也会有所帮助。一些示例是求解阶乘并生成第 n 个斐波那契数。
作为参考，我强烈推荐 Robert Sedgewick 的 Algorithms。
希望有帮助。祝你好运。
于 2009-04-04T20:43:59.563 回答
1
递归函数就像一个弹簧，每次调用都会压缩一点。在每个步骤中，您将一些信息（当前上下文）放在堆栈上。当到达最后一步时，弹簧被释放，立即收集所有值（上下文）！
不确定这个比喻是否有效...... :-)
无论如何，除了有点人为的经典例子（阶乘是最糟糕的例子，因为它效率低下且容易变平，斐波那契，河内......）有点人为（我很少，如果有的话，在实际编程案例中使用它们），它是有趣的是看看它在哪里真正使用。
一个非常常见的情况是走一棵树（或一个图，但一般来说，树更常见）。
例如，文件夹层次结构：要列出文件，您需要对它们进行迭代。如果您找到子目录，则列出文件的函数会以新文件夹作为参数调用自身。当从列出这个新文件夹（及其子文件夹！）返回时，它会恢复其上下文，到下一个文件（或文件夹）。
另一个具体案例是绘制 GUI 组件的层次结构时：通常有容器（如窗格）来保存组件，这些组件也可以是窗格，或复合组件等。绘制例程递归调用每个组件的绘制函数，它调用它所拥有的所有组件的绘制函数，等等。
不确定我是否很清楚，但我喜欢展示教学材料在现实世界中的使用，因为这是我过去偶然发现的东西。
于 2009-04-04T20:55:06.120 回答
1
想想工蜂。它试图制造蜂蜜。它完成了它的工作，并期望其他工蜂生产剩下的蜂蜜。当蜂窝充满时，它就会停止。
把它想象成魔法。您有一个与您尝试实现的功能同名的功能，当您给它子问题时，它会为您解决它，您唯一需要做的就是将您的部分的解决方案与它的解决方案集成给你。
例如，我们要计算一个列表的长度。让我们调用我们的函数magic_length 和我们的魔法助手魔法长度我们知道，如果我们给出没有第一个元素的子列表，它将通过魔法给我们子列表的长度。那么我们唯一需要考虑的就是如何将这些信息与我们的工作结合起来。第一个元素的长度是 1，magic_counter 给了我们子列表 n-1 的长度，因此总长度是 (n-1) + 1 -> n
int magical_length( list )
sublist = rest_of_the_list( list )
sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
return 1 + sublist_length
然而，这个答案是不完整的，因为我们没有考虑如果我们给出一个空列表会发生什么。我们认为我们拥有的列表总是至少有一个元素。因此，如果我们得到一个空列表并且答案显然是 0，我们需要考虑答案应该是什么。所以将此信息添加到我们的函数中，这称为基础/边缘条件。
int magical_length( list )
if ( list is empty) then
return 0
else
sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
return 1 + sublist_length
于 2011-09-07T09:12:35.873 回答