Introduction to Pointers, Structures and Linked-Lists Part 6

Introduction to Pointers, Structures and Linked-Lists Part 6
Introduction to Recursion
by Chris Bennett aka Dwarfsoft

Well, it has been a while since my last article. I have been holidaying away from regular Internet access. I had hoped to cover multiple indirection for advanced pointer use, but my advanced topic kept crashing my computer. I was looking for a more straightforward way of completing the task, but I decided to just give you a quick look at recursive functions.

"What is a recursive function?" I hear you ask. Well, 'recursion' is a term that is used to mean that a function will call itself until it finally reaches a conclusion and unwinds itself all the way back through its calls. I do not think that words are going to describe this as well as examples.

int RecursiveFunction (int i);
int RecursiveFunction (int i)
{
  printf("%d\n", i);
  if (i) RecursiveFunction(i-1);
  printf("%d\n", i);
  return i;
}

This is a reasonable example of simple recursion. The first line is the prototype of the function, and this must be placed up the top of your code. Effectively, all of your prototypes should be up the top of your code or in your header files. The output of a call to this function if called "RecursiveFunction(5);" would be "5,4,3,2,1,0,0,1,2,3,4,5" where the numbers are on alternating lines. Recursive functions can be used for finding out if a sentence is a palindrome or in our case for sorting a Linked List. Here is a look at a palindrome checker.

int IsPalindrome (char str[80]);
int IsPalindrome (char str[80])
{
  // Return true if this is the last letter
  if (strlen(str) == 1) return -1;

  printf("%c with %c\n", str[0], str[strlen(str)-1]);

  char buf[80];
  // Return false if the alternate letters are not the same
  if (str[0] != str[strlen(str)-1]) return (0);

  // Sending the substring
  strcpy(buf, &str[1]);
  buf[strlen(buf)-1] = NULL;

  // Return the result of the Recursive call
  return IsPalindrome(buf);
}

Obviously this function needs "string.h" to be included with it, but you can get the idea. This function recursively calls itself back to the return statement. This is so that the true (-1) or false (0) value that is sent back makes its way to the calling function so that we can determine if the sentence is a palindrome or not. For example, if we fed the sentence "SATAN OSCILLATE MY METALLIC SONATAS" without the spaces into our function like this:

if (IsPalindrome("SATANOSCILLATEMYMETALLICSONATAS"))
  printf("Is a Palindrome");

Then you get the output telling you that it is a Palindrome. There is a printing function in the IsPalindrome function so that you may track the progress of the recursions. Hopefully after studying this for a little while you will get the hang of recursive functions.

Now, I did promise to rewrite the sorting function to be recursive. I actually wrote two versions that are recursive. The original function was long and at times very difficult to understand. Before I give you what I promised, here is the structure that we are dealing with, a doubly linked list:

typedef struct strAddress *AddressPtr_t;
typedef struct strAddress
{
  char Name[31];
  char Address[181];
  char PhoneNo[13];
  AddressPtr_t Next,Prev;
} Address_t;

The first rewrite of the original function was longer, but it was broken into three functions that were all required to do the original work. It was only slightly more readable:

AddressPtr_t SortByNameInit(AddressPtr_t Cur)
{
  //Get to the beginning again
  while (Cur && Cur->Prev)
    Cur = Cur->Prev;
  return Cur;
}

AddressPtr_t SortByNameRecursion(AddressPtr_t Cur)
{
  // The middle loop iteration pointer
  AddressPtr_t Iter = Cur;

  // A boolean value for remembering whether the list was modified or not
  bool Changed = false;

  // Start the Sort
  // If there exists an element, Iter is the next element
  if (Iter) Iter->Next;
  // Reset the Modified switch for this iteration
  while (Iter)
  {
    // If it belongs before Cur, put it there
    if (strcmp(Cur->Name,Iter->Name) > 0)
    {
      // Remove Iter from its location
      if (Iter->Next) Iter->Next->Prev = Iter->Prev;
      Iter->Prev->Next = Iter->Next;
      
      // Insert Iter before Cur
      Iter->Prev = Cur->Prev;
      if (Iter->Prev) Iter->Prev->Next = Iter;
      Iter->Next = Cur;
      Cur->Prev = Iter;
      
      // Set modified flag
      Changed = true;
    }
    // Next iteration
    Iter = Iter->Next;
  }
  if (!Cur || !Changed)
  {
    // Basically keeps iterating until there are no changes and Cur = NULL
    return SortByNameInit(Cur);
  } else if (Changed)
  {
    Cur = SortByNameInit(Cur);		
    return SortByNameRecursion(Cur);
  } else
  {
    // Go to the next value
    if (Cur) return SortByNameRecursion(Cur->Next);
  }
  return SortByNameInit(Cur);
}

AddressPtr_t SortByName(AddressPtr_t Cur)
{
  Cur = SortByNameInit(Cur);
  Cur = SortByNameRecursion(Cur);
  return Cur;
}

SortByName() is called just the same is it was before, but the execution of it is slightly different. The highlighted lines above show where the recursive functions are. I tend to call a function recursively mostly on or after a return operator. The second rewrite of the sort function is broken up into four different functions. It is the most easily read of the group. It does not require deep tabbing to keep code blocks apart:

AddressPtr_t Shuffle(AddressPtr_t Cur)
{
  // This is the reverse of what was happening in SortByNameRec
  // because we are now sorting backwards
  AddressPtr_t Iter, Last = Cur;
  Iter = Last->Prev;

  // Search backwards down the list for the spot to put Cur
  while (Iter && (strcmp(Iter->Name, Cur->Name) > 0))
  {
    // Keep hurtling backwards down the list
    Iter = Last->Prev;
    if (Iter) Last = Iter;
  }

  // If we aren't at the beginning of the list
  if (Iter)
  {
    // Instert Cur this far back down the list
    if (Cur->Prev) Cur->Prev->Next = Cur->Next;
    if (Cur->Next) Cur->Next->Prev = Cur->Prev;
    if (Iter->Next) Iter->Next->Prev = Cur;
    Iter->Next = Cur;
    Cur->Next = Iter->Next;
    Cur->Prev = Iter;
  } else if (Last)
  {
    // If this is the beginning of the list,
    // insert Cur at the beginning
    if (Cur->Prev) Cur->Prev->Next = Cur->Next;
    if (Cur->Next) Cur->Next->Prev = Cur->Prev;
    
    Last->Prev = Cur;
    Cur->Next = Last;
    Cur->Prev = NULL;
  }
  return Cur;
}


AddressPtr_t SortByNameRec(AddressPtr_t Cur)
{
  AddressPtr_t Iter = NULL;
  // Ensure that we actually have a Cur before defining an Iter
  if (Cur) Iter = Cur->Next;
  
  // Ensure that we have an Iter before attempting a comparison
  if (Iter)
    // See if there needs to be a swap
    if (Iter && (strcmp(Cur->Name, Iter->Name) > 0))
    {
      // Shuffle moves Iter down the list
      Shuffle(Iter);
      // Start sorting list from here onwards
      return SortByNameRec(Cur);
    } else
      // Sort from Next Item onwards
      return SortByNameRec(Cur->Next);
  return Cur;
}

AddressPtr_t SortByNameInit(AddressPtr_t Cur)
{
  // return to the head of the list
  while (Cur && Cur->Prev)
    Cur = Cur->Prev;

  return Cur;
}

AddressPtr_t SortByName(AddressPtr_t Cur)
{
  // Reorder the list to its head
  Cur = SortByNameInit(Cur);

  // Do the recursion sort
  Cur = SortByNameRec(Cur);

  // Reorder the list to its head
  Cur = SortByNameInit(Cur);
  return (Cur);
}

This is longer than the original, but I think you will agree with me that it is MUCH easier to read. I have decided to include the original function to underline my point. The original function is located at the end of this file before my conclusion. Anyway, the functionality of the above code is slightly different from the original. It is more efficient. Instead of just moving Iter behind Cur if they need to be swapped, the Shuffle function basically drops Iter down the list as far as it will go and therefore keeping the list behind Cur sorted. It also makes for pleasant reading. It is much healthier on the eyes.

int SortByName(AddressPtr_t Cur)
{
  // The middle loop iteration pointer
  AddressPtr_t Iter = Cur;

  // A boolean value for remembering whether the list was modified or not
  bool Changed;

  //Get to the beginning again
  while (Cur && Cur->Prev)
    Cur = Cur->Prev;

  // Start the Sort
  // If there exists an element, Iter is the next element
  if (Iter) Iter->Next;

  // Basically keeps iterating until there are no changes and Cur = NULL
  while (Changed || Cur)
  {
    // Reset the Modified switch for this iteration
    Changed = false;
    while (Iter)
    {
      // If it belongs before Cur, put it there
      if (strcmp(Cur->Name,Iter->Name) > 0)
      {
        // Remove Iter from its location
        if (Iter->Next) Iter->Next->Prev = Iter->Prev;
        Iter->Prev->Next = Iter->Next;

        // Insert Iter before Cur
        Iter->Prev = Cur->Prev;
        if (Iter->Prev) Iter->Prev->Next = Iter;
        Iter->Next = Cur;
        Cur->Prev = Iter;

        // Set modified flag
        Changed = true;
      }
      // Next iteration
      Iter = Iter->Next;
    }
    if (Changed)
    {
      // Start sorting from the beginning again
      //Get to the beginning again
      while (Cur && Cur->Prev)
        Cur = Cur->Prev;
      // If an element exists, Iter is the next element
      if (Cur) Iter = Cur->Next;
    } else
    {
      // Go to the next value
      if (Cur) Cur = Cur->Next;
      if (Cur) Iter = Cur->Next;
    }
  }
  return 0;
}

I hope that has helped you grasp this wonderful topic of recursion. It really does have a lot of fun possibilities and can be quite useful. I don't think that I have particularly demonstrated to you the more useful implementations, but I will leave it for you to play with. Now is the part where I try and coax you into joining me in my next article on Member Functions. I am sure that you don't need this by now, because you are so desperately dependent on my articles that it is for your own good to read them... Look forward to addicting you more

Cheers, Chris Bennett (a.k.a. Dwarfsoft)

Discuss this article in the forums

Date this article was posted to GameDev.net: 9/30/2004
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
General