C++ Help with my recursive function

[mrmodest34]

Greetings, this is my first post here but I will try to do it correctly. I know this specific question is a common one, but I am not looking for someone to do it for me, I just need someone to help me out a little. I understand the basics of recursion, but I have run into something that has stumped me. The question is, using only one recursive function, produce the pattern below based on the integer n(maximum amount of asterisks being displayed. I can either make the top of the hill to appear or the bottom. I am having trouble making both the top and bottom appear with only one function recursively. I can do this without recursion but only with 2 separate functions.

so if n = 5 then the hill would look like this,

*
**
***
****
*****
****
***
**
*

My code for the function so far is,

void stars(int n){
if(n > 0){
stars(n-1);
for(int i = 0; i < n;i++){
cout << "*";
}
cout << endl;
// if I were to place stars(n-1) here I would get the bottom half
}
}

----------------------
output:
*
**
***
****
*****
----------------------

I am just having trouble wrapping my head around how to do all of this in 1 function recursively. If you can show me something that could help, please let me know. Thanks in advance!

[Labdabeta]

Try running this code and see what you can make of it:

void recursiveTest(int cntr)
{
    if (cntr==0)
    {
        cout<<"Pivotting..."<<endl;
    }
    else
    {
        cout<<"Winding up..."<<endl;
        recursiveTest(cntr-1);
    }
    cout<<"Unwinding..."<<endl;
}
int main()
{
    recursiveTest(5);
    return 0;
}

[mrmodest34]

Try running this code and see what you can make of it:

void recursiveTest(int cntr)
{
    if (cntr==0)
    {
        cout<<"Pivotting..."<<endl;
    }
    else
    {
        cout<<"Winding up..."<<endl;
        recursiveTest(cntr-1);
    }
    cout<<"Unwinding..."<<endl;
}
int main()
{
    recursiveTest(5);
    return 0;
}

I am trying to implement my code into that but I am still not successful I suppose it will take some time. I am still trying to do it with 2 for loops but I thought the purpose of recursion was to get rid of loops all together.

This is what I have now based on what you sent me, I think I am getting a bit closer...

void recursiveTest(int cntr)
{
if (cntr==0)
{
cout<<"CENTER"<<endl; // center
}
else
{
// for top half
for(int i = 0; i < cntr; i++){
cout << "*";

}
cout << endl;
recursiveTest(cntr-1);
}
cout << "UNWINDING" << endl;
}

current output:

*****
****
***
**
*
CENTER
UNWINDING
UNWINDING
UNWINDING
UNWINDING
UNWINDING
UNWINDING

[Labdabeta]

You may need two parameters. Here is an example that should help you along a bit:

void recursiveTest(int val, int start)
{
    if (val==0)
    {
        cout<<"Pivotting..."<<endl;
    }
    else
    {
        cout<<"Winding up, time #"<<start-val<<"..."<<endl;
        recursiveTest(val-1,start);
    }
    cout<<"Unwinding, time #"<<start-val<<"..."<<endl;
}
void callRecursiveFunction(int val)
{
    recursiveTest(val,val);
}

[mrmodest34]

You may need two parameters. Here is an example that should help you along a bit:

void recursiveTest(int val, int start)
{
    if (val==0)
    {
        cout<<"Pivotting..."<<endl;
    }
    else
    {
        cout<<"Winding up, time #"<<start-val<<"..."<<endl;
        recursiveTest(val-1,start);
    }
    cout<<"Unwinding, time #"<<start-val<<"..."<<endl;
}
void callRecursiveFunction(int val)
{
    recursiveTest(val,val);
}

I can only do this with 1 parameter unfortunately.

[Labdabeta]

Hmmm... in that case, unless you get off on a technicality you will need iterative recursion. This is where you make a recursive call in a loop. I am working on the solution myself... I happen to have trouble with iterative recursion.

[Labdabeta]

I was just thinking... without some kind of hack of some format this is impossible. Just think about it. if calling starTree(5) gives:
*
**
***
****
*****
****
***
**
*

and calling starTree(4) gives:
*
**
***
****
***
**
*

Since starTree(4) is in no way part of starTree(5) at least linearly, this leaves but two options:
1) Platform specific console commands to shift the position of the put cursor.
2) Storing the data, either as another parameter, or a global variable or something
3) I cannot think of anymore, but I love to find out that I am wrong.

Here are a couple ways to do number 2:

//if initially int was the limit, we can use the upper bit of
//  this version of n to store the initial value
void drawTree(unsigned int n)
{
    if (!(n&0xFFFF0000))//this is the first call
        n|=(n<<16);//if n WAS 0x0000WXYZ now it IS 0xWXYZWXYZ
    int val=(int)(n&0x0000FFFF);//just get THIS n
    int start=(int)(n&0xFFFF0000);
    start>>=16;//lets go back
    if (val)//AKA: if (val!=0)
    {
        /*Apparently ++i is better than i++ because
         *  i++ requires that a copy of i be temporarily
         *  created. Though with ints this is avoided by
         *  the compiler, ++i is at least as fast if not
         *  faster than i++. This is especially true for
         *  complex data types, but it is not all that
         *  important. I often forget to change this myself.
         */
        for (int i=0; i<start-val; ++i)
        {
            cout<<"*";
        }
        cout<<endl;
        drawTree(n-1);//we can just take one off of n
    }
    for (int i=0; i<start-val; ++i)
    {
        cout<<"*";
    }
    cout<<endl;
}

Here is a 'better' method:

struct treeFuncData
{
    int start;
    int n;
};
//if initially int was the limit, we can use the upper bit of
//  this version of n to store the initial value
void drawTree(treeFuncData n)
{
    if (n.start==0)
        n.start=n.n;
    if (n.n)
    {
        for (int i=0; i<n.start-n.n; ++i)
        {
            cout<<"*";
        }
        cout<<endl;
        n.n-=1;
        drawTree(n);//we can just take one off of n
        n.n+=1;
    }
    for (int i=0; i<n.start-n.n; ++i)
    {
        cout<<"*";
    }
    cout<<endl;
}
void drawMeATree(int n)
{
    drawTree({0,n});
}

Either way, without console seeking, I cannot see any way to do this. I would love to be proven wrong by some beautiful piece of code, I just can't imagine what it could be.

[mrmodest34]

I was just thinking... without some kind of hack of some format this is impossible. Just think about it. if calling starTree(5) gives:
*
**
***
****
*****
****
***
**
*

and calling starTree(4) gives:
*
**
***
****
***
**
*

Since starTree(4) is in no way part of starTree(5) at least linearly, this leaves but two options:
1) Platform specific console commands to shift the position of the put cursor.
2) Storing the data, either as another parameter, or a global variable or something
3) I cannot think of anymore, but I love to find out that I am wrong.

Here are a couple ways to do number 2:

//if initially int was the limit, we can use the upper bit of
//  this version of n to store the initial value
void drawTree(unsigned int n)
{
    if (!(n&0xFFFF0000))//this is the first call
        n|=(n<<16);//if n WAS 0x0000WXYZ now it IS 0xWXYZWXYZ
    int val=(int)(n&0x0000FFFF);//just get THIS n
    int start=(int)(n&0xFFFF0000);
    start>>=16;//lets go back
    if (val)//AKA: if (val!=0)
    {
        /*Apparently ++i is better than i++ because
         *  i++ requires that a copy of i be temporarily
         *  created. Though with ints this is avoided by
         *  the compiler, ++i is at least as fast if not
         *  faster than i++. This is especially true for
         *  complex data types, but it is not all that
         *  important. I often forget to change this myself.
         */
        for (int i=0; i<start-val; ++i)
        {
            cout<<"*";
        }
        cout<<endl;
        drawTree(n-1);//we can just take one off of n
    }
    for (int i=0; i<start-val; ++i)
    {
        cout<<"*";
    }
    cout<<endl;
}

Here is a 'better' method:

struct treeFuncData
{
    int start;
    int n;
};
//if initially int was the limit, we can use the upper bit of
//  this version of n to store the initial value
void drawTree(treeFuncData n)
{
    if (n.start==0)
        n.start=n.n;
    if (n.n)
    {
        for (int i=0; i<n.start-n.n; ++i)
        {
            cout<<"*";
        }
        cout<<endl;
        n.n-=1;
        drawTree(n);//we can just take one off of n
        n.n+=1;
    }
    for (int i=0; i<n.start-n.n; ++i)
    {
        cout<<"*";
    }
    cout<<endl;
}
void drawMeATree(int n)
{
    drawTree({0,n});
}

Either way, without console seeking, I cannot see any way to do this. I would love to be proven wrong by some beautiful piece of code, I just can't imagine what it could be.

Ok, think about this though,

void recursiveTest(int n)
{

if(n > 0)
{
// for top half
recursiveTest(n-1);
for(int i = 0; i < n; i++)
cout << "*";
cout << endl;
}
else if(n == 0){
// bottom half... but how?
}
}

int main()
{
recursiveTest(5);
return 0;
}

So, this code here prints out just the top part. So I run the function at the top only if n > 0 so then I decrement n each time and run through the for loop. Now, do you think there is a way I could just call n + 1 recursively somewhere but after I return to the inital state of n? n would have to be 5 once more... it can be done I was told but I can't wrap my head around it.

[Labdabeta]

The problem with incrementing n, even if you decrement it is that you end up with an infinite loop because each time the function is called n will continue to increase until you get to n=some really big number, at which point n will become negative and you will have a console filled to the brim with asterisks. I thought that it should be possible too, but if you think about it using reductio ad absurdum you get:

Assuming drawTree(X) draws the desired pattern by drawing a smaller tree, since the pattern takes the form (replacing n asterisks with merely n and new lines with commas):

drawTree(X)=1,2,3,...,n-2,n-1,n,n-1,n-2,...,3,2,1

to define the call recursively we would require:

drawTree(X)=something or nothing,drawTree(something or nothing, but not this),something or nothing

since we require that only the first and last values are 1 we need drawTree at the ends:

nothing,drawTree(something or nothing),nothing

This leads to a tautological statment that:

drawTree(X)=drawTree(something or nothing, but not this)
drawTree(X)=drawTree(not X)

Since drawTree is 'one-to-one' we know that drawTree(X) cannot equal anything but drawTree(X). Since when we assumed the problem was possible we ran into a contradiction the problem itself therefore must be contradictory.

Incidentally I was able to get code that would draw the top, OR the bottom of the tree, but not both. I cannot think of any way that it could be possible, as you can see in a fairly well-reasoned proof above. The proof does not exclude iterative approches such as:

void drawTree(int n)
{
    for (int i=1; i<n; ++i)
    {
        for (int ii=0; ii<i; ++ii)
            cout<<"*";
        cout<<endl;
    }
    for (int i=n; i>0; --i)
    {
        for (int ii=0; ii<i; ++ii)
            cout<<"*";
        cout<<endl;
    }
}

[mrmodest34]

The problem with incrementing n, even if you decrement it is that you end up with an infinite loop because each time the function is called n will continue to increase until you get to n=some really big number, at which point n will become negative and you will have a console filled to the brim with asterisks. I thought that it should be possible too, but if you think about it using reductio ad absurdum you get:

Assuming drawTree(X) draws the desired pattern by drawing a smaller tree, since the pattern takes the form (replacing n asterisks with merely n and new lines with commas):

drawTree(X)=1,2,3,...,n-2,n-1,n,n-1,n-2,...,3,2,1

to define the call recursively we would require:

drawTree(X)=something or nothing,drawTree(something or nothing, but not this),something or nothing

since we require that only the first and last values are 1 we need drawTree at the ends:

nothing,drawTree(something or nothing),nothing

This leads to a tautological statment that:

drawTree(X)=drawTree(something or nothing, but not this)
drawTree(X)=drawTree(not X)

Since drawTree is 'one-to-one' we know that drawTree(X) cannot equal anything but drawTree(X). Since when we assumed the problem was possible we ran into a contradiction the problem itself therefore must be contradictory.

Incidentally I was able to get code that would draw the top, OR the bottom of the tree, but not both. I cannot think of any way that it could be possible, as you can see in a fairly well-reasoned proof above. The proof does not exclude iterative approches such as:

void drawTree(int n)
{
    for (int i=1; i<n; ++i)
    {
        for (int ii=0; ii<i; ++ii)
            cout<<"*";
        cout<<endl;
    }
    for (int i=n; i>0; --i)
    {
        for (int ii=0; ii<i; ++ii)
            cout<<"*";
        cout<<endl;
    }
}

Yeah, I have gotten it to work either way but not both ways. I do have to figure it out though because it is possible. Maybe a logarithmic way to do it or something. I bet there is someone on here that knows how to do it they just probably haven't seen this thread yet.

[Labdabeta]

Well... I got one working, it technically meets the requirements... but I don't count it as a true solution.

void drawTree(int n)
{
    if (n<0)
    {
        for (int i=n; i<0; ++i)
            cout<<"*";
        cout<<endl;
        drawTree(n+1);
    }
    if (n>0)
    {
        drawTree(n-1);
        for (int i=1; i<n; ++i)
            cout<<"*";
        cout<<endl;
    }
}
void drawMeATree(int n)
{
    drawTree(n);
    drawTree(-n);
}

I just don't like it because it is based on a dual call, but as proven above it would be completely impossible to do this as a single traditional recursive call. But to recap, a recursive call by definition calls itself, but with different arguments. Since writing to the console is linear, we can only append to it (that means no going back, or shifting at all) unless we can 'tack' something to the start or the end of the output of the call to change it to another call, we are unable to complete the problem.

[mrmodest34]

Well... I got one working, it technically meets the requirements... but I don't count it as a true solution.

void drawTree(int n)
{
    if (n<0)
    {
        for (int i=n; i<0; ++i)
            cout<<"*";
        cout<<endl;
        drawTree(n+1);
    }
    if (n>0)
    {
        drawTree(n-1);
        for (int i=1; i<n; ++i)
            cout<<"*";
        cout<<endl;
    }
}
void drawMeATree(int n)
{
    drawTree(n);
    drawTree(-n);
}

I just don't like it because it is based on a dual call, but as proven above it would be completely impossible to do this as a single traditional recursive call. But to recap, a recursive call by definition calls itself, but with different arguments. Since writing to the console is linear, we can only append to it (that means no going back, or shifting at all) unless we can 'tack' something to the start or the end of the output of the call to change it to another call, we are unable to complete the problem.

Great, I had tried that earlier but I must have messed up the syntax because I was not getting an output. But I also sent the value positive only one time instead of trying a negative value. I am now going to try to have two rows of n in the middle before the decrementing begins. Thanks for your help.