时间戳

首页 > 解决方案 > 将递归函数转换为迭代函数

c - 将递归函数转换为迭代函数

问题描述

我正在尝试将此递归函数转换为迭代函数

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

标签： calgorithmrecursioniteration

解决方案

警告，（它是......）未经测试的代码:-)

如评论中所述，递归函数以某种方式遍历数组，直到它停止，同时在堆栈中记住所有段落：只有这样它才开始打印。所以你应该使用一个数组来保存中间结果。

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，因为它首先打印，然后检查。

希望这会有所帮助，我试图纠正错误并实施反转。

推荐阅读