Как мне преобразовать эту рекурсивную функцию в итеративную? - PullRequest
Новая
       64

Как мне преобразовать эту рекурсивную функцию в итеративную?

1 голос
/ 05 мая 2020

У меня проблемы с преобразованием этой рекурсивной функции 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];
}

Ответы [ 2 ]

2 голосов
/ 06 мая 2020

Это похоже на поиск в глубину: он исследует каждого человека, исследуя первое знакомство этого человека, затем исследуя первое знакомство этого знакомого, и так далее, прежде чем в конечном итоге вернуться. Рекурсия, как правило, является довольно хорошей стратегией для поиска в глубину, и большинство итеративных реализаций фактически используют стек для записи адресов узлов выше в дереве, чтобы вернуться к ним позже. Итеративный поиск в глубину выглядит следующим образом:

  1. Пусть S будет стеком, изначально содержащим только root просматриваемого графа.
  2. Выталкивать из стека в переменную v .
  3. Pu sh в S всех потомков (или, как их в данном случае называют, «знакомых») v .
  4. Если стек пуст, завершить работу; в противном случае go к шагу 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 выполняет возврат только тогда, когда у него заканчиваются дочерние элементы для поиска, поэтому вам придется добавить несколько дополнительных logi c, чтобы он знал о своем расстоянии от root.

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

1 голос
/ 05 мая 2020

Полная прозрачность, я не знаю c слишком хорошо, поэтому я использовал псевдокод, в котором я не знал синтаксиса, но что-то вроде этого может сработать?

Общая идея преобразования рекурсии в итерация часто требует добавления в стек объектов (в данном случае людей), требующих обработки. Вы добавляете эти объекты при определенных условиях (в данном случае, если они не слишком глубоко в сети знакомых).

Затем вы выполняете итерацию, пока стек не пуст, извлекая верхний элемент и обрабатывая его. Этап «обработки» обычно также состоит из добавления дополнительных элементов в стек.

Вы фактически имитируете «стек вызовов», который возникает в результате рекурсивной функции.

В этом больше вовлечено, если вам важен порядок, в котором обрабатываются элементы, но в этом случае не похоже, что вы это делаете, поскольку они помечены только как «достижимые». 

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*/)
        }
    }
}

EDIT: улучшенный код

...