Thread: Recursion = headache;

  1. #1
    Redundantly Redundant RoD's Avatar
    Join Date
    Sep 2002
    Location
    Missouri
    Posts
    6,331

    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?

    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??!!

  2. #2
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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.
    Last edited by Sang-drax; 12-20-2002 at 04:06 PM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  3. #3
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511

    Talking

    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.
    Mr. C: Author and Instructor

  4. #4
    Redundantly Redundant RoD's Avatar
    Join Date
    Sep 2002
    Location
    Missouri
    Posts
    6,331
    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?

  5. #5
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511

    Wink

    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.
    Mr. C: Author and Instructor

  6. #6
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    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!

  7. #7
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    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.

  8. #8
    Redundantly Redundant RoD's Avatar
    Join Date
    Sep 2002
    Location
    Missouri
    Posts
    6,331
    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.

  9. #9
    Registered User
    Join Date
    Nov 2002
    Posts
    1,109
    yeah, recursion isn't something most people grasp right away. you'll be fine though...

  10. #10
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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;
    }

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, 09:45 PM
  2. Recursion
    By Lionmane in forum C Programming
    Replies: 11
    Last Post: 06-04-2005, 12:00 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. stack and recursion help needed!
    By LouB in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 02:19 PM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM