# trouble with recursion

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 09-30-2004
Chaplin27
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); }```
• 09-30-2004
Hunter2
>>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).
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.
• 09-30-2004
Kybo_Ren
As Hunter says:
Code:

`char ruler[Len];`
is only valid in C99.
• 09-30-2004
jlou
Since Len is a const int, it should be fine, right?
• 09-30-2004
Kybo_Ren
Oh, didn't see the const :o
• 09-30-2004
Chaplin27
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
• 09-30-2004
Hunter2
>>or even just a general overview of recursion would help...anything at all would be great...
:rolleyes: 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?
• 09-30-2004
Chaplin27
much needed help
hunter2...thanks for your patience and your help...you're the *beep* and I greatly appreciatethe help...thanks! -Chap
• 09-30-2004
Vicious
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.

its jverkoeys sig. :D
• 09-30-2004
xddxogm3
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.
• 10-01-2004
misplaced
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?
• 10-01-2004
xddxogm3
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
• 10-01-2004
Chaplin27
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
• 10-02-2004
xddxogm3
:D glad I could help.
X
• 10-02-2004
zzzaaahhh
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.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last