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)
Author: Chris Bennett aka Dwarfsoft
Contact: dwarfsoft@hotmail.com
April 11, 2001
(C) Copyright Chris Bennett , 2001