Thread: how to use recusrion

  1. #1
    Registered User
    Join Date
    Jul 2009
    Posts
    1

    how to use recusrion

    hi there

    i was wondering " how to write recursive functions ?"... Is there a general pattern or way to write such function or do we just think and find a way.

    I know to how to write simple recursive function but when the question get tough i know we can reduce the complexity using recursion but dont know how to write one

  2. #2
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    well the general pattern is like
    Code:
    int func(...)
      int result;
      do_stuff_first;
      if(end_condition)
        result=default_value;
      else
        result=func(...);
      do_stuff_last;
      return result;
    }
    But that is of limited usefulness.

    If you can't easily see a way to write a function recursively, then don't. Recursion is slower then looping, and vulnerable to stack overflow. It can be more clear to read if the problem naturally lends itself to recursion, but if it doesn't they you will only be adding complexity.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I think recursion is the first approach you should take when you find a problem that can be solved easily using it. Then once you get it working and understand it fully you can figure out the iterative approach which is usually going to be faster albeit more complex.

    The recursive solution is usually the least complex but also the least efficient.

  4. #4
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    i was wondering " how to write recursive functions ?"... Is there a general pattern or way to write such function or do we just think and find a way.
    Recursion is definitely a tricky topic, and requires you to believe i your code more than anything else. For a program to be recursive, it must have the following properties -

    1) A base case which ends the recursion.
    2) A recursive decomposition which breaks the problem down into sub-problems of the same form.

    In general, the pattern for recursive problems is -

    Code:
    if (test for simple case) {
    Compute a simple solution without using recursion.
    } else {
    Break the problem down into subproblems of the same form.
    Solve each of the subproblems by calling this function recursively.
    Reassemble the solutions to the subproblems into a solution for the whole.
    }
    Here is an example with the common factorial function -

    which is defined as -
    n! = n * !(n - 1) where n > 0

    Code:
    int Factiorial(int n)
    {
         if(n == 0)
             return 1;
        else
             return n * Factiorial(n - 1);
    }

  5. #5
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    To the OP, note that recursion may sometimes hide its lack of ability to actually solve a problem. Not sure how to put it in words, but it may disguise itself as a solution that is in fact... not.

    The factorial example that we keep seeing everywhere to exemplify recursion is just a case of a bad use for recursion. The solution has one major bug: It may result in integer overflow. Since the factorial of such a simple number as 13, overflows the function return type capacity. One could be tempted to increase the possible number of calculations...

    Code:
    double Factorial(int n);
    But then we just introduced another bug. Meanwhile,

    Code:
    double Factorial(double n);
    Doesn't do anything for us either. We are back at the original bug. Finally we may be tempted to fix the bug...

    Code:
    int Factorial (int n) {
    
        if (n > 12) return ???;
    
        // ... rest of code
     
    }
    Because this is a recursive function that check is being done every time the function is entered adding even more to the performance penalty usually involved with recursive functions.

    It's no wonder then, recursive functions are rarely seen outside well known use cases.
    Last edited by Mario F.; 07-18-2009 at 08:03 PM.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Sometimes recursion just makes things immensely simpler. If you write some code to parse a file, and then you add #include support to the parser, it's probably very easy to just recursively call the parsing function to deal with the new file that has been #include'd.

    That's a rather limited use of recursion, though -- anything more complicated and you need base cases, and you need to make sure that complex cases are really broken up into simpler cases, or you'll have infinite recursion on your hands. I think Spidey's post explains it rather well.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Tags for this Thread