Detail About Recursion and its Type

Discussion in 'C' started by asadullah.ansari, May 5, 2008.

  1. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    Article is originally written by Zeeshan Amjad

    Introduction



    Here I am going to give a detail about Recursion in C++. Definition: Recursion is the process where a function is called itself but stack frame will be out of limit because function call will be infinite times. So a termination condition is mandatory to a recursion.

    Many complex problem can be solved by recursion in a simple code. But it's too much costly than iterative. because in every recursion call one stack frame will formed.You all already know that about it's cost. but if problem is very complex than no way to solve except recursion.

    Background



    First recursion came into mathematics and then came into Computer science. Idea of it's use that first broke your problem into subproblems and solve it by using recursion.

    The code



    In C++, Recursion can be divided into two types:
    (a)Run- Time Recursion: Normal as in C
    (b)Compile- Time Recursion: By using Template

    Each of these can be also divided into following types:

    1. Linear Recursion
    2. Binary Recursion
    3. Tail Recursion
    4. Mutual Recursion
    5. Nested Recursion


    1. Linear Recursion: This recursion is the most commonly used. In this recursion a function call itself in a simple manner and by termination condition it terminates. This process called 'Winding' and when it returns to caller that is called 'Un-Winding'. Termination condition also known as Base condition.

    Example: Factorial calculation by linear recursion

    Run-Time Version

    Code:
     int Fact(long n)
    {
     	if(0>n)
                   return -1;
    	if(0 == n)
    	   return 1;
    	else
    {
          return ( n* Fact(n-1));
    }
    }
    Winding Process:

    Function called Function return

    Fact(6) 6*Fact(5)
    Fact(5) 5*Fact(4)
    Fact(4) 4*Fact(3)
    Fact(3) 3* Fact(2)
    Fact(2) 2* Fact(1)
    Fact(1) 1* Fact(0)
    Terminating Point
    Fact(0) 1

    Unwinding Process

    Fact(1) 1*1
    Fact(2) 2*1
    Fact(3) 3*2*1
    Fact(4) 4*3*2*1
    Fact(5) 5*4*3*2*1
    Fact(6) 6*5*4*3*2*1


    Compile-Time Version

    Code:
    // template for Base Condition
    template <>
    struct Fact<0>
    {
       enum 
      { 
          factVal = 1 
       };
    };
    
    template <int n>
    struct Fact
    {
       // Recursion call by linear method
       enum
      { 
    value = n * Fact<n - 1>::factVal
       };
    }; 
    To test it how it's working at compile time, just call
    cout << Fact<-1>::factVal ;
    And compile it then compiler error will come, because no template for -1.

    2. Binary Recursion: Binary Recursion is a process where function is called twice at a time inplace of once at a time. Mostly it's using in data structure like operations for tree as traversal, finding height, merging, etc.

    Example: Fibonacci number

    Run Time Version Code
    Code:
    int FibNum(int n)
    {
       // Base conditions
          if (n < 1)
             return -1;
          if (1 == n || 2 == n)
            return 1;
    
       // Recursive call by Binary Method
         return FibNum(n - 1) + FibNum(n - 2);   // At a time two recursive function called so               
                                                                          //   binary
    }
    Compile Time Version Code
    Code:
    // Base Conditions
    template<>
    struct FibNum<2>
    {
       enum { val = 1 };
    };
    template <>
    struct FibNum<1>
    {
       enum { val = 1 };
    };
    
    // Recursive call by Binary Method
    template <int n>
    struct FibNum
    {   
       enum { val= FibNum<n - 1>::val + FibNum<n - 2>::val };
    };
    3. Tail Recursion: In this method, recursive function is called at the last. So it's more efficient than linear recursion method. Means you can say termination point will come(100%) only you have to put that condition.

    Example: Fibonacci number

    Run Time Version Code
    Code:
    int FibNum(int n, int x, int y)
    {   
       if (1 == n)    // Base Condition
       {
          return y;
       }
       else        // Recursive call by Tail method
      {
          return FibNum(n-1, y, x+y);
       }
    }
    Compile Time Version Code

    Code:
    template <int n, int x, int y>
    struct FibNum
    {
       // Recursive call By tail method
       enum 
      { 
            val = FibNum<n-1, y, (x+y)>::val
       };
    };
    
    // Base Condition or Termination 
    template<int x, int y>
    struct FibNum<1, x, y>
    {
       enum 
      {
          val = y 
       };
    };
    4. Mutual Recursion: Functions calling each other. Let's say FunA calling FunB and FunB calling FunA recursively. This is not actually not recursive but it's doing same as recursive. So you can say Programming languages which are not supporting recursive calls, mutual recursion can be applied there to fulfill the requirement of recursion. Base condition can be applied to any into one or more than one or all functions.

    Example: To find Even Or Odd number

    Run Time Version Code
    Code:
    bool IsOddNumber(int n)
    {
       // Base or Termination Condition
       if (0 == n)
          return 0;
       else
          // Recursive call by Mutual Method
          return IsEvenNumber(n - 1);
    }
    bool IsEvenNumber(int n)
    {
       // Base or Termination Condition
       if (0 == n)
          return 1;
       else
          // Recursive call by Mutual Method
          return IsOddNumber(n - 1);
    }
    Compile Time Version Code
    Code:
    // Base Or Termination Conditions
    template <>
    struct IsOddNumber<0>
    {
       enum 
      {
         val = 0 
      };
    };
    template <>
    struct IsEvenNumber<0>
    {
       enum 
      { 
          val = 1 
      };
    };
    
    // Recursive calls by Mutual Method
    
    template <int n>
    struct IsOddNumber
    {
       enum 
      { 
             val = n == 0 ? 0 : IsEvenNumber<n - 1>::val 
       };
    };
    
    
    template <int n>
    struct IsEvenNumber
    {
       enum 
      { 
           val = n == 0 ? 1 : IsOddNumber<n - 1>::val
      };
    }; 
    5.Nested Recursion: It's very different than all recursions. All recursion can be converted to iterative (loop) except nested recursion. You can understand this recursion by example of Ackermann function.

    Example: Ackermann function

    Run Time Version Code
    Code:
    int Ackermann(int x, int y)
    {
          // Base or Termination Condition
        if (0 == x)
       {
          return y + 1;
     }   
    // Error Handling condition
       if (x < 0  ||  y < 0)
      {
          return -1;
       }  
    // Recursive call by Linear method 
       else if (x > 0 && 0 == y) 
      {
          return Ackermann(x-1, 1);
      }
       // Recursive call by Nested method
       else
      {
          return Ackermann(x-1, Ackermann(x, y-1));
      }
    }
    Compile Time Version Code
    Code:
    // Base Or Termination condition
    template <int y>
    struct Ackermann<0, y>
    {
       enum { val = y + 1 };
    };
    
       // Recursive Call by Linear Method
    template <int x>
    struct Ackermann<x, 0>
    {
       enum 
       { 
                val = Ackermann<x-1, 1>::val
       };
    };
    // Recursive Call by Nested Method
    template <int x, int y>
    struct Ackermann
    {
       Enum
       { 
             val = Ackermann<x-1, Ackermann<x, y-1> ::val>::val 
       };
    };

    References



    "Teaching recursion using recursively generated geometric design"
    by Aaron Gordon
     
  2. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    Really good article, impressive I must say.
     
  3. imrantechi

    imrantechi New Member

    Joined:
    Feb 12, 2008
    Messages:
    116
    Likes Received:
    4
    Trophy Points:
    0
    very good article
     
  4. sanjujoshhi

    sanjujoshhi New Member

    Joined:
    Apr 4, 2008
    Messages:
    13
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Design Engineer
    Location:
    India
  5. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  6. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  7. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  8. ddhire

    ddhire New Member

    Joined:
    Aug 26, 2008
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    hi i am hire
     
  9. ddhire

    ddhire New Member

    Joined:
    Aug 26, 2008
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    Thank you.
     
  10. BSTU.UOK

    BSTU.UOK New Member

    Joined:
    May 22, 2008
    Messages:
    10
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    IT undergraduate
    Location:
    Syrian Arab republic
    thx.....so good
     
  11. zamjad

    zamjad New Member

    Joined:
    Oct 7, 2008
    Messages:
    15
    Likes Received:
    1
    Trophy Points:
    0
  12. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Agreed Zeeshan but Article of the month is already owned by him and he has all the prices. Also We see that topic is same but the content is not totally copied.

    Also the same is posted by him on many forums like

    http://www.cplusplus.com/forum/articles/2935/
    http://www.dreamincode.net/forums/showtopic51296.htm
    http://www.daniweb.com/forums/thread122912.html

    Which should have been avoided for becoming the winner.

    As the topic belongs to you if you would like the notice to be added please do let us know.
     
  13. zamjad

    zamjad New Member

    Joined:
    Oct 7, 2008
    Messages:
    15
    Likes Received:
    1
    Trophy Points:
    0
    If you think it is then anyone can write more than donzens article daily.

    This shows the credibility of these sites itself.

    This decision is for your site credibility and for future authors who decided to write for you or avoid your site.

    After few mins google i came across one more article

    http://www.dreamincode.net/forums/showtopic45816.htm

    In addition to the above article, I recommend you to please take a look at this one too

    http://www.codeproject.com/KB/atl/atl_underthehood_.aspx

    Regards
     
  14. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    We are constantly working on the copy paste problems of article rewriting and we have removed many such articles - Duplicate Articles Problem but yes we should have done more research on this to be fair.

    Agreed and we are definitely working on this. Even the Article competition is now made longer as well as couple of votes to avoid such things.

    Also regarding your other links suggestion and now we have revoked the Author Level of the writer as well as would make changes in the Article of the month Rules and guidelines as well as adding the copyright notice to the article.

    Thanks for your inputs
     
  15. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Also I wanted to add we are using copyscape service to detect the duplicate whenever any article is approved and what we saw is the Author posted the same article later after the approval on the other forums and so from now on we may need to be doing this very often.
     
  16. debleena_doll2002

    debleena_doll2002 New Member

    Joined:
    Feb 5, 2008
    Messages:
    119
    Likes Received:
    0
    Trophy Points:
    0
    I had also seen this same topic in other sites by other author but content is not the same. Copyright rule is that content should not be copied.

    What do you think ? There are many articles on the same topic but contents are different...First thing article topic is not a Research Topic Okay.....

    If you are talking about this topic "Recursion" there are thousands articles but contents are different...Topic does not matter for articles.

    I will take an example UNIX kernal is there...But LINUX group is saying we are totally different than Unix but they also modified some unix code and launch new operating system" Linux"...Same example as solaris is also flavour of Unix.
     
  17. zamjad

    zamjad New Member

    Joined:
    Oct 7, 2008
    Messages:
    15
    Likes Received:
    1
    Trophy Points:
    0
    Thanks dableena for your post. Now let me clear few things that you might mix up. First of all take a look at all of my post when did I actually claim about copy right?

    Any computer person can easily identify that this article is not exactly copied but the main idea, theme, and even all the examples except “Tail recursion” are same. You can’t say it is copied, but it is heavily based on mentioned articles without even mentioning it.

    I just wanted to say one thing,

    Give credit where it is due
     
  18. debleena_doll2002

    debleena_doll2002 New Member

    Joined:
    Feb 5, 2008
    Messages:
    119
    Likes Received:
    0
    Trophy Points:
    0
    But here we are not goin for PHD. 10000 articles can be on the same topics i have already mentioned.
    Yes you are right!!! It may be not to win as winner of this month for this article. This total depend on system how r u implementing. But you cannt mention as " originally written zeesan in asadullah.ansari article." This is his wish that he mention or not .He knows better. You have to take permission of author then you can modify his article.
    You know just go read BOOK as mention by him
    "Teaching recursion using recursively generated geometric design"
    by Aaron Gordon

    same explanation by this book also. Can you blame to those writers also who mention this book as in his articles.
     
  19. zamjad

    zamjad New Member

    Joined:
    Oct 7, 2008
    Messages:
    15
    Likes Received:
    1
    Trophy Points:
    0
    I am sorry debleena, but I still couldn’t understand what you wanted to say, please explain it to me. What my intention was I already mentioned in my previous mail.I am still confuse what do you want to say in this statement

    What total are you talking about this? And what is depends on system? Do you want to say that recursion depends on system?

    Can you please explain when did I mention this thing? What should be written or not written with this article, I have already left that decision to the moderator. And you may also understand that I am not a moderator to change others post.

    For your kind information this is not a book, this is in fact an article published in “Journal of Computing Science in Colleges” in October 2006. Did you actually get a chance to see this article (or so called book) yourself? If you are a member of ACM then you can access it form ACM Digital Library. And for your kind information I have actually read that article. This 7 page articles has nothing to do with recursion type it only deals with “Recursively-Generated Geometric Designs” and discussed "Nested Triangles, Nested Polygons and Fractals" I can’t post the whole article here, but for your reference let me copy its abstract here

    You can read this abstract yourself from here

    http://portal.acm.org/citation.cfm?id=1181811.1181830

    Even more interesting is that this reference is also copied from this article.

    http://www.codeproject.com/KB/cpp/Recursion_Prmr_CPP_01.aspx

    This reference was mentions properly in the above article by explaining what reader should expect in it, not adding the reference just for the sake of something in the reference section. Here is the excerpt from the above article that refers to this.

    Here number 3 is the reference of “Teaching recursion using recursively generated geometric design, Aaron Gordon”

    If you have time then I recommend you to take a look at its second part before someone write an article based on it without even giving the credit where it is due, from here

    http://www.codeproject.com/KB/cpp/Recursion_Prmr_CPP_02.aspx

    Can you please explain a little bit what you want to ask or say to me?
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice