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

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]

Please add that information (output of both pieces of code) to the question. — cigien
– cigien, Commented Apr 25, 2020 at 1:33
You have to print the output in reverse. So you need to store the numbers somewhere then print it out backwards. — David G
– David G, Commented Apr 25, 2020 at 1:34
as @0x499602D2 suggested your iterative code is printing child to parent. Use an array to store the values and print them in reverse order. — Cherubim
– Cherubim, Commented Apr 25, 2020 at 1:36

linuxfan says Reinstate Monica · Accepted Answer · 2020-04-25 06:56:38Z

1

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.

edited Apr 25, 2020 at 6:56

answered Apr 25, 2020 at 6:18

linuxfan says Reinstate Monica

4,7282 gold badges23 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

NoShady420 Over a year ago

Tested the code. Replace temp = parent[j]; with temp = j. The code misses the last digit. Suggested it as an edit

Java Diva Over a year ago

Tested too, please include the suggestion in your solution so I can mark it as the answer

linuxfan says Reinstate Monica Over a year ago

Thak you @AbhayAravinda and Java, it is curious that a short routine like this is difficult to comprehend totally, but the team working is effective.

Ujjawal Kumar · Accepted Answer · 2020-04-25 07:24:13Z

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:

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):

cdlane · Accepted Answer · 2020-04-25 17:49:07Z

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:

Collectives™ on Stack Overflow

Transform Recursive function to Iterative function

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related