7 Feb 1996

Outline

Today we'll review recursion, as it's likely to appear on the quiz.

• Deleting from a linked list, recursively
• Deleting characters from a string

Deleting from a linked list

Here's a recursive routine for deleting the first occurence of a string from a linked list of strings.

struct list_el {
  char *word;
  list_el *next;
}

// delete_first returns a pointer to the new start of the list

list_el*
delete_first(list_el *start, char *search_word) {
  list_el *new_start;

  // is the list empty?

  if(start == NULL) return NULL;

  // is the first word the one we want?   

  if(strcmp(start->word, search_word) == 0) {
    new_start = start-> next;
    delete start;
    return new_start;
  }
  
  // recursively search in rest of list

  start->next = delete_first(start->next);
  return start;
}

Now suppose that we want to delete ALL occurrences of a word in a list. How would you modify the previous code to do this?

Here's one answer:

list_el*
delete_all(list_el *start, char *search_word) {
  list_el *new_start;

  if(start == NULL) return NULL;

  if(strcmp(start->word, search_word) == 0) {
    new_start = start->next;
    delete start;
    return delete_all(new_start);
  }
  
  start->next = delete_all(start->next);
  return start;
}

Deleting characters from a string

Consider a similar problem: Suppose that we want to delete all occurrences of a certain character from a string.

What's wrong with this function?

char*
delete_char(char *word, char del_char) {
  if(del_char == '\0') return word; // get serious
  if(word[0] == '\0') return word;  // empty word
  if(word[0] == del_char) return delete_char(word + 1, del_char);
  // we're relying on strcpy to work when the strings overlap!
  strcpy(word + 1, delete_char(word + 1, del_char));
  return word;
}

1. It modifies the string that is passed to it.
2. It relies on strcpy to work when strings overlap (unfortunately, it may not).
3. It does a lot of copying.

Here's a non-recursive (working) way to do the same thing:

char*
delete_char(char *word, char del_char) {
  int length, new_length;
  char *new_word;

  length = strlen(word);  // length does not include the '\0'
  new_word = new char[length + 1];
  strcpy(new_word, word);

  if(del_char == '\0') return new_word;

  // be sure to copy the '\0' at the end

  for(i = 0, new_length = 0; i < length + 1; i++) {
    if(word[i] != del_char) {
      new_word[new_length] = word[i];
      new_length++;
    }
  }
}

A subtle question: Do these functions leak memory? The first may shorten the string, while the second may allocate more space than it really needs. So, some allocated memory goes unused. But when the strings are deleted, all of the unused characters are deleted too.