CODEWITHSUNDEEP
cloopsrecursioniterationtail-recursion
user11125533
user11125533

Reputation: 39

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

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

Upvotes: 1

Views: 128

Answers (2)

Foobie Bletch
Foobie Bletch

Reputation: 224

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.

Upvotes: 2

McKay M
McKay M

Reputation: 448

Full transparency, I don't know c too well, so I used pseudocode where I didn't know the syntax, but something like this might work?

The general idea of converting recursion to iteration often requires adding objects (in this case, people) that need processing to the stack. You add these objects on some condition (in this case, if they're not too deep in the web of acquaintances).

You then iterate as long as the stack is not empty, popping off the top element and processing it. The 'processing' step usually also consists of adding more elements to the stack.

You are effectively mimicking the 'call stack' which results from a recursive function.

There's more involved in this if you care about the order in which elements are processed, but in this case, it doesn't seem like you do since they're only marked as '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*/)
        }
    }
}

EDIT: Improved code

Upvotes: 1

Related Questions