A practical recursive function, finally!

Many years ago, in my very first programming class in college, I was introduced to the concept of recursion. I loved it! I wanted to use it. For a number of years after that I was on the lookout for a practical application of recursion. But I eventually gave up.

Every recursive function that I wrote and every one that I ran across could be done better with a simple loop. Until now.

This function matches a pattern with an arbitrary number of * and ? wildcard characters against a filename (without wildcards) and returns true or false.

I'm sure it could be written more efficiently without recursion, but I can't see a way to keep it simple without recursion. (In this application, speed is less important than simplicity.)

I'm pleased. I hope you are too.

Code:

int Match(const char *pattern, const char *filename) { if (NULL == pattern || NULL == filename) { return false; } // Match characters and '?' up to the first '*' while (0 != *pattern && 0 != *filename && '*' != *pattern && (toupper(*pattern) == toupper(*filename) || '?' == *pattern)) { pattern++; filename++; } int match = (0 == *pattern && 0 == *filename); // Use iterative recursion to match everything beyond the first '*' if ('*' == *pattern++) { do { match = Match(pattern, filename); } while (!match && 0 != *filename++); } return match; }

Quote:

For a number of years after that I was on the lookout for a practical application of recursion.

They are everywhere and very useful!

Quote:

Every recursive function that I wrote and every one that I ran across could be done better with a simple loop. Until now.

Im pretty sure that every recursive function can be written as an iterative one (i.e. looping), and vice-versa. I havent looked at your code, but Im pretty sure whatever you write can be converted to iterative from recursive, and vice versa. (I say this because I think it was proved in one of my compiler/languages courses).

With all that said, both recursive and iterative functions/implementations have their pros and cons. Some problems are naturally solved by recursion so may be easier to implement. However, recursion has the overhead of calling functions, whereas iterative functions do not. And of course there are many more pros/cons for each.

Quote:

Originally Posted by KenJackson

Many years ago, in my very first programming class in college, I was introduced to the concept of recursion. I loved it! I wanted to use it. For a number of years after that I was on the lookout for a practical application of recursion. But I eventually gave up.

Every recursive function that I wrote and every one that I ran across could be done better with a simple loop. Until now.

This function matches a pattern with an arbitrary number of * and ? wildcard characters against a filename (without wildcards) and returns true or false.

I'm sure it could be written more efficiently without recursion, but I can't see a way to keep it simple without recursion. (In this application, speed is less important than simplicity.)

I'm pleased. I hope you are too.

I'm more taken by surprise than anything else. I'm not sure how you could code for a year or two and not run into recursion several times. In some ways it's a good thing though because many people tend to write things like a binary search using recursion which just needlessly uses up stack space, when a loop would make much more sense using O(1) stack space.

However, the only kinds of recursive functions that are best written as iterative are those that are just tail-recursive. That leaves a huge number of algorithms that are best implemented recursively or at least partly recursively IMHO. If you ever have to go as far as maintaining your own explicit stack structure just to avoid the recursion then you're going totally overboard.

Something as simple as QuickSort is best written recursively (or at least partly recursively) because it logically has two recursive calls.

You've never written any kind of tree data structure I presume?
Here's how I always write a basic in-order tree-traversal algorithm:

Code:

void inOrderPrint(const T *n) { while (n != NULL) // <- iteration { inOrderPrint(n->left); // <- recursion cout << n->value; n = n->right; } }

That's what I mean by partially recursive.

Quote:

Originally Posted by iMalc

I'm more taken by surprise than anything else. I'm not sure how you could code for a year or two and not run into recursion several times.

I didn't say I hadn't run into it. I was just never impressed that it was the best way to code it.

Quote:

Something as simple as QuickSort is best written recursively (or at least partly recursively) because it logically has two recursive calls.

I think I've used qsort() from stdlib.h a couple times. It worked well enough on those occasions.

Quote:

You've never written any kind of tree data structure I presume?

You presume correctly. That would fall either in the category of large data handling or of unnecessarily complex for small data.

Most of my work is embedded that's heavy on I/O and state machines, but where you rarely have enough data to bother sorting--just iterate over it.

Quote:

You've never written any kind of tree data structure I presume?

Most people rarely write data structures and the tools to manipulate them, they use those tools written prior by others.

I've worked the industry for over a decade now, and rarely encountered the need to write a data structure (let alone a tree) implementation from scratch.
Almost always it's far more convenient (and productive) to use an existing library (in those cases where the core language/libraries doesn't have an appropriate one built in).

Maybe it's different for people working in some parts of the IT landscape, but that's how things work for the majority of us who write business applications.

Quote:

Originally Posted by KenJackson

Many years ago, in my very first programming class in college, I was introduced to the concept of recursion. I loved it! I wanted to use it. For a number of years after that I was on the lookout for a practical application of recursion. But I eventually gave up.

Every recursive function that I wrote and every one that I ran across could be done better with a simple loop. Until now.

This function matches a pattern with an arbitrary number of * and ? wildcard characters against a filename (without wildcards) and returns true or false.

I'm sure it could be written more efficiently without recursion, but I can't see a way to keep it simple without recursion. (In this application, speed is less important than simplicity.)

I'm pleased. I hope you are too.

Code:

int Match(const char *pattern, const char *filename) { if (NULL == pattern || NULL == filename) { return false; } // Match characters and '?' up to the first '*' while (0 != *pattern && 0 != *filename && '*' != *pattern && (toupper(*pattern) == toupper(*filename) || '?' == *pattern)) { pattern++; filename++; } int match = (0 == *pattern && 0 == *filename); // Use iterative recursion to match everything beyond the first '*' if ('*' == *pattern++) { do { match = Match(pattern, filename); } while (!match && 0 != *filename++); } return match; }

Seems to work well, too. But just keep in mind: (1) 'false' is not a valid keyword in C, and (2) it's probably unecessary to check for NULL arguments - if they are then they shouldn't have even made it that far in the first place - just let the program die ungracefully.

^^ especially if you are going to check for every recusrion the same thing

Quote:

Originally Posted by Sebastiani

But just keep in mind: (1) 'false' is not a valid keyword in C

Oops.

I actually wrote it in C++, just because of the application it's going into, and converted it to C. But I missed that one.