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

Question

I'm having trouble trying to convert this recursive function find_reachable(..) to it's iterative equivalent. I have looked around and saw suggestions to use a stack but cannot figure it out. I also recognize that this function is tail recursive, but don't know what to do with this info. The if statement has me particularly stumped. Any help appreciated, thanks.

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

This looks like a depth-first search: it examines each person by examining that person's first acquaintance, then examining that acquaintance's first acquaintance, and so on before eventually backtracking. Recursion is generally a pretty good strategy for the depth-first search, and most iterative implementations do in fact use a stack to record the addresses of nodes higher up in the tree in order to backtrack to them later. The iterative depth-first search goes like this:

1. Let S be a stack, initially containing only the root of the graph being searched.
2. Pop from the stack into variable v.
3. Push to S all children (or, as they are called in this case, "acquaintances") of v.
4. If the stack is empty, terminate; otherwise, go to step 2.

The simplest way to implement stacks in C is to use a singly linked list, like so:

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

There is one complication here, though! Your function only searches to a given depth. This is the reason why that if statement is there in the first place: to terminate the recursion when the search has gone deep enough. The regular DFS backtracks only when it runs out of children to search, so you'll have to add some extra logic to make it aware of its distance from the root.

You may also want to make sure that an acquaintance is only pushed into the stack if it is not already in the stack. This will save you from redundant iterations—think about what would happen if many of these people have mutual acquaintances.