Thread: 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.

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.

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!

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

?????

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.

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!

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