Thread: When to use recursion ?

  1. #1
    Unregistered
    Guest

    When to use recursion ?

    Hi,

    According to my book it says that interation (loops), in many cases, can be use instead of recursion. But in some cases, recursion mimics the problem better. My question is simply when is a good time to use recursion and if possible provide an example.

    note: I am more comfortable when using loops....


    many thnx

  2. #2
    Unregistered
    Guest
    Recursion is best used when a recursive solution makes the code simpler and easier to follow.

    Iteration is best used when a recursive solution doesn't make the program much simpler or when a recursive solution is devastatingly inefficient.

    A good example of recursion is a binary search for a binary tree.
    It's efficient enough for the purposes and vastly improves the readability of the program.

    A terrible example of recursion is the fibonacci program.
    It follows the mathomatical algorithm better than the iterative solution, but it doesn't make the code much easier to follow or shorter and it's so inefficient you don't want to imagine.

  3. #3
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    A lot of mathematical functions are recursive relations. The Fibonacci numbers, the Mandelbrot-set, the factorial function etc.

    It is often very easy to implement these relations as recursive functions in a programming language.

    A very much used example, the factorial function:

    n! = n x (n - 1) x (n - 2) x ... x 2 x 1

    int fac (int n)
    {
    if (n == 1)
    return 1;
    else
    return (n * fac (n - 1));
    }

    But there are many more applications of recursion.

    Recursion is mainly used in algorithm design phase, where you concentrate on designing an algorithm to solve certain problem and you don't want to worry about optimizations. When the algorithm design has finished, you can optimize it and also take the language you will be using in account.

    In almost all cases, if not all cases, recursion can be removed. There are many techniques for removing recursion. They were developed since not all languages do support recursion.

  4. #4
    The Artful Lurker Deckard's Avatar
    Join Date
    Jan 2002
    Posts
    633
    There are some costs associated with using recursion. The recursive function is copied onto the stack each time it calls itself. This takes time and memory not required in solutions using iteration.

    The previous posters hit the mark when they advised you to only use recursion when it makes the code easier to follow. Most likely, you will use recursion when forced to by your instructor or university professor.
    Jason Deckard

  5. #5
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    My experience has been that recursion is mostly used in searching and sorting problems where a divide-and-conquer method is used. Divide-and-conquer refers to solving a problem with a large data set by reducing it to two smaller data sets, and solving for each of those.

    Sometimes recusrion just makes more sense. For example, the towers of Hanoi (http://www.cut-the-knot.com/recurrence/hanoi.html)....
    Code:
    void hanoi (int src, int aux, int dest, int num)
    {
     if (num != 0)
     {
      // Move the pegs above to the auxillary peg...
      hanoi (src, dest, aux, num - 1);
      
      // Move the current peg to the destination peg...
      printf ("Peg moved from %d to %d.\n", src, dest);
    
      // Move the pegs from the auxillary peg to dest
      hanoi (aux, src, dest, num - 1);
     }
     return;
    }
    Other problems too, like say, try to find how many paths there are from the bottom left cell of a square to the top right cell of the square. These are problems where a stack needs to be used, and it's often more convenient to use the function's stack than try to make your own.

    If you're interested, you might want to check out a book on fractals. Those pretty much are recursive by definition.
    Last edited by QuestionC; 01-06-2002 at 01:09 PM.
    Callou collei we'll code the way
    Of prime numbers and pings!

  6. #6
    Unregistered
    Guest
    thnx

    other than maths functions which i'm not good at and algorithms, is there a live example which can also be solved by recursion?

    thnx for all replies so far.

  7. #7
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    531

    I had the same problem.

    I have an idea. When almost in every iteration you have more

    if (To do like you have done && have value of variables will be needed again)
    go for recursion call;

    It is more important for thinking style for successfull implementation of divide and conquer type of problem.

    Best way is to see some problem which were solved recursive way.
    [ Never code before desk work ]
    -------------------------------------:-->
    A man who fears Nothing is the man who Loves Nothing
    If you Love Nothing, what joy is there in your life.
    =------------------------------------------------------= - I may be wrong.

  8. #8
    Unregistered
    Guest
    thnx

    Did you see the other thread called 'Towers of Hanoi' ?
    If anyone knows the recursive solution OR iterative solution to the problem pls post it, i don't know how to solve that even with pseudocode code.

    thnx a lot

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. convert Recursion to linear can it be done
    By umen242 in forum C++ Programming
    Replies: 2
    Last Post: 10-15-2008, 02:58 AM
  3. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  4. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  5. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM