0

我想知道如何（或者即使可能）在没有调用自身的单独函数的情况下实现递归。到目前为止，我见过的所有实现递归的算法都使用单独的函数。我想了很多，想出了一个想法，即带有一些可变突变的 goto 语句可以完成这项工作，但我真的不确定。我做了一个小型研究，发现了关于这个结构化编程定理的信息 ，它证明了每个算法都可以只用三个数据结构来实现，所以这样的递归实现必须是可行的，但我仍然不能将所有东西组装成一致的知识和对整体的理解- 接近。

4

3 回答 3

2

您正在寻找的基本上是将递归函数表达为迭代形式。这可以通过使用堆栈轻松完成。这是一个非常简单的 C# 示例：

int NodeCount(Node n)
{
      if (n.Visited) return 0; // This node was visited through another node, discard
      n.Visited = true;
      int res = 1;
      foreach (Node ni in n.Children) // Recurse on each node
      {
            res += NodeCount(ni); // Add the number of sub node for each node
      }
      return res;           
}

这是迭代形式的完全相同的函数：

int NodeCount(Node root)
{
    int res = 0;
    Stack<int> stk = new Stack<int>();
    stk.Push(root) // We start with the root node
    while( stk.Count > 0) // While we still have nodes to visit
    {
          Node current = stk.Pop(); // Get the node on top of the stack
          current.Visited = true;  // Mark it as visited
          res ++; // Add one to the count
          foreach (Node ni in n.Children) // Push all non visited children to the stack
          {     
                if (ni.Visited == false) 
                        stk.Push(ni);
          }

    }
    return res;
}
于 2012-09-21T20:24:41.673 回答
1

在没有调用自身的单独函数的情况下实现递归。

是的，可以将递归算法转换为迭代算法。但是为什么要使用goto语句呢？当您进行函数调用时，生成的程序集有一个分支指令可以跳转到类似于goto.
因此，您将完成的工作与机器代码最终将完成的工作有些相似，这样做的好处是避免了堆栈帧调用，而使用goto.
如果要避免递归，请使用迭代。你是怎么想出这个问题的？

于 2012-09-21T20:24:20.283 回答
1

您可以使用任何基于堆栈的语言在没有函数的情况下执行某种递归。例如，在 Forth 中，您可以这样编写斐波那契函数：

：斐波那契 0 1 10 0 做 2dup + rot 。循环交换。. ;

该程序递归地生成斐波那契数列的 10 次迭代，每次迭代都使用前一次迭代的输入。没有调用任何函数。

于 2012-09-21T21:21:09.110 回答