algorithm - 在没有单独函数的情况下实现递归

Question

我想知道如何(或者即使可能)在没有调用自身的单独函数的情况下实现递归。 到目前为止，我见过的所有实现递归的算法都使用一个单独的函数。我想了很多，想出了一个带有一些可变突变的 goto 语句可以完成这项工作的想法，但我真的不确定。 我做了一个小调查，找到了关于这个的信息 Structured programming theorem这证明每个算法都可以只用三个数据结构来实现，所以这样的递归实现一定是可行的，但我仍然无法将所有内容组合成一致的知识和对整个可能方法的理解。

Answer 1

您正在寻找的基本上是将递归函数表达为迭代形式。这可以通过使用堆栈轻松完成。这是一个非常简单的 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;
}