help on recursion.

This is a discussion on help on recursion. within the C++ Programming forums, part of the General Programming Boards category; This is not for a class assingment or anything. I am just curious as to what recursion iss and how ...

  1. #1
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901

    Lightbulb help on recursion.

    This is not for a class assingment or anything. I am just curious as to what recursion iss and how it is utiliesed. Keep in mind that I am not far in the more advanced techniques like arrays and I still am having a tough time with pointers. I know classes, functions, loops, and things like that. Can you give me an explination and maybe an example on what basic recursion is and I can go from there. Thankx, and did I mentino this is not a homework question.

  2. #2
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    recursion is simply when a function can call itself.

    Code:
    int Factorial(int x)
         {
         return  (x>1) ? (x * Factorial(x-1)) : 1;
         }
    Last edited by FillYourBrain; 10-24-2002 at 11:51 AM.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  3. #3
    btq
    btq is offline
    julie lexx... btq's Avatar
    Join Date
    Jun 2002
    Posts
    161
    recursion is for instance when you make a call to the same
    function you're in,
    something like:
    Code:
    void recur(int a)
    {
         ...
         a*=2;
         recur(a);
         ...
    }
    this example is just an example and I can see no functionality
    whatsoever but you get the idea..
    now offcourse you'll need some conditions or this will go on for
    ever. An example of a algo using recursion is
    mergesort. Can't come up with anything else right now..
    so to finish things off: was this a homework assignment?

    ::so beaten !! ::

    /btq
    Last edited by btq; 10-24-2002 at 10:53 AM.
    ...viewlexx - julie lexx

  4. #4
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    Posts
    812
    Recursion is where a function repeats by calling itself.

    I.e.

    Code:
    int doSomething(int data, int cnt)
    {
      // Partially process data
      data = .. ..;
      cnt--;
    
      if(cnt == 0)
        return data;
      else
        return doSomething(data, cnt);
    }
    See that doSomething calls itself.

    This can really simplify some tasks, especially things like tree searches, where the function calls itself at each branch.

    However, recursion should be used with care, a recursive function should ensure that recursion ends & doesn't attempt to repeat for ever (notice the if cnt == 0 check above). Each time a function recurses, data is added to the stack. If too many recursion occur, the stack will eventually overflow.

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Does anyone actually use recursion anymore? While it can be more readable (although LOTS of times, not!) there almost always seems to be an easier algorithm that is not only faster, but also takes up less memory. A classic example is the Fibonacci sequence that is always seen sighted using recursion, try finding out the 40th Fibo number using recursion and you'll wait all day, while a simple for loop or dynamic programming will give it to ya in a split second!

  6. #6
    Registered User The Dog's Avatar
    Join Date
    May 2002
    Location
    Cape Town
    Posts
    788
    Originally posted by FillYourBrain
    recursion is simply when a function can call itself.

    Code:
    int Factorial(int x)
         {
         return  (x<1) ? (x * Factorial(x-1)) : 1;
         }
    Shouldn't that have been :
    Code:
    int Factorial(int x)
    {
         return  (x>1) ? (x * Factorial(x-1)) : 1;
    }
    ?????

  7. #7
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    yup
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  8. #8
    Registered User
    Join Date
    Jan 2002
    Posts
    559
    Code:
    #include <iostream>
    using std::cout;
    
    void recursion();
    
    int main()
    {
      recursion();
      return 0;
    }
    
    void recursion()
    {
      cout << "Recursion\n";
      recursion();
    }
    Truth is a malleable commodity - Dick Cheney

  9. #9
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Code:
    function gdc(m,n) = m           if m == n
    function gdc(m,n) = gdc(m-n,n)  if m > n
    function gdc(m,n) = gdc(n-m,m)  if m < n
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  10. #10
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    Posts
    812
    >Does anyone actually use recursion anymore?

    Have you heard of the K-approximation algorithm. This finds the minimum character differences between two strings. Show me an easy algorithm to do this without using recursion.

    How about a find file function, which returns true if a filename exists somewhere on the harddrive? Show me any easy way to implement this without recursion.

    However, I don't think recursion should be used needlessly.
    OS: Windows XP
    Compilers: MinGW (Code::Blocks), BCB 5

    BigAngryDog.com

  11. #11
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Davros, since I'm still relatively new to programming and haven't yet run across either of those algorithms, I'll take your word for it! The K-approximation I'd need more details on, but with the file finder I can't think of a better way to sort through all the subfolders than recursion so ya got me! Is recursion also the only way to solve a maze? Seems like these two would be similar, ie go as far as possible down one path, then backtrack to the last fork in the road.

  12. #12
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    you never NEED recursion but any replacement does simulate recursion (although faster and no danger of killing the callstack).

    You can do your maze with a stack, pushing each decision onto the stack in a loop (simulated recursion).
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  13. #13
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Ack, my brain is hurting trying to figure out how to write something like that. Heres my attempt using pseudocode, let me know if I'm right!
    Code:
    struct position {int x_pos, int y_pos, int numChoices}
    stack maze
    
    add beginning position to the stack
    
    while (stack is not empty or reach the end of maze)
    {
       for (loop through all possible choice decisions at the position which is on top of stack)
       {
           add new position to stack in direction of choice
           continue with next while iteration
       }
        pop the end of the stack
    }
    I think this would work, although maybe not the optimal way to use the stack. It seems like this would be the better way to do that file search as well, recursion busted again! Davros, could you give more details on the K-approximation problem? Like to see if we can figure out a better way to do that as well. Death to recursion!

  14. #14
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    Posts
    812
    >you never NEED recursion

    I would agree. My only point is that recursion can vastly simplify some algorithms.

    >The K-approximation I'd need more details on...

    A K-approximation returns the minimum character differences between two strings. For example, how many character differences between the two following strings:

    s1 : 'Hello World'
    s2 : 'Hallo World'

    Answer 1. Easy. Now how many character differences between:

    s1 : 'Hello World'
    s2 : Hllo World'

    Answer 1: Missing character in s2. How many differences now:

    s1: 'Hello World'
    s2: 'Hxallo World'

    Answer 2: Extra character in s2 + 1 incorrect character.

    I would love to see a relatively straight forward way of doing this without recursion. For the record, here's my algorithm which uses AnsiString. AnsiString is references from index 1, not zero like c strings. For most intents, AnsiString is equivelent to STL string class.

    Code:
    int LinguaLex::kRecurse(const AnsiString& s1, const AnsiString& s2, int k, int maxK)
    {
      // K-Approximation string comparison (case sensitive)
      if (s1 == s2) return 0;
      if (k >= maxK && maxK > -1) return maxK;
    
      int lmax;
      int lmin;
      int len1 = s1.Length();
      int len2 = s2.Length();
      if (len1 > len2)
      {
        lmax = len1;
        lmin = len2;
      }
      else
      {
        lmax = len2;
        lmin = len1;
      }
       for(int n = 1; n <= lmin; n++)
      {
        if (s1[n] != s2[n])
        {
          // Recursive call to find min difference
          AnsiString sub1(s1.SubString(n+1, len1 - n));
          AnsiString sub2(s2.SubString(n+1, len2 - n));
    
          if (lmax < maxK || maxK == -1) maxK = lmax;
          int xc = kRecurse(sub1, sub2, k+1, maxK);
          int mc = kRecurse(s1.SubString(n, len1 - n + 1), sub2, k+1, xc + 1);
    
          int ac;
          if (xc < mc)
            ac = kRecurse(sub1, s2.SubString(n, len2 - n + 1), k+1, xc + 1);
          else
            ac = kRecurse(sub1, s2.SubString(n, len2 - n + 1), k+1, mc + 1);
    
          if (xc <= mc && xc <= ac)
            return xc + 1;
          else
          if (mc <= xc && mc <= ac)
            return mc + 1;
          else
          if (ac <= xc && ac <= mc)
            return ac + 1;
         }
     }
    
      return lmax - lmin;
    }

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, 08: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, 09: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, 08:24 AM

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