Как сделать неопределенное количество вложенных циклов, используя только циклы

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
   }
}

Но из того, что я читаю онлайн ( этот вопрос ), похоже, что большинство из них согласны с тем, что то, что можно сделать с помощью рекурсии, может быть сделано также с использованием циклов (если единственной проблемой является получение выходных данных). В ответе / комментарии говорится, что «по сути, создание циклов вместо рекурсии означает ручную обработку стека», но практически, как мне «обработать стек» в этом сценарии? Нужен ли мне указатель или что-то еще для этого?

Кто-то может спросить: «Зачем использовать цикл, если вы можете сделать с рекурсией? В какой ситуации вы можете использовать только цикл?». Ну, мне просто любопытно, как это можно сделать, используя только циклы без рекурсии.

Может ли кто-нибудь предоставить дизайн:

1. только петля
2. без рекурсии
3. может выполнять неопределенное число вложенных циклов

Заранее спасибо.

РЕДАКТИРОВАТЬ:

Давайте рассмотрим положительный целочисленный параметр nested, который сообщает программе, сколько нужно вложенных циклов.

Например, алгоритм выдаст что-то вроде этого, если nested == 3:

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

Если nested == 4

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

Если nested == 0

//do something

Описание изображения:

Давайте возьмем зацикливание древовидной структуры в качестве примера. На этом изображении Height of tree - это 2, что также представляет amount of nested loop needed и nested в предыдущем описании, и это также сбалансированное двоичное дерево, поэтому, используя только циклы, мы можем сделать что-то подобное.

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

Для вашего примера состояние хранилища содержит список некоторых условий. На каждом уровне у нас есть индекс уровня как состояния и мы можем проверить соответствующее условие.

Древовидная структура, как показано на рисунке, может быть пройдена как с помощью рекурсии, так и с итеративным подходом с использованием стека (или очереди).

---

Рассмотрим рекурсивные и итеративные версии QuickSort (реализация взята из 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; 
        } 
    } 
}