Transform Recursive function to Iterative function

Question

I am trying to convert this recursive function to an iterative one

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

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

    printPath(parent, parent[j]); 

    printf("%d ", j); 
}

This is the OUTPUT

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

This is what I have tried but the output is incorrect

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

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

    }
} 

This is the OUTPUT [incorrect]

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

Before dealing with an iterative one, your recursive solution needs a fix as it can't display the path for child 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); 
}

The iterative solution is along the lines that folks have suggested:

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]);
    }
}

Output for either:

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 2

According to your question, I get the parent array as:

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

I also run your code :

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

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

    }
} 

Now three things to note:

1) Initialize int temp = j and not with parent[j]. This makes sure that you start with your path from j and not from parent[j].

2) Instead of doing this:

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

do this:

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

This makes sure that you first print j and then parent[j].

After making the above changes your output will look like this:

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 

Now the last note.

3) To get the desired output you need to print in reverse order. One way is to first count the elements in the path. Then create an array of that size. Traverse again starting from j and store the elements in the array. After that you can print the array in reverse order.

After making these changes we get the following code:

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]);
} 

The above code will give you the correct output (as you mentioned):

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

Warning, (it was...) untested code :-)

As stated in comment, the recursive function walks the array in some way, until it reaches a stop, while remembering in the stack all the passages: only then it starts to print. So you should use an array to hold the intermediate results.

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]);
  }
}

I am not sure that this routine works, can not test now. In your original temptative there was an error because by doing

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

it outputs even a -1, because it first prints, and then checks.

Hope this helps, I tried to correct the error and implement the reversing.