trouble with recursion

This is a discussion on trouble with recursion within the C++ Programming forums, part of the General Programming Boards category; Hey everyone! I'm having some serious problems mentally grasping recursion...and what this prog does (prints out a ruler basically), just ...

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    153

    trouble with recursion

    Hey everyone!
    I'm having some serious problems mentally grasping recursion...and what this prog does (prints out a ruler basically), just doesn't seem to make sense to me how it goes about doing what it does...if anyone could go over this code, and maybe help me to understand recursion...that would be amazing! Thanks guys, YET again. -Chap

    Code:
    #include <iostream>
    using namespace std;
    const int Len = 66;
    const int Divs = 6;
    void subdivide(char ar[], int low, int high, int level);
    int main()
    {
        char ruler[Len];
        int i;
        for (i = 1; i < Len - 2; i++)
            ruler[i] = ' ';
        ruler[Len - 1] = '\0';
        int max = Len - 2;
        int min = 0;
        ruler[min] = ruler[max] = '|';
        cout << ruler << "\n";
        for (i = 1; i <= Divs; i++)
        {
            subdivide(ruler, min, max, i);
            cout << ruler << "\n";
            for (int j = 1; j < Len - 2; j++)
                ruler[j] = ' ';     //reset to blank ruler
        }
        cin.get();
        return 0;
    }
    
    void subdivide(char ar[], int low, int high, int level)
    {
        if (level == 0)
            return;
        int mid = (high + low) / 2;
        ar[mid] = '|';
        subdivide(ar, low, mid, level - 1);
        subdivide(ar, mid, high, level - 1);
    }

  2. #2
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    >>char ruler[Len];
    Are you sure that's legal?...

    Ok, anyway, what your program does is:
    main() - prints each stage of the ruler's drawing on a new line (that's what the loop's for).
    [edit]I mean, it draws a new ruler with more subdivisions in it, each time it loops.[/edit]

    subdivide():
    It finds the position in the ruler that is directly between low and high (hence mid), then draws a | at that position. Then it calls itself, except it passes low as low and mid as high - therefore it ends up drawing in between low and mid, etc.. Once all the drawing to the left of the tick has finished (it 'knows' because level becomes zero, since every time it calls itself it passes level - 1), it goes and does everything to the right of the tick.

    It's a little hard to explain it perfectly, but you just have to trace the program in your mind and try to see the pattern that the recursion makes.
    Last edited by Hunter2; 09-30-2004 at 06:09 PM.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  3. #3
    Registered User Kybo_Ren's Avatar
    Join Date
    Sep 2004
    Posts
    136
    As Hunter says:
    Code:
    char ruler[Len];
    is only valid in C99.

  4. #4
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    Since Len is a const int, it should be fine, right?

  5. #5
    Registered User Kybo_Ren's Avatar
    Join Date
    Sep 2004
    Posts
    136
    Oh, didn't see the const

  6. #6
    Registered User
    Join Date
    Sep 2004
    Posts
    153
    I'm not asking if the code is fine or not...I compiled it and it's just fine...I'm curious what exactly it does...I'm not understanding how it makes the lines the way it does...or even just a general overview of recursion would help...anything at all would be great...thanks again-Chap

  7. #7
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    >>or even just a general overview of recursion would help...anything at all would be great...
    What a waste of my valuable sugar molecules that went toward typing that explanation up.

    Ok. Recursion: To understand recursion, you must first understand recursion. Got it? Ok. Your function calls itself, altering the parameters each time, in such a way that eventually the parameter called 'level' will become 0, and therefore it will stop calling itself and die. From birth to death, it (a) draws a line in between the low and high parameters passed to it, and (b) spawns two identical progeny, and splits its belongings evenly between them. (c) Eventually, the inheritance passed down from generation to generation to its distant grandchildren is too little for them to live on, and they die off, and with them the family line dies and they are spoken of no more; and so the rest of your program goes on.

    Got it?
    Last edited by Hunter2; 09-30-2004 at 07:08 PM.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  8. #8
    Registered User
    Join Date
    Sep 2004
    Posts
    153

    much needed help

    hunter2...thanks for your patience and your help...you're the *beep* and I greatly appreciatethe help...thanks! -Chap

  9. #9
    i dont know Vicious's Avatar
    Join Date
    May 2002
    Posts
    1,200
    The best definition of recursion is in someones signature here. (Cant remember who's)

    It is as follows:

    Definition of Recursion:
    Recursion /ree-ker'-zhon/: See Recursion.

    [edit]
    its jverkoeys sig.
    What is C++?

  10. #10
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    I believe the text book definition is a function that calls another instance of itself to brake down a larger problem into a smaller similar problem called a base case. Recursion is basically the ability of a function to call itself.
    easy example
    Code:
    int Factorial(int n){
    if (n==0)
      return 1;
    else
      return n * Factorial(n-1);
    }
    I didn't test this, but I believe it works.
    beware this is an easy way to eat up memmory resources.
    recursion works similar to a stack when it comes to consumption of system resources.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  11. #11
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    i'm using the example above, although i thought it was to find the prime factors of a given number it seems not to be...anyhow this is how it works (kind of).....

    each time factorial is called it creates a whole new function called factorial.....
    the first call to factorial (say from main) cannot complete until the second call (from inside factorial itself) is complete (has something resolvable, like a number constant ex; 1).....but the second call can't complete until the third completes..and so on and so on...the function completes when n == 0...the function eventually returns the number constant 1.
    now the line
    return n * Factorial(n - 1);
    can be thought of as
    return n * 1

    now, in the instance of the function that called factorial ^^^
    return n * Factorial(n -1);
    now can be thought of as
    return n * n * 1

    the can can be thought of as
    return n * n * n * 1

    Code:
    int Factorial(int n){                        //say n = 60
    if (n==0)                                        //n has not been broken down to 0
        return 1;                                   //any number times 1 is is the same number
    else
        return n * Factorial(n-1);         //returns 60 times the return of factorial(59) 
    }
    int Factorial(int n){                          //n = 59
    if (n==0)                                          // is not 0
      return 1;                               
    else
      return n * Factorial(n-1);               //return 59 * Factorial(58);
    }
    int Factorial(int n){                           //n = 57
    if (n==0)
      return 1;
    else
      return n * Factorial(n-1);               //returns 57 times factorial(56)
    }
    
    .................... until n == 0 more times
    if you hard coded this function for n = 3, it would look like
    Code:
    factorial(n = 3)
    {
    return 3 * 2 * 1
    }
    
    factorial(n = 7)
    {
    return 7 * 6 * 5 * 4 * 3 * 2 * 1
    }
    comprende?
    Last edited by misplaced; 10-01-2004 at 12:42 AM.

  12. #12
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    It is for finding a factoral
    n!=nX(n-1)X...X1
    The example I posted and more are in a book I have.
    I would recomend it if you want to read further on the issue.
    It has a very detailed chapter on recursion.

    C++ Program Design
    An Introduction to Programming and Object-Oriented Design
    2nd Edition
    James P. Cohoon/Jack W. Davidson

    Here is a good website on recursion I googled.
    http://personal.vsnl.com/erwin/recursion.htm
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  13. #13
    Registered User
    Join Date
    Sep 2004
    Posts
    153

    Once again..thanks!!

    Holy crap...xviddivxoggmp3, thanks for the website! Yeehaaa! I checked it out and it definitely is EXACTLY what I was hoping to find...you're awesome! -Chap

  14. #14
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    glad I could help.
    X
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  15. #15
    Registered User
    Join Date
    Oct 2004
    Posts
    26
    1. The basic idea of recursion is that you try to break down a big problem into similar but smaller subproblems.
      In turn, each similar smaller subproblem is broken down into similar, even smaller subsubproblems.
    2. You keep breaking problems down further and further until all the subsubsubsubproblems are small enough that you know how to solve them without breaking them down any further.


    Because the smaller subproblems are "similar", you can make the function call itself with the smaller subproblem as input. But if it keeps calling itself indefinitely, that's like an infinite loop (and will eat up all the computer's memory), so you have to do two things: (1) make absolutely sure that every time the function calls itself, it's calling itself on a STRICTLY SMALLER subproblem, (2) make absolutely sure that the method the function uses to break things down is guaranteed to eventually produce a problem it can answer without calling itself.

    Practically speaking, there's one other important consideration: at each step, the procedure for breaking a big problem down into smaller subproblems should not generate too many smaller subproblems. If the breakdown procedure at each step generates 10 subproblems, EACH of those subproblems may in turn generate 10 subsubproblems, EACH of which may generate 10 subsubsubproblems, etc. etc. This will rapidly eat up computer memory. Ideally, the breakdown procedure at each step should not generate more than 2 or 3 subproblems (3 is already a lot).

    The basic conceptual outline of a recursive function is like this:
    Code:
    answertype recursive_function (problemtype problem)
    {
    	answertype result;
    
    	if (problem is "bigger" than some level) {
    		do something to break the problem down into (hopefully only 1 or 2) smaller subproblems 
    		result = some combination of recursive_function(subproblem1) and recursive_function(subproblem2)
    	}
    	else if (problem is "smaller" than some level) {
    		result = something that doesn't require having the function call itself
    	}
    	
    	return result;
    }
    The factorial example is one where the problem is broken down into ONE smaller subproblem:

    Code:
    long factorial(int n)
    {
    	long	result;
    
    	if (n > 0) 				//"problem" is than some level
    		result = n * factorial(n-1);	//note that the input to the subproblem is SMALLER now
    	else if (n==0)				//"problem" is less than or equal to some level
    		result = 1;			//note that function is not calling itself
    	else /* n < 0, invalid */
    		result = -1;
    
    	return result;
    }
    If you tried to pretend being the computer, here's what you would do for factorial(5):
    Code:
    factorial(5) = 5 * factorial(4)					//break down factorial(5) into 5 * factorial(4)
    	     = 5 * (4 * factorial(3))				//break down factorial(4) into 4 * factorial(3)
    	     = 5 * (4 * (3 * factorial(2)))			//break down factorial(3) into 3 * factorial(2)
    	     = 5 * (4 * (3 * (2 * factorial(1))))		//break down factorial(2) into 2 * factorial(1)
    	     = 5 * (4 * (3 * (2 * (1 * factorial(0)))))		//break down factorial(1) into 1 * factorial(0)
    	     = 5 * (4 * (3 * (2 * (1 * (1)))))			//factorial(0) is easy:   return 1
    	     = 5 * (4 * (3 * (2 * (1)))) 			//factorial(1) now returns 1*1 = 1
    	     = 5 * (4 * (3 * (2)))				//factorial(2) now returns 2*1 = 2
    	     = 5 * (4 * (6))					//factorial(3) now returns 3*2 = 6
    	     = 5 * (24)						//factorial(4) now returns 4*6 = 24
    	     = 120						//factorial(5) now returns 5*24= 120

    Your ruler function is an example where the problem is broken down into TWO smaller subproblems. I've rewritten it to conform to the conceptual outline above:
    Code:
    void subdivide(char ar[], int low, int high, int level)
    {
        if (level > 0) {				//if "problem" is bigger than some level (i.e., level>0)
    	int mid = (high + low) / 2;		//then do something to break it down into smaller subproblems
    	ar[mid] = '|';				//namely, draw a line in the middle of the ruler
    	subdivide(ar, low, mid, level - 1); 	//then subdivide the left half; problem is smaller because LEVEL is smaller
    	subdivide(ar, mid, high, level - 1);	//and subdivide the right half; problem is smaller because LEVEL is smaller
    	return;
        }
        else if (level == 0)			//eventually reaches LEVEL where function doesn't have to break down any more
            return;					//just returns without calling itself
    }

    If you tried to pretend being the computer, here's what you would do for subdivide(ar, 0, 8, 2):
    Code:
    	0 1 2 3 4 5 6 7 8	//level==2>0, so do the stuff for level>0
    					//calculate mid=(8+0)/2==4
    	        |			//draw a line at ar[4]
    					//now subdivide(ar,0,4,1) (left  subarray of 0,8). level==1>0, so do stuff for level>0
    						//calculate mid=(4+0)/2==1
    	    |					//draw a line at ar[2]
    						//now subdivide(ar,0,2,0) (left  subarray of 0,4). level==0, so just return
    						//now subdivide(ar,2,4,0) (right subarray of 0,4). level==0, so just return
    					//now subdivide(ar,4,8,1) (right subarray of 0,8).  level==1>0, so do stuff for level>0
    						//calculate mid=(8+4)/2==6
    		    |				//draw a line at ar[6]
    						//now subdivide(ar,4,6,0) (left  subarray of 4,8). level==0, so just return
    						//now subdivide(ar,6,8,0) (right subarray of 4,8). level==0, so just return
    					//return
    You can see that even though the subdivide function breaks problems down into only two subproblems (subdivide the left subarray, subdivide the right subarray), each of those subproblems is broken into 2 subsubproblems before level==0 and we could stop breaking down and just return.

    This can rapidly get very hairy. Had we set level=3, there would have been 1 big problem, 1x2 subproblems, 1x2x2 subsubproblems, and 1x2x2x2 subsubsubproblems. Had we set level=6, there would have been 1x2**6 subsubsubsubsubsubproblems.

    Recursion is conceptually elegant once you can understand it, but in practice it can rapidly eat up a lot of resources, even with not very big input.

Page 1 of 2 12 LastLast
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. Trouble with recursion...
    By headbr in forum C Programming
    Replies: 2
    Last Post: 08-01-2008, 06:14 PM
  3. Recursion program trouble... ?
    By Beachblue in forum C Programming
    Replies: 7
    Last Post: 06-19-2008, 01:43 PM
  4. #include recursion trouble
    By ichijoji in forum C++ Programming
    Replies: 4
    Last Post: 07-01-2003, 05:15 PM
  5. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 09:56 AM

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