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

---

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

As Hunter says:

Code:

---

char ruler[Len];

---

is only valid in C99.

Since Len is a const int, it should be fine, right?

Oh, didn't see the const :o

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

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

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

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

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.

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?

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

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

:D glad I could help.
X

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.

That's an excellent explanation - comprehensive and detailed. The only complaint I have is against:

(1) make absolutely sure that every time the function calls itself, it's calling itself on a STRICTLY SMALLER subproblem

While that generally will work, there are cases where it doesn't: namely, those cases where there is no calculable end to the recursion. Take for example a floodfill algorithm: For each adjacent pixel that is of the same colour, you recurse down that path setting the new colour as you go. Note that this does not break the problem into smaller sub-problems; although it branches, the problem is identical at each step in the recursion (unless you count the overall state of the program at which the function is executed) until at some point none of the surrounding pixels are of the target colour, and the function then returns.

zzzaaahhh,

I agree that is a good detailed explination.

recursion is very recursive in nature