Archived

This topic is now archived and is closed to further replies.

A Recursion(shudder!!!) Problem!!!!

This topic is 5974 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I am new to programming in C++ and have run into a program I can not code: User inputs a number x the number is written from x down to zero the number is written from zero up to x these 2 lines are written x times. The thing holding me back is that I cant code a function to write from x to zero and zero to x. Any help would be SUPER appreciated as this is making my stay up late and my head hurt, and I cant go on in my studies cause I''m always thinking of how to solve it. ANY HELP APPRECIATED!!! Sincerely Me.

Share this post


Link to post
Share on other sites

Hi,

I am new to programming in C++ and have run into a program I can not code:

User inputs a number x
the number is written from x down to zero
the number is written from zero up to x
these 2 lines are written x times.

The thing holding me back is that I cant code a function to write from x to zero and zero to x. Any help would be SUPER appreciated as this is making my stay up late and my head hurt, and I cant go on in my studies cause I''m always thinking of how to solve it. ANY HELP APPRECIATED!!!



ok, say x is 3
1: 3 to 0 - 3,2,1,0
2: 0 to 3 - 0,1,2,3
all of that 4 times (0,1,2,3 - 4 total numbers)
so,
u go:

for (int t=0;t<=x;t++) // x times those lines
{
for (int y=x;y<=0;y--)
{
textout (y); // from x to 0 if x>0
}
for (int z=0;z<=x;z++)
{
textout(z); // from 0 to x
}
}


" Do we need us? "


Warrior of Great Darkness

Share this post


Link to post
Share on other sites
if you really wanted a recursive solutionthat could do both, you could do something like:

#define UP +1
#define DOWN -1

void Count(int start, int finish, int updown)
{
printf("%d\n",start);

if(start==finish)
return;

Count(start+updown,finish,updown);

return;
}

Then to use it, you can do something like this

void main( int argc, char *argv[] )
{
int x = 0;

scanf("%d",x);

Count(x,0,DOWN);
Count(0,x,UP);

return;
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Okay if the original poster is still checking this for updates he''ll notice very different and very similar answers to his problem. The thing is no one has pointed out why they are different and similar at the same time and this will no doubt frustrate the original poster.

The two kinds responses given have either been recursive functions or for/while/do-while loops. The reason why both can be used to generate equally valid answers is any loop can be transformed into a tail-recursive function (I''ll define this in a second.). This can be done since they both repeat their body by either looping (How does a computer do this you think? If your compiler did its job right it does the same for both, it adjusts the PC, but most don''t.) or calling itself [function].

Here is a function that will display all numbers from n to 0 counting down:

void f(int n)
{
cout << n << '' '';

if (n == 0)
{
return;
}
else
{
f(n-1);
}
}

The equivalent method in the form of a loop is:

for (int i = n; i >= 0; i--)
{
cout << i << '' '';
}

The key in understanding the similarity is noting that in the tail-recursive function there is no need for the use of a counting variable since the runtime stack is used to mimick its behavior. The parameter of each successive call to f is decreased by 1 and when it equals 0 the function stops, just as the for loop terminates. It is more common to write the above function as the following though:

void f(int n)
{
if (n == 0)
{
cout << 0 << endl;
}
else
{
cout << n << '' '';
f(n-1);
}
}

With a simple modification the above function can also display the numbers growing from 0 to n:

void f(int n)
{
if (n == 0)
{
cout << 0;
}
else
{
cout << n << '' '';
f(n-1);
cout << '' '' << n;
}
}

If a call to f(4) is made the output will be:

4 3 2 1 0 1 2 3 4

Each number represents a new frame ushed onto or popped off of the stack. If n decreases a frame has been pushed on and if n increases a frame has been popped off. This frame pushing and popping mimicks the concept of "something" changing each time through the loop. An alternative method would be to break f up into two functions; one function which counts down and another that counts up. You may then convert both tail-recursive functions into simple for loops that will be similar to what others posted in reply.

If you can do that you''ll be well on your way to understanding recursion. Try to do in on paper first, and then code it. Stack overflow errors aren''t pretty on all operating systems. Another thing you can do is find a math book with some information on induction. Most proofs of algorithm correctness are done by induction and reverse-induction is the idea behind dynamic programming--look that up in an algorithm book.

Luck to ya.

Share this post


Link to post
Share on other sites
I made a little function that can accomplish your task. However you have to use it a specific way. Assign A and B as X then set adder to -1. (ex. BtoZerotoA(X,X,-1)

I hope this will help. I haven''t tested it myself so please let me know what happens.

Input:
A - X or the Max count value (must be a positive whole number)
B - Current Count Value (must be from A to 0)
adder - counter (must be a negative whole number from -1 to -A)

Output:
Increments B to Zero by adder(negative value) then increments zero to A by adder reversed(positive value).

Here''s the code:

BtoZerotoA(A,B,adder)
{
// First, test if adder is valid
// that is non-zero
if (adder==0)
{return;}

// Second, Test if B is within A to Zero Range
// then Display B
if((B<=A)&(B<0))
{
// Display B

BtoZerotoA(A,B+adder,adder);
}

// Third, Test if B is Zero
// then change adder''s direction
if(B=0)
{
// Display B if 0 value is need in output

// Reverese adder''s direction from negative
// to positive
adder *= -1;

BtoZerotoA(A,B+adder,adder);
}

// End of btoZerotoA
return;
}

Share this post


Link to post
Share on other sites