Recursion = headache;

I got to the section of our class text that discusses Recursion, and it makes no sense to me, maybe you guys can help?

Quote:

---

Recursive Processes

Many problems can be solved by having a subprogram call itsself recursively as a part of the solution. Recursion is frequently used in math. Consider for example the definition of n! (n factorial) for a nonnegative integer n. This is defined by

0! =1
1! =1

for n >1,n!=n * (n-1)!

thus, 6!=6*5!=6*5*4!=6*5*4*3!=6*5*4*3*2!=6*5*4*3*2*1

---

huh??!!

Try to follow the program execution in this function when called with the argument 3, for example.

Code:

---

int f(int n)
{
  if (n==0)
    return 1;
  return f( n-1 );
}

---

(Edit) Hehe, I mistyped the code a bit (I was thinking of a factorial function). It doesn't matter though.

Well recursion is something you are going to have to "grasp" especially if you are going to major in CS at Universities. Recursion is found in many areas in CS and in Math. Some things are easier to do with recursion others not.

Quote:

---

Originally posted by Sang-drax
Try to follow the program execution in this function when called with the argument 3, for example.

Code:

---

int f(int n)
{
  if (n==0)
    return 1;
  return f( n-1 );
}

---

---

so n becomes, at the end, 0 again or negative?

Quote:

---

Try to follow the program execution in this function when called with the argument 3, for example.


code:--------------------------------------------------------------------------------
int f(int n)
{
if (n==0)
return 1;
return f( n-1 );
}
--------------------------------------------------------------------------------

---

With recursion we have a base case (stoping case) and the recursive case( which will eventually lead to the stoping case)

here when n == 0 the function will return 1 otherwise it will recursively call the f(n-1) case until it reaches the base case.

Check out recursion on the internet.

How would you determine many digits there are in a variable of type long? One way is to use recursion.

Code:

---

#include <iostream>

using std::cin;
using std::cout;

int digitize(long);

int main()
{
  long num;
  cout << "enter an integer value greater than -1 and the program will calculate how many digits it contains." << endl;
  cin >> num;
  int result = 0;
  result += digitize(num);
  cout << "the number of digits in " << num  << " is " << result << endl;
  return 0;
}

int digitize(long Num)
{
  int Result = 0;
  if(Num == 0)
    return Result;
  else
  {
    Num /= 10;
    Result = digitize(Num);
    ++Result;
    return Result;
  }
}

---

say user enters 21 when input requested in main(). When the line:

result = digitize(num);

in main() is encountered the function digitize() is called and it is passed the value of num to evaluate.

In digitize() the value of num is stored in Num. Note that Num is not the same variable as num (it even has a different name, although it doesn't have to have). The changes to Num made in this call to digitize() will have no bearing on the value of num back in main(). In digitize() a local variable called Result is declared and initialized to zero. Since this variable is local to main() it will have no effect on any other Result except as a possible return value (as we'll see shortly). Then the value of Num is evaluated. If the value of Num is zero then Result is returned without modification. If the value of Num isn't zero then Num is divided by 10 and the new value of Num is used as the argument for a second call to digitize(). NOTE: we haven't reached the last two lines of the first call to digitize before we encounter a second call to digitize, since the current value of Num is 21.

In the second call to digitize() there is another local variable called Result declared. It has the same name and same initial value as the local variable called Result in the first call to digitize() but it has a different address and it is a completely different Result than the first one. The value of Num passed to this call of digitize() is 2. Since 2 != 0 we go to the else section where Num is again divided by 10, and the new value of Num is passed to a third call of digitize(). NOTE: again we haven't gotten to the last two lines of this call to digitize() yet before digitize() is called the third time.

In the third call to digitize() the local variables Num and Result appear again, but the Num in this call to does equate to 0. Therefore the conditional of the if() statement is true and Result; with value of 0, is returned to the second call of digitize() where is assigned to the Result which is local to the second call to digitize(). Since Result is initialized as zero in the second call to digitize() this assignment doesn't change the value of Result, but that's okay. Now we can go on the second to the last line of the second call to digitize() where the Result local to the second call to digitize() is incremented, before being returned to the first call to digitize().

The Result returned to the first call to digitize() has the value of 1. It is assigned to the Result local to the first call to digitize() which changes the value of the Result local to digitize() from zero to one. Then the value of this Result is incremented by one from one to two and Result is then sent back to main() where it is assigned to result.

Finally, the program outputs the value of result.

Recursion can be a very useful technique but it can be costly using all those local variables, etc. so if more than a few levels of recursion are required you need to make use of dynamic memory or run the risk of overloading the stack and crashing the program.

Many times you can achieve the same results without using recursion, but it's a handy tool to have around when you want it. Some people find the syntax of recursion to be easier to follow than an iterative solution, and others feel the opposite. So use it when you "have to" or when it comes in handy!

Definition of faculty:

0! = 1
n! = n * (n-1)!

So in code it would be

Code:

---

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

---

Assume n is initially 4, then the function would be have as follows:

Code:

---

: fac (4)
: 4 * fac (3)
: 4 * 3 * fac (2)
: 4 * 3 * 2 * fac (1)
: 4 * 3 * 2 * 1 * fac (0)
: 4 * 3 * 2 * 1 * 1
: 24

---

Hope it makes a little clearer.

I don't quite grasp it yet, but with all the kick ass info you guys just gave me i'm sure i will, thnx alot.

yeah, recursion isn't something most people grasp right away. you'll be fine though...

There are many problems that are really hard or impossible
to solve without recursion. For example chess search
or the edit distance problem. To really understand I think
you have to study proof by induction.
Here's an example of code to solve the edit distance problem
www.cs.wisc.edu/~condon/cs577/homeworks/ph4.ps

The algorithm works or at least appears to work because
take for example algorithm => altruistic
If the best operation is to copy then
we have cost(copy) + mincost(lgorithm=>ltruistic)
All of the operations show this structure with modification.
Thus a algorithm can be developed that solves

min ( cost(copy) + mincost(lgorithm=>ltruistic)
cost(replace) + mincost(lgorithm=>altruistic)
cost(insert) + mincost(algorithm=>ltruistic)
and so on for the rest of the operations )
The problem is a strictly recursive solution is too slow so
we save subproblems in a table.

Code:

---

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define EDIT_INFINITY 100000
#define OP_COPY      0
#define OP_REPLACE    1
#define OP_DELETE    2
#define OP_INSERT    3
#define OP_TWIDDLE    4
#define OP_KILL      5

static const int cost[] = {1, 4, 2, 3, 1, 0};
struct EditSequence
{
    int cost;
    vector<int> op;
};

#define MAX_M 100
#define MAX_N 100

EditSequence minCostTbl[MAX_M + 3][MAX_N + 3];

EditSequence minCost(string x, string y, int i, int j)
{
    int m = x.length();
    int n = y.length();
    if (i == m + 1 && j == n)
    {
        EditSequence s;
        s.cost = 0;
        return s;
    }

    if (i > m || j > n)
    {
        EditSequence s;
        s.cost = EDIT_INFINITY;
        return s;
    }
   
    EditSequence s = minCostTbl[i][j];
    if (s.cost != -1)
        return s;

    EditSequence t1 = minCost(x, y, i + 1, j + 1);
    EditSequence t2 = minCost(x, y, i + 1, j);
    EditSequence t3 = minCost(x, y, i, j + 1);
    EditSequence t4 = minCost(x, y, i + 2, j + 2);
    EditSequence t5 = minCost(x, y, m + 1, j);
    int mc = EDIT_INFINITY;
    int mo = OP_INSERT;
    EditSequence* sequence = 0;
    int c;

    if (i < m && j < n && x[i] == y[j])
    {
        c = cost[OP_COPY] + t1.cost;
        if (c < mc)
        {
            mc = c;
            mo = OP_COPY;
            sequence = &t1;
        }
    }

    c = cost[OP_REPLACE] + t1.cost;
    if (c < mc)
    {
        mc = c;
        mo = OP_REPLACE;
        sequence = &t1;
    }

    c = cost[OP_DELETE] + t2.cost;
    if (c < mc)
    {
        mc = c;
        mo = OP_DELETE;
        sequence = &t2;
    }

    c = cost[OP_INSERT] + t3.cost;
    if (c < mc)
    {
        mc = c;
        mo = OP_INSERT;
        sequence = &t3;
    }
   
    if (i + 1 < m && j + 1 < n
        && x[i + 1] == y[j] && x[i] == y[j + 1])
    {
        c = cost[OP_TWIDDLE] + t4.cost;
        if (c < mc)
        {
            mc = c;
            mo = OP_TWIDDLE;
            sequence = &t4;
        }
    }

    c = cost[OP_KILL] + t5.cost;
    if (c < mc)
    {
        mc = c;
        mo = OP_KILL;
        sequence = &t5;
    }

    sequence->cost = mc;
    sequence->op.push_back(mo);

    minCostTbl[i][j] = *sequence;

    return *sequence;
}

EditSequence minCost(string x, string y)
{
    return minCost(x, y, 0, 0);
}

void printSequence(const EditSequence& s)
{
    cout << "min cost = " << s.cost << endl;
    for (int i = s.op.size() - 1; i >= 0; --i)
    {
        switch(s.op[i]) {
        case OP_COPY:
            cout << "copy" << endl;
            break;
        case OP_REPLACE:
            cout << "replace" << endl;
            break;
        case OP_DELETE:
            cout << "delete" << endl;
            break;
        case OP_INSERT:
            cout << "insert" << endl;
            break;
        case OP_TWIDDLE:
            cout << "twiddle" << endl;
            break;
        case OP_KILL:
            cout << "kill" << endl;
            break;
        default:
            cout << "error" << endl;
            break;
        }
    }
}

int main(int argc, char *argv[])
{
    char *x, *y;
   
    if (argc != 3) {
        cout << "error: invalid number of arguments" << endl;
        return -1;
    }
   
    x = argv[1];
    y = argv[2];

    EditSequence invalidSequence;
    invalidSequence.cost = -1;
   

    for (int i = 0; i < MAX_M + 3; ++i) {
        for (int j = 0; j < MAX_N + 3; ++j) {
            minCostTbl[i][j] = invalidSequence;
        }
    }

    EditSequence s = minCost(x, y);
    printSequence(s);

    return 0;
}

---