algorithm - 如何仅使用循环来执行不特定数量的嵌套循环

Question

假设我有一个实现循环和递归的函数:

public void Foo(int para1, int para2, bool is_leaf_node)
{
   if(is_leaf_node)
       //do something
   else
   {
       //do something 
       while(some_condition)
       {
           //assign variable to be passed to next recursive call
           Foo(para1_next,para2_next,is_leaf_node_next);
       }
   }
}

使用这种类型的设计，我可以进行不特定数量的嵌套循环。结果是这样的:

while(condition1)
{
   //do something
   while(condition2)
   {
      //do something
      //keep nested looping 
      //until the last one (is_leaf_node == true) which don't have a while loop
   }
}

但是从我在线阅读的内容 (this question) 来看，他们中的大多数人似乎都同意使用递归可以完成的事情也可以使用循环来完成(如果获取输出是唯一关心的问题)。答案/评论说“基本上，做循环而不是递归意味着手动处理堆栈”，但实际上，在这种情况下我如何“处理堆栈”？我需要指针或任何其他东西才能做到这一点吗？

有些人可能会问“既然可以用递归完成，为什么还要使用循环？在什么情况下你只能使用循环？”。好吧，我只是好奇如何只使用循环而不使用递归来完成这件事。

谁能提供一个设计:

1. 只循环
2. 没有任何递归
3. 可以执行不特定数量的嵌套循环

提前致谢。

编辑:

假设我们有一个正整数参数 nested，它告诉程序需要多少个嵌套循环。

例如，如果 nested == 3，算法将产生类似这样的结果:

while(condition1)
    while(condition2)
        while(condition3)
             //do something

如果 嵌套 == 4

while(condition1)
    while(condition2)
        while(condition3)
            while(condition4)
                //do something

如果嵌套== 0

//do something

图片说明:

让我们以循环树状结构为例。在此图像中，树的高度是2，这也代表需要的嵌套循环数量和嵌套前面的描述 ，它也是平衡二叉树，所以只使用循环，我们可以做这样的事情。

int i =0;
while(i<2)
{
    int j =0;
    while(j<2)
    {
       //do something, ie:
       std::cout<<arr[i][j];
       j++;
    }
    i++;
}

其中i表示Level 1的索引，j表示Level 2的索引。

但是，如果 Height of tree 或 depth of tree 在执行之前是未知的并且不平衡怎么办？树在第一条向下路径上可以有 3 层，在第二条向下路径上可以有 5 层。我能想到的唯一解决方案是实现递归和循环，看起来像我在第一个代码部分中陈述的代码。因此，如果不使用递归，我们如何循环遍历一个 height 或 depth 未知的树状结构，它不需要平衡并从根部开始？

Answer 1

总体方案:

Initialize state storage
Loop:
   Extract state and  check - should we continue?
       Yes: 
            do work
            change state
       No:
            break

对于您的示例，状态存储包含一些条件的列表。在每个级别我们都有级别的索引作为状态并且可以检查相应的条件。

像你的图片显示的树结构，可以用递归和 with iterative approach using stack 遍历。 (或队列)存储。

---

考虑 QuickSort 的递归和迭代版本(实现 taken from geeksforgeek)。

第二个版本实现了显式堆栈并再现了递归堆栈的隐式操作。

我看到的唯一区别 - 迭代版本不会将 0/1 长度范围放在堆栈上，而递归版本总是进行递归调用，但在 if (l >= h)

/* A[] --> Array to be sorted,  
l --> Starting index,  
h --> Ending index */

void quickSort(int A[], int l, int h) 
{ 
    if (l < h) { 
        /* Partitioning index */
        int p = partition(A, l, h); 
        quickSort(A, l, p - 1); 
        quickSort(A, p + 1, h); 
    } 
} 
void quickSortIterative(int arr[], int l, int h) 
{ 
    // Create an auxiliary stack 
    int stack[h - l + 1]; 

    // initialize top of stack 
    int top = -1; 

    // push initial values of l and h to stack 
    stack[++top] = l; 
    stack[++top] = h; 

    // Keep popping from stack while is not empty 
    while (top >= 0) { 
        // Pop h and l 
        h = stack[top--]; 
        l = stack[top--]; 

        // Set pivot element at its correct position 
        // in sorted array 
        int p = partition(arr, l, h); 

        // If there are elements on left side of pivot, 
        // then push left side to stack 
        if (p - 1 > l) { 
            stack[++top] = l; 
            stack[++top] = p - 1; 
        } 

        // If there are elements on right side of pivot, 
        // then push right side to stack 
        if (p + 1 < h) { 
            stack[++top] = p + 1; 
            stack[++top] = h; 
        } 
    } 
}