我如何将这个递归函数转换为迭代函数？

Question

我在尝试将此递归函数 find_reachable(..) 转换为其等效的迭代函数时遇到问题。我环顾四周，看到了使用堆栈的建议，但无法弄清楚。我也认识到这个函数是尾递归的，但不知道如何处理这个信息。 if 语句让我特别难过。感谢任何帮助，谢谢。

void find_reachable(struct person *current, int steps_remaining,
                              bool *reachable){
    // mark current root person as reachable
    reachable[person_get_index(current)] = true;
    // now deal with this person's acquaintances
    if (steps_remaining > 0){
        int num_known = person_get_num_known(current);
        for (int i = 0; i < num_known; i++){
            struct person *acquaintance = person_get_acquaintance(current, i);
            find_reachable(acquaintance, steps_remaining - 1, reachable);
        }
    }
}
.....
struct person {
  int person_index; // each person has an index 0..(#people-1)
  struct person ** known_people;
  int number_of_known_people;
};

// return the person's unique index between zero and #people-1
int person_get_index(struct person * p) {
  return p->person_index;
}

// return the number of people known by a person
int person_get_num_known(struct person * p) {
  return p->number_of_known_people;
}

// get the index'th person known by p
struct person * person_get_acquaintance(struct person * p, int index) {
  //fprintf(stderr, "index %d, num_known %d\n", index, p->number_of_known_people);
  assert( (index >= 0) && (index < p->number_of_known_people) );
  return p->known_people[index];
}

Answer 1

完全透明，我不太了解c，所以我在我不知道语法的地方使用了伪代码，但是这样的东西可能有用吗？

将递归转换为迭代的一般思路通常需要将需要处理的对象（在本例中为人）添加到堆栈中。您在某些情况下添加这些对象（在这种情况下，如果它们在熟人网络中不是太深）。

然后只要堆栈不为空就进行迭代，弹出顶部元素并处理它。 'processing' 步骤通常还包括向堆栈添加更多元素。

您实际上是在模仿 'call stack' 由递归函数产生的结果。

如果您关心元素的处理顺序，则涉及更多内容，但在这种情况下，您似乎并不关心，因为它们仅被标记为 'reachable'。

void find_reachable(struct person *current, int steps_remaining, bool *reachable){

    stack = /* create a new stack which contains a (person, int) touple or struct */

    stack.push(/* current & steps_remaining*/)

    while (/*stack is not empty*/) {
        currentStruct = /* pop the top of stack */
        current = currentStruct.person
        depth = currentStruct.depth

        reachable[person_get_index(current)] = true;

        if (depth - 1 <= 0) {
            continue;
            // don't add this person's aquantances b/c we're 'steps_remaining' levels in
        }

        int num_known = person_get_num_known(current);
        for (int i = 0; i < num_known; i++){
            struct person *acquaintance = person_get_acquaintance(current, i);
            stack.add(/*acquantance & depth - 1*/)
        }
    }
}

编辑：改进代码

Answer 2

这看起来像一个 depth-first 搜索：它通过检查每个人的第一个熟人来检查每个人，然后检查那个熟人的第一个熟人，依此类推，最后回溯。递归通常是 depth-first 搜索的一个很好的策略，大多数迭代实现实际上使用堆栈来记录树中较高节点的地址，以便稍后回溯到它们。迭代 depth-first 搜索是这样的：

令 S 为堆栈，最初仅包含正在搜索的图的根。
从堆栈弹出到变量v.
推送到 S 所有 children（或者，在这种情况下，它们被称为 "acquaintances"） v.
如果栈为空，则终止；否则，转到步骤 2。

在 C 中实现堆栈的最简单方法是使用单链表，如下所示：

struct person_stack;
struct person_stack {
    struct person *who;
    struct person_stack *next;
};

struct person *person_stack_pop(struct person_stack **s) {
    struct person_stack *old_top = *s;
    struct person *who = old_top->who;
    *s = *s->next;
    free(old_top);
    return who;
}

struct person_stack *person_stack_push(struct person_stack **s, struct person *p) {
    struct person_stack *new_top = malloc(sizeof (struct person_stack));
    new_top->next = *s;
    new_top->who = p;
    *s = new_top;
    return *s;
}

不过这里有一个复杂的问题！您的函数仅搜索给定的深度。这就是为什么 if 语句首先出现的原因：当搜索足够深时终止递归。常规 DFS 仅在用完 children 进行搜索时才回溯，因此您必须添加一些额外的逻辑以使其了解其与根的距离。

您可能还想确保仅当熟人不在堆栈中时才将其推入堆栈。这将使您免于重复迭代——想想如果这些人中有许多人相互认识会发生什么。

我如何将这个递归函数转换为迭代函数？

How would I convert this recursive function to an iterative one?

c

iteration

recursion

loops

tail-recursion