A practical recursive function, finally!

This is a discussion on A practical recursive function, finally! within the C Programming forums, part of the General Programming Boards category; Many years ago, in my very first programming class in college, I was introduced to the concept of recursion. I ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Location
    Maryland, USA
    Posts
    46

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

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    For a number of years after that I was on the lookout for a practical application of recursion.
    They are everywhere and very useful!
    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.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    Quote Originally Posted by KenJackson View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Nov 2009
    Location
    Maryland, USA
    Posts
    46
    Quote Originally Posted by iMalc View Post
    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.

    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.

    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.

  5. #5
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    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.

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,669
    Quote Originally Posted by KenJackson View Post
    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.

  7. #7
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    ^^ especially if you are going to check for every recusrion the same thing

  8. #8
    Registered User
    Join Date
    Nov 2009
    Location
    Maryland, USA
    Posts
    46
    Quote Originally Posted by Sebastiani View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. error handling in recursive function.
    By broli86 in forum C Programming
    Replies: 4
    Last Post: 06-23-2008, 02:11 PM
  2. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  3. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 01:28 PM
  4. recursive function
    By tonderai76 in forum C++ Programming
    Replies: 11
    Last Post: 04-21-2004, 12:49 PM
  5. Recursive Ackermann's function - need help
    By Unregistered in forum C++ Programming
    Replies: 6
    Last Post: 03-04-2002, 03:42 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21