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 simply when a function can call itself.

Code:

int Factorial(int x)
     {
     return  (x>1) ? (x * Factorial(x-1)) : 1;
     }

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

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

?????

yup

Code:

#include <iostream>
using std::cout;

void recursion();

int main()
{
  recursion();
  return 0;
}

void recursion()
{
  cout << "Recursion\n";
  recursion();
}

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

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

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.

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).

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