Преобразование рекурсивной функции в итеративную функцию

Question

Я пытаюсь преобразовать эту рекурсивную функцию в итерационную

void printPath(int parent[], int j) 
{ 

    // Base Case
    if (parent[j] == - 1) 
        return; 

    printPath(parent, parent[j]); 

    printf("%d ", j); 
}

Это ВЫХОД

0 1
0 1 2
0 1 2 3
0 7 6 5 4
0 7 6 5
0 7 6
0 7
0 1 2 8

Это то, что я пробовал, но вывод неправильный

void printPath(int parent[], int j) 
{   
    int temp = parent[j];

    while (temp != - 1)
    {
        temp = parent[temp];
        printf("%d ", temp);

    }
} 

Это ВЫХОД [неверно]

0 -1
0 0 -1
0 1 0 -1
0 6 7 0 -1
0 7 0 -1
0 0 -1
0 -1
0 1 0 -1

Answer 1

Предупреждение, (это был ...) непроверенный код: -)

Как указано в комментарии, рекурсивная функция каким-то образом обходит массив, пока не достигнет остановки, запоминая в стопке все отрывки: только потом он начинает печатать. Таким образом, вы должны использовать массив для хранения промежуточных результатов.

void printPath(int parent[], int j) {
  int  revert[V];    // to reverse; "V" is a costant (==9, size of vector)
  int  count=0;      // perhaps not needed, is assumed to always reach V
  int  temp;

  // unroll and store
  temp = j;         // edited; my temp=parent[j] was wrong
  while (temp) {
    revert[count++] = temp;
    temp = parent[temp];
  }

  // print reversed
  while (count) {
    count--;
    printf("%d ", revert[count]);
  }
}

Я не уверен, что эта процедура работает, не может проверить сейчас. В исходном искушении произошла ошибка, потому что при выполнении

    temp = parent[temp];
    printf("%d ", temp);

он выводит даже -1, потому что сначала печатает, а затем проверяет.

Надеюсь, это поможет, я попытался исправить ошибка и реализуем задний ход.

Answer 2

Прежде чем иметь дело с итеративным, ваше рекурсивное решение нуждается в исправлении, так как оно не может отобразить путь для дочернего элемента 0:

void printPath_recursive(int parent_of[], int child)
{
    int parent = parent_of[child];

    if (parent != -1)
    {
        printPath_recursive(parent_of, parent);
    }

    printf("%d ", child); 
}

Итеративное решение в том же духе, которое предложили люди:

int parent_map[] = {-1, 0, 1, 2, 5, 6, 7, 0, 2};

#define PARENT_MAP_LENGTH (sizeof(parent_map) / sizeof(parent_map[0]))

void printPath_iterative(int parent_of[], int child) 
{
    int s = 0, ancestry[PARENT_MAP_LENGTH];

    while (child != -1)
    {
        ancestry[s++] = child;

        child = parent_of[child];
    }

    while (s > 0)
    {
        printf("%d ", ancestry[--s]);
    }
}

Вывод для:

0
0 1
0 1 2
0 1 2 3
0 7 6 5 4
0 7 6 5
0 7 6
0 7
0 1 2 8

Answer 3

В соответствии с вашим вопросом, я получаю родительский массив как:

int parent[] = {-1,0,1,2,5,6,7,0,2};

Я также запускаю ваш код:

void printPath(int parent[], int j) 
{   
    int temp = parent[j];

    while (temp != - 1)
    {
        temp = parent[temp];
        printf("%d ", temp);

    }
} 

Теперь отметим три вещи:

1) Инициализируйте int temp = j, а не parent[j]. Это гарантирует, что вы начинаете с вашего пути с j, а не с parent[j].

2) Вместо этого:

temp = parent[temp];
printf("%d ", temp);

сделайте это:

printf("%d ", temp);
temp = parent[temp];

Это гарантирует, что вы сначала напечатаете j, а затем parent [j].

После внесения вышеуказанных изменений ваш вывод будет выглядеть следующим образом:

1 0 
2 1 0 
3 2 1 0 
4 5 6 7 0 
5 6 7 0 
6 7 0 
7 0 
8 2 1 0 

Теперь последняя заметка.

3) Чтобы получить желаемый результат, вам нужно распечатать в обратный порядок. Один из способов - сначала посчитать элементы на пути. Затем создайте массив такого размера. Перейдите снова, начиная с j, и сохраните элементы в массиве. После этого вы можете распечатать массив в обратном порядке.

После внесения этих изменений мы получим следующий код:

void printPath(int parent[], int j) 
{   
    // Initialized temp from j
    int temp = j;

    // int variable that will store the number of elements in path
    int cnt=0;

    // traversing the path for first time to get count of elements in path
    while (temp != - 1)
    {
        cnt++;
        temp = parent[temp];
    }

    // creating array of cnt size
    int arr[cnt];

    // traversing the path for second time.
    // this time we will store elements in the array
    temp = j;
    int i=0;

    while(temp!=-1){
        arr[i++]=temp;
        temp = parent[temp];
    }

    // printing the elements in reverse order
    for(int i=cnt-1;i>=0;i--)
        printf("%d ",arr[i]);
} 

Приведенный выше код даст вам правильный вывод (как вы упомянули) :

0 1 
0 1 2 
0 1 2 3 
0 7 6 5 4 
0 7 6 5 
0 7 6 
0 7 
0 1 2 8