我看到大多数编程语言教程都通过使用一个简单的例子来教授递归，即如何生成斐波那契数列，我的问题是，除了生成斐波那契数列之外，还有另一个很好的例子来解释递归是如何工作的吗？
问问题
15038 次
23 回答
38
经典的是二叉树搜索：
def findval (node,val):
if node == null:
return null
if node.val = val:
return node
if node.val > val:
return findval (node.left,val)
return findval (node.right,val)
findval (root,thing_to_find)
这可能比一个简单的公式复杂一点，但它是递归的“面包和黄油”使用，它说明了使用它的最佳位置，即递归级别最小化的地方。
我的意思是：您可以添加两个非负数：
def add (a,b):
if b == 0:
return a
return add (a+1,b-1)
但是你会发现自己很快就会用完大量的堆栈空间（当然，除非编译器优化了尾端递归，但你可能应该忽略你关心的教学水平）。
于 2011-02-09T12:58:03.087 回答
29
其他答案提到了各种算法，这完全可以，但是如果您想要更多“具体”示例，则可以列出某个目录及其子目录中的所有文件。分层文件系统是递归（树）结构的著名示例，您可以使用此具体示例显示深度优先和广度优先搜索。
于 2011-02-09T13:20:50.317 回答
26
我最喜欢的递归示例是河内塔：要将一堆棋子从极点 A 移动到极点 B，您将最低棋子上方的所有东西移动到不是 A 或 B 的柱子，然后将最低棋子移到 B，然后然后你移动你放在最低块顶部的“辅助杆”上的堆栈。对于第一步和第三步，您将递归地遵循此指令。请参阅链接以获得更长的解释:)
于 2011-02-09T13:07:21.763 回答
20
检查回文：
bool recursivePalindrome(std::string str, unsigned int index = 0) {
if (index > str.length()/2) return true;
else if (str[index] == str[str.length()-index-1])
return recursivePalindrome(str, ++index);
else return false;
}
或者在不太严重的情况下:)
void StackOverflow()
{
StackOverflow();
}
于 2011-02-09T12:59:02.777 回答
16
如何找到阶乘。
int GetFactorial(int n )
{
if ( n==0) return 1;
return n*GetFactorial(n-1);
}
这个想法是，阶乘被递归地定义为 n 和 (n-1) 的阶乘的乘积。从递归定义中，你得到你的递归。
于 2011-02-09T12:59:12.613 回答
12
作为文件系统的一部分遍历目录树的文件夹层次结构是一个很好的真实示例。查看此 SO 帖子以获取 C++ 示例：
于 2011-02-09T13:15:53.877 回答
10
- 这里给出的大多数其他示例都是数学示例，它们实际上只是重新说明了递归的相同应用。
- 搜索和排序变体是很好的算法示例，但对于初学者来说通常有点过于复杂。
- 河内塔是经典，但确实很做作。
=================
我用来演示递归的简单功能的示例是目录树中的递归文件处理。
这是一个 C# 示例
void ProcessFiles( string sFolder )
{
foreach( string f in Directory.GetFiles( sFolder ) )
{
DoSomethingTo( f );
}
foreach( string d in Directory.GetDirectories( sFolder ))
{
ProcessFiles( d );
}
}
于 2011-02-09T16:34:47.837 回答
10
合并排序是一个很好的算法示例，它在递归实现时更易于阅读和理解。
这是合并排序的高级伪代码版本：
def merge_sort(List sortlist)
if sortlist.length <= 1 return sortlist
split sortlist into leftlist and rightlist
return merge(merge_sort(leftlist), merge_sort(rightlist))
def merge(List leftlist, List rightlist)
while(leftlist and rightlist not empty)
compare leftlist.first to rightlist.first
pop lowest value off its list and append to resultlist
append any remains of leftlist onto resultlist
append any remains of rightlist onto resultlist
return resultlist
其迭代版本的编写和可视化要复杂得多。
于 2011-02-09T13:04:09.063 回答
5
递归的好例子通常与底层数据结构或问题本身是递归的情况有关：树、图、使用分而治之的算法（如许多种类）、递归语法的解析器（如常见的算术表达式）、找到策略类似国际象棋的两人游戏（举个简单的例子，考虑 Nim）、组合问题等。
于 2011-02-09T15:44:59.227 回答
3
算术表达式的评估可以使用堆栈递归或迭代地完成。比较这两种方法可能很有启发性。
于 2011-02-09T13:13:34.087 回答
3
尝试递归二进制搜索： http ://www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html
或递归快速排序： http ://www.dreamincode.net/forums/topic/72311-recursive-quicksort-algorithm/
这些只是递归函数的广阔世界中的两个小例子。
于 2011-02-09T12:59:35.163 回答
1
我记得我通过编写一个搜索 单词阶梯的程序来理解递归。在给定的字典中。
于 2011-02-09T18:27:07.357 回答
1
我的岳母参加了 C 的入门课程。她有一个家庭作业问题，例如：
你有一根金属条（长度为 len），还有一些订单（n）将金属切割成各种长度。您希望最大限度地使用金属量，但不能超过总长度。
讲师建议以二进制形式从 1 迭代到 2**n，如果相应位为 0，则排除订单，如果其位为 1，则包括订单，同时跟踪最大和。他的提议将在多项式时间内运行。
使用递归背包算法存在另一种解决方案。您可以从 len 向下迭代到 1 并进行深度优先搜索以递归地找到长度的总和。
我使用递归的另一个领域是霍夫曼编码（用于压缩字符串），但这没有背包问题的直观感觉。
递归是一个完全不同的绝妙概念。祝您学习或教授它。
于 2011-02-09T14:39:48.780 回答
1
任何有层次的东西。例如，列出你老板下面的所有员工。
于 2011-02-09T17:20:46.040 回答
1
阿克曼函数：
/* undefined if m and n are negative */
uint32 ackermann( uint32 m, uint32 n )
{
if( m < 0 && n < 0 ) { exit(1); /* invalid m and n */ }
if( m == 0 ){ return n + 1; }
if( m > 0 && n == 0 ){ return ackermann( m - 1, 1 ); }
if( m > 0 && n > 0 ){ return ackermann( m - 1, ackermann(m, n - 1) ); }
}
m > 0 的多重比较是多余的（可以简化）。然而，让它们保持原样显示了 Ackermann 函数的标准定义。
但是，除了斐波那契数之外，人们不必走得太远就能找到有趣的递归函数。
您拥有最大公分母 (GDC) 函数、快速排序和始终典型的二进制搜索算法。
于 2011-02-09T17:00:34.817 回答
1
于 2011-02-09T17:24:44.030 回答
1
显然，它不是 C++，但这个概念是合理的：
PHP递归遍历嵌套多维数组：
public function recurse_me($collection) {
foreach ($collection as $value) {
if (is_array($value)) {
$this->recurse_me($value);
} else {
// process value.
}
}
}
于 2011-02-09T17:43:03.253 回答
0
链接节点类型结构上的许多操作可以是递归的。其他人提到了 BST，但如果您不想解释它们是什么，请考虑在线性未排序列表中搜索最大值：
int MaxValue(Node node)
{
if (node == null)
return 0;
if (node.Next == null)
return node.Value;
int maxNext = MaxValue(node.Next);
return node.Value > maxNext ? node.Value : maxNext;
}
列表（在本例中为链表）在现实世界中很容易解释；您的听众甚至不必具有编程背景。您可以简单地将其描述为一组未排序的框或数字列表。
于 2011-02-09T17:05:15.220 回答
0
学术例子是阶乘
嗯！
计算。在现实生活中，您会获得数学库。
于 2011-02-09T12:57:54.420 回答
0
堆排序也是一个很好的例子。您可以在 Cormen、Rivest 和其他人的“算法简介”中阅读它。很棒的书，我希望你能从中找到很多有趣的东西。
于 2011-02-09T13:06:45.630 回答
0
有一些排序算法依赖于递归。
然后，是用递归实现的二分查找。
于 2011-02-09T12:59:09.237 回答
0
于 2011-02-09T13:01:58.830 回答