CODEWITHSUNDEEP
c++recursion
Matt
Matt

Reputation: 95

using recursion instead of loops

I am trying to figure out an assignment that requires me to use recursion rather than loops to output a certain number of asterisks in a certain format.

basically, I am required to collect input from the user, and output something that looks like this

Number or asterisks: 5
*****
****
***
**
*
**
***
****
*****

I am struggling to figure this out, as I keep thinking about ways to figure it out by using a loop rather than with recursion. How am I supposed to output a certain number of items and have it know when to form a new line without a loop?

I am really having a hard time with this, and if someone could just help me figure out the first half I have a feeling I can do the second myself. I bet this is going to be one of those moments where I facepalm and get mad at myself for not seeing the answer sooner! This is using c++ by the way, more specifically visual studio 2015.

Thanks guys.

Upvotes: 0

Views: 871

Answers (2)

Jason
Jason

Reputation: 1099

Your main loop could be like this:

void printAsterix(int n)
{
    printRow(n);

    if(n > 1) printAsterix(n - 1);

    printRow(n);
}

Basically, on "n == 5" it prints a row of 5, then calls itself with n == 4, then prints another row of 5. This would give you the nested appearance.

You can also use recursion in how "printRow(n)" works. I'd suggest starting with a loop in there, get it all working with that, then make a recursive version of printRow. printRow would have to know to put the newlines on the end, once it finishes up. With that you need to take a minute to think through the recursion line by line and work out what order things will actually happen in:

void printRow(int n)
{
    cout << "*";

    if(n > 1)
    {
        printRow(n - 1);
    }
    else
    {
        cout << "\n\n";
    }
}

In this case it would go through and print a * for each of n 5,4,3,2,1, but then it'll notice n is not greater than 1, so instead of calling itself again it will print the two newlines. You need to be careful with recursion artefacts such that the commands happen in the right order. For example if you wrote

void printRow(int n)
{
    if(n > 1)
    {
        printRow(n - 1);
    }
    else
    {
        cout << "\n\n";
    }

    cout << "*";
}

The stars are all being printed on the return-side of the recursive calls - this is, anything AFTER the recursion calls happen in the reverse order of things before the calls. This means the newlines would occur before the *'s. Which might be completely fine, but you need to account for it.

Upvotes: 2

Steve Harris
Steve Harris

Reputation: 344

Interestingly I had a lot of problems with recursion early on.

Your question is pretty simple, though. Go straight to your simplest case, then think of it as one more than your simplest case and how to get to your simplest case.

Recursion requires that your function call itself, so you can think of it as a sort of "stacked iteration" if you like.

There is a really, REALLY cool book on things like strange loops and recursions, and I would recommend it highly: Gödel, Escher, Bach: An Eternal Golden Braid by Douglas R. Hofstadter.

Upvotes: 3

Related Questions