有没有一个没有递归形式的算法的特征？
有没有一个没有递归形式的算法的特征？
提问于 2018-02-09 00:06:43
这个问题源于二叉树表示法(preorder，postorder，level order等)，其中的.Some可以用递归的形式编写(例如，preorder表示法)，但我不认为有用于level order表示法的递归算法(或者，如果您知道如何实现，请告诉我！)所以我的问题是:有没有一种“类型”的算法不能以递归的形式编写？如果是这样的话，如何描述这种类型的算法呢？(或者，有没有一种系统可以让您编写一个证明，证明某些算法不能以递归方式编写？)
回答 3
Stack Overflow用户
回答已采纳
发布于 2018-02-09 00:12:42
我不一定认为这是this question的副本，但它是一个很好的参考。它提供了一个证明，说明每个迭代算法都可以递归编写。因此，不存在不具有递归形式的算法类别。
Stack Overflow用户
发布于 2018-02-09 00:19:53
while Condition do Statement end 可以等效地写成
to Perform():
if Condition then Statement; Perform() end而且所有的顺序程序都可以递归地重写，而不需要循环。
Stack Overflow用户
发布于 2018-02-09 00:25:38
递归是从基本情况开始的。如果最终结果来自基本情况，则该算法具有递归形式。递归算法通常采用F(n) = G( F(n-1 ) ... )的形式，例如斐波那契级数。F(n) = F(n-1) + F(n-2)。这自然会归入递归形式。
你的问题似乎更多的是关于算法的实现。每一种递归算法都可以递归和非递归地实现。因为递归本身就使用函数堆栈。您可以在非递归形式的实现中显式使用相同的堆栈。
因此，您可以使用递归和非递归形式轻松地实现预排序、后序和按序。
说到级别顺序，我相信你也可以用递归的形式实现它。例如(可能不是完全正确的形式)。
void printLevelOrder( int level, Queue<Node> q ) {
if ( !q.isEmpty() ) {
Node curr = q.peek();
int size = q.size();
System.out.print( "At level " + level + " : " );
for ( int i = 0; i < size; i++ ) {
System.out.println( q.poll().toString() );
}
for ( Node child : curr.children() ) {
q.add( child );
}
}
printLevelOrder( level + 1, q );
}但重点是算法的实现和数学形式是不同的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/48689840
复制相关文章
相似问题
腾讯云开发者
