除了生成斐波那契数列之外，还有什么递归的好例子？

Question

可能的重复：
现实世界中的递归示例
递归函数示例

我发现大多数编程语言教程都通过使用一个简单的示例来教授递归，即如何生成斐波那契数列，我的问题是，除了生成斐波那契数列之外，还有另一个很好的例子来解释递归是如何工作的吗？

Answer 1

检查回文：

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();
}

Answer 2

求阶乘怎么样。

int GetFactorial(int n )
{
  if ( n==0) return 1;
  return n*GetFactorial(n-1);
}

这个想法是，阶乘被递归地定义为 n 和 (n-1) 阶乘的乘积。从递归定义中，你可以得到递归。

Answer 3

遍历作为文件系统一部分的目录树的文件夹层次结构是一个很好的实际示例。查看此 SO 帖子中的 C++ 示例：

为什么我在递归删除目录时遇到问题？

Answer 4

• 这里给出的大多数其他例子都是数学例子，它们实际上只是重新说明了递归的相同应用。
• 搜索和排序变体是很好的算法示例，但对于初学者来说通常有点太复杂。
• 河内塔是一部经典作品，但确实很做作。

================

我用来演示递归的简单威力的示例是目录树中的递归文件处理。

这是一个 C# 示例

void ProcessFiles( string sFolder )
{
    foreach( string f in Directory.GetFiles( sFolder ) )
    {
        DoSomethingTo( f );
    }
    foreach( string d in Directory.GetDirectories( sFolder ))
    {
        ProcessFiles( d );
    }
}

Answer 5

合并排序是一个很好的算法示例，当递归实现时更容易阅读和理解。

这是合并排序的一个高级伪代码版本：

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

它的迭代版本的编写和可视化要复杂得多。

Answer 6

有几个示例：

加泰罗尼亚数字：

T(n) = Sum(T(i)*T(n-i)) for all 1 <= i < n

阿克曼函数：

A(x,y) = y+1 (if x = 0)
A(x,y) = A(x-1,1) (if y=0)
A(x,y) = A(x-1, A(x,y-1)) otherwise.

简单迷宫问题 >

寻找哈密顿路径问题

阶乘。

您可以查看 wiki 页面以获取其他参考。

Answer 7

递归的好例子通常与底层数据结构或问题本身是递归的情况相关：树、图、使用分而治之方法的算法（如许多排序）、递归语法的解析器（如常见的算术表达式）、查找策略类似国际象棋的两人游戏（举个简单的例子，考虑一下 Nim）、组合问题等。

Answer 8

尝试递归二分搜索：
http://www.fredosaurus.com/notes-cpp/algorithms/searching /rbinarysearch.html

或者递归快速排序：
http://www.dreamincode.net/forums/topic/72311- recursive-quicksort-algorithm/

这些只是递归函数的广阔世界中的两个小例子。

Answer 9

算术表达式的计算可以使用堆栈递归或迭代地完成。比较这两种方法非常有启发性。

Answer 10

我记得我通过编写一个程序来理解递归，该程序搜索单词梯子。在给定的字典中。

Answer 11

我的岳母参加了 C 语言的入门课程。她有一个家庭作业问题，比如：

你有一根金属条（长度为len）和一个数字
将金属切割成的订单数 (n)
各种长度。你想要最大化
所使用的金属量，但是
不能超过总长度。

讲师建议以二进制形式从 1 迭代到 2**n，如果相应位为 0，则排除一个订单，如果相应位为 1，则包括一个订单，同时跟踪最大和。他的提议将在多项式时间内运行。

另一种解决方案是使用递归背包算法。您可以从 len 向下迭代到 1 并进行深度优先搜索以递归地查找长度之和。

我使用递归的另一个领域是 Huffman 编码（用于压缩字符串），但是这没有背包问题的直观感受。

递归是一个完全不同的奇妙概念。祝愿您学习或教授它。

Answer 12

阿克曼函数：

/* 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 是多余的（并且可以简化）。然而，让它们保持原样，会显示阿克曼函数的标准定义。

但人们不必脱离数学边缘那么远就能找到除斐波那数之外的有趣的递归函数。

您拥有最大公约数 (GDC) 函数、快速排序和始终典型的二分搜索算法。

Answer 13

任何事物都具有层次结构。
例如列出你老板下面的所有员工。

Answer 14

递归在数学归纳法中找到了基础，并且应该这样教授。

通过列表处理可以清楚地暴露通过归纳法定义的函数。关于 fold 有很多话要说例如。

然后，转向树木。

Answer 15

显然，它不是 C++，但概念很合理：

PHP 递归遍历嵌套多维数组：

public function recurse_me($collection) {
    foreach ($collection as $value) {
        if (is_array($value)) {
            $this->recurse_me($value);
        } else {
            // process value.
        }
    }
}

Answer 16

学术上的例子是阶乘

n！

计算。
在现实生活中，你会得到数学库。

Answer 17

有些排序算法依赖于递归。

然后，还有使用递归实现的二分搜索。

Answer 18

帕斯卡三角形

Answer 19

堆排序也是一个很好的例子。你可以在 Cormen、Rivest 等人的《算法导论》中阅读相关内容。很棒的书，我希望你会从中发现很多有趣的东西。

Answer 20

链接节点类型结构上的许多操作可以是递归的。其他人提到了 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;
}

列表（在本例中为链接列表）在实际中非常容易解释 -世界术语；您的观众甚至不必具有编程背景。您可以简单地将其描述为一组未排序的框或数字列表。

Answer 21

经典的是二叉树搜索：

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)

但是您会发现自己很快就用完了大数字的堆栈空间（当然，除非编译器优化了尾端递归，但对于您所关心的教学水平，您可能应该忽略这一点）。

Answer 22

其他答案提到了各种算法，这完全没问题，但是如果您想要更多“具体”示例，您可以列出某个目录及其子目录中的所有文件。分层文件系统是递归（树）结构的一个众所周知的示例，您可以使用这个具体示例来显示深度优先和广度优先搜索。

Answer 23

我最喜欢的递归示例是 河内塔：从杆子上移动一堆棋子A 到杆 B，将最低棋子上方的所有棋子移动到非 A 或 B 的杆子，然后将最低的棋子移动到 B，然后将放在最低棋子顶部的“辅助杆”上的堆栈移动到片。对于第一步和第三步，您将递归地遵循此说明。请参阅链接以获得更长的解释:)