除了生成Fibonacci序列之外,递归的一个很好的例子是什么？

Question

可能的重复:
递归的真实
示例递归函数的示例

我看到,通过一个简单的例子是如何产生的斐波那契序列大多数编程语言教程教递归,我的问题是,有没有比产生Fibonacci序列解释递归是如何工作之外的另一个很好的例子？

Answer 1

经典是二叉树搜索:

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 2

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

Answer 3

我最喜欢的递归的例子是河内塔:要摆脱极A到B极片的堆栈,你的一举一动都最低的一块,是不是A或B极上面,然后将最低片到B,然后你移动你放在最低部分顶部的"辅助杆"的堆栈.对于第一步和第三步,您将递归地遵循此指令.请参阅链接以获得更长的解释:)

Answer 4

检查一个palyndrome:

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 5

怎么样找到阶乘.

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

这个想法是,因子被递归地定义为n和(n-1)的阶乘的乘积.从递归定义,你得到你的递归.

Answer 6

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

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

Answer 7

合并排序是一种非常好的算法示例,在递归实现时更易于阅读和理解.

这是Merge Sort的一个高级伪代码版本:

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 8

• 这里给出的大多数其他示例都是数学示例,它们实际上只是重新说明了相同的递归应用.
• 搜索和排序变体是很好的算法示例,但对于初学者来说往往有点过于复杂.
• 河内的塔楼是一个经典但非常人为的设计.

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

我用来演示递归的简单功能的例子是目录树中的递归文件处理.

这是一个C#示例

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

Answer 9

有几个样本:

加泰罗尼亚语数字:

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.

简单的迷宫问题

找出哈密顿路径问题

阶乘.

你可以看到其他参考的维基页面.

Answer 10

递归的好例子通常与底层数据结构或问题本身是递归的情况有关:树,图,使用分而治之法的算法(如许多种类),递归语法的解析器(如常见的算术表达式),查找策略象棋般的两个玩家游戏(一个简单的例子考虑Nim),组合问题等.