Advice for writing a simple number triangle, only with recursion, no loops?

Question

So I have already written a function to write a number pyramid of variable height using several for loops and it works perfectly.

Here's an example of the kind of pyramids I'm talking about:

User Enters 4

      1 

    1 2 1

  1 2 3 2 1 

1 2 3 4 3 2 1 

So I do indeed need to pad the left side with whitespace.

My problem is I can't get it to work with recursion only, no loops. I can't even think of a place to start in terms of recursion, really. I know I need a base case, as well as a way to approach that base case.

Should I write multiple recursive functions, or is there a way to do it with just one? (In addition to main, I mean.)

Here's what I have so far (it's not much at all):

void givepyramid(int lines);  //lines = Number of lines in pyramid (4 in example above)
{
     if lines == 1;
        cout << (//all the spaces needed)<<1;
     else
         cout << (I'm not too sure on how to go about this here.)
}

Any advice would be much appreciated! Thanks.

Answer 1

I created folowing solution. It works with number of lines more 10.

#include <iostream>
#include <vector> 
using namespace std;

void buildLine(int countline, int iteration)
{
 cout << string((countline-iteration),'\t');


 for(int i = 0; i < iteration; ++i)
 {
  cout << i+1 << "\t";
 }

 for(int i = iteration-1; i > 0; --i)
 {
   cout << i << "\t";
 }

 cout << string(countline-iteration,'\t') << endl;

 buildLine(countline,++iteration);

}

void buildPyramid(int lines)
{
 buildLine(lines, 1);
}


int main() {

   buildPyramid(11); 
}

Answer 2

Here is a simple solution which draws pretty triangles without using loops:

#include <iostream>

void printRowNumbers( unsigned int n, unsigned int max )
{
    if ( n < max ) {
        std::cout << n << ' ';
        printRowNumbers( n + 1, max );
    }
    std::cout << n << ' ';
}

void drawTriangle( unsigned int n, unsigned int indent = 0 )
{
    if ( n > 1 ) {
        drawTriangle( n - 1, indent + 2 );
    }
    std::cout << std::string( indent, ' ' );
    printRowNumbers( 1, n );
    std::cout << "\n";
}

The main idea is that there are two problems really which you'd usually tackle using loops:

1. Printing a row of numbers (without any particular indentation) like 1 2 3 2 1 or 1 2 3 4 5 4 3 2 1. The key idea is that you aren't only printing the numbers up to a maximum value and back, you are in fact printing the numbers from some start value (which seems to be always 1 here) up to a maximum and then back to the start value.

   The insight is that printing such a "number mirror" from 1 to 5 and back is the same thing as printing 1, then printing a mirror from 2 to 5, then printing 1 again. And printing a mirror from 2 to 5 is the same as printing a 2, then doing a mirror from 3 to 5, then printing 2 again. And so on, up to the point where your minimum value is the same as the maximum, in which case you just print that number (that's your base case).

2. Printing something a number of times, each time on a new line with an ever decreasing indentation. We would need a function which can print something (say, a letter) a number of times - each time, on its own line and with ever-decreasing indentation. The last line is not indented at all. The simple case is printing just one line - in that case you don't have any indentation at all. Printing two lines would be the same thing as printing one line first with an indentation of, say, 2 - and then printing the line again. Printing three lines means printing two lines with an indentation of 2 first (which in turn means printing one line with an indentation of four!), then the third line with no indentation.

   Our code just happens to not print some random letter, instead the drawTriangle function takes care of getting the indentation right (and printing a newline) but lets printRowNumbers print the actual numbers.

As you can see, I didn't use a terribly analytical approach (it's possible to rewrite any loop into a recursion, so you could've written a loop and then mechanically transform it into a recursion by following some rules). Instead, I just did a few experiments by hand like "How does doing this two times differ from doing it just once, and how does doing it thrice differ from doing it twice" and then spot a pattern.

Answer 3

You may replace

for (int i = 0; i != N; ++i) {
    body(i, localVars);
}

by

void body_rec(int N, int i, LocalVars& localVars)
{
    if (i == N) return;
    body(i, localvars);
    body_rec(N, i + 1, localVars)
}

Answer 4

A simple and recursive function without loops:

void printTree(int maxLevel, int currLevel = 0, int currPos = 1)
{
    if(currLevel>maxLevel)
        return;
    if(currPos<(maxLevel-currLevel))
    {
        cout<<'\t';
        printTree(maxLevel, currLevel, ++currPos);
    }
    else if(currPos<(maxLevel-currLevel + currLevel*2)-1)
    {
        cout<<((maxLevel - currPos)<=0?(currPos - maxLevel)+2:(maxLevel - currPos))<<'\t';
        printTree(maxLevel, currLevel, ++currPos);
    }
    else
    {
        cout<<endl;
        printTree(maxLevel, ++currLevel, 0);
    }
}

For your example, call the function as printTree(4)

Answer 5

Works for numbers > 10, and fully without loops.

PS:C++11

#include <iostream>
#include <vector>
#include <string>


void gen_numbers(int len, int number, std::string &ans) {

    if (len > 1) {
        ans.append(std::to_string(number));
        ans.push_back(' ');
        gen_numbers(len - 1, number + 1, ans);
        ans.push_back(' ');
        ans.append(std::to_string(number));
    }
    if (len == 1)
        ans.append(std::to_string(number));

}

void print_spaces(int number) {
    std::cout << " ";
    if (number)
        print_spaces(number - 1);
}

void draw (int line, int depth) {
    if (line > 1) {
        draw(line - 1, depth);
    }

    print_spaces(2 * (depth - line));
    std::string ans;
    gen_numbers(line, 1, ans);
    std::cout << ans;
    print_spaces(depth - line);
    std::cout << std::endl;
}



int main() {
    draw(12, 12);
    return 0;
}

Answer 6

You can use two different recursive functions, which may or may not be reducible to a single recursive function. The example below can be edited to pad the left relatively simply and is left as an exercise. Essentially, you want to build the rows of the string on the left and right separately, then join them around the center number.

std::string buildString(int i, bool side)
{
    if(i < 1)
    {
        return "";
    }
    if(i == 1)
    {
        return "1";
    }
    if(i > 1)
    {
        std::ostringstream s;
        s << i;
        if(side == false) // left build
        {
             return buildString(i - 1, false) + " " + s.str();
        }
        if(side == true) // right build
        {
             return s.str() + " " + BuildString(i - 1, true);
        }
     }
 }

 //pass is function the expected length as well in order to enable padding
 void buildPyramid(int i /*, int max */)
 {
     if(i < 1)
     {
          return;
     }
     if(i > 1)
     {
          //by calling build pyramid recursively and falling through to the print statement after, you can cause the top of the pyramid to print first without looping
          buildPyramid(i - 1);
     }
     //the center number of each row is added here since it's the only number that isn't duplicated. By storing the resultant string in an ostringstream you can check the length and add padding.
     std::cout << buildString(i - 1, false) << " " << i << " " << buildString(i - 1, true);
 }

Answer 7

I haven't tested this code, but you could do something like this. It doesn't make use of any loops. This will print out an inverted pyramid, so I will leave the un-inverting part as an exercise for the reader.

void givepyramid(int lines)
{
    giveIndentedPyramid(lines, 0);
}

void giveIndentedPyramid(int line, int indentation)
{
    printIndentationRecursive(indentation);

    if(line > 0)
    {
        printLineRecursiveUp(1, line);
        printLineRecursiveDown(line);

        cout << endl;
        giveIndentedPyramid(line-1, indentation+2);
    }
}

void printIndentationRecursive(int indentation)
{
    /*
    for(int i = 0; i < indentation; i++)
    {
        cout << " ";
    }
    */
    if(indentation > 0)
    {
        cout << " ";
        printIndentationRecursive(indentation-1);
    }
}

void printLineRecursiveUp(int current, int line)
{
    /*
    for(int i = 1; i < line; i++)
    {
        cout << i << " ";
    }
    */
    if(current < line)
    {
        cout << current << " ";
        printLineRecursiveUp(current + 1, line);
    }
}

void printLineRecursiveDown(int line)
{
    if(line > 0)
    {
        cout << line << " ";
        printLineRecursiveDown(current - 1, line);
    }
}

Keep in mind this is untested code, so treat it as pseudo-code that you can use as a guideline to learn how to use recursion.