Recursive Triangle Function

I need some help on a problem. I have an assignment where we are asked to write 8 separate functions. However, I am also supposed to write an iteration version and a recursive version for each function. I have finished all of the iteration version functions and 6 of 8 recursive functions, but I am having difficulty with creating the last two recursively. So, I am asking for a little insight here.

These last two functions ask for a function that takes input from the user and uses that input to print a Triangle. The first function prints a triangle that stands on it's tip and the second one stands on its base.

For example:

Triangle 1 with user input 4 prints:

****
***
**
*

and Triangle 2 with user input 4 prints:

*
**
***
****

I have written the iteration version of these functions as follows and they work great.

Code:

---

/* Print a Triangle of Stars on it's tip
Input: a positive integer
Output: an n-sized triangle */
void Triangle(int s)
{
        int i = 0;
       
        while (s > 0)
        {
                for (i = 0; i < s; i++)
                {
                        printf("*");
                }
        printf("\n");
        s = s - 1;
        }
}

/* Print a Triangle of Stars on it's base
Input: a positive integer
Output: an n-sized triangle */
void TriangleTwo(int t)
{
        int i = 0;
        int x = 0;
        int y = 1;
        int counter = 0;
       
        while (counter < t)
        {
                x = t - (t - y);
               
                for (i = 0; i < x; i++)
                {
                        printf("*");
                }
        printf("\n");
        y++;
        counter++;
        }
}

---

My problem is that I need to convert these functions from iterations into recursive functions, but I can't seem to get them to work. I am not looking for a solution, just a helping hand to point me on the right track to finding a solution.

Any help is greatly appreciated.

I'm still learning C ...and recursion isn't really my speciality ;), I will have to think a little about it to give an answer.

Anyway I have a question about your second iterative version. Why did you use all those variables? Two of them are enough ;)

For example, what's the puropse of x?

Code:

---

x = t - (t - y);

---

=> x=t-t+y
=> x=y

Also I don't understand why do you initialize i to 0 at the beggining, when it's set to 0 in the for loop anyway.

P.S.

I see you used i++, y++ etc. everywhere. Why did you use s = s - 1 then?
s = s - 1 is the same as --s (or you could use s-- , in your case it would do the same as --s)

there are two variables to work with, the row (4), and the # of stars 4,3,2,1. do you need to recursively call both rows and stars, or will just one of the variables, do?

For a single variable recursion, you might have an if statement that returns when the base case is reached, and otherwise, prints one star, and recursively calls itself with number of stars - 1.

So putchar('*') would be fine, here. The recursion is "on" the number of stars that are printed. That would typically use a for loop in main() to control it:

(in pseudo code)

Code:

---

for row = 4 to 1
  call printIt(rows);

//in printIt(num) 
if num == 0
  return
otherwise:
  putchar '*'
  printIt(num-1);

---

Of course, the for loop in main is iterative. Only printIt() is recursive, but recursion inside of recursion is something I strictly avoid.

First of all, let me thank you both for replying and trying to help.

mMarko is right, I used some bad coding practices in the code
I posted and have since cleaned it up. I should have stuck with
the general theme and I am now using
s--
instead of
s = s - 1
As well, the code also should have read just
int i;
to declare the variable container, then it's initialized to 0 in the for loop.

As for the use of the other variables, here's what I'm doing.

t is an integer passed from main to the function TriangleTwo.
It declares the size of the triangle.
However, in this case I want the function to begin by printing only
one * at the top of the triangle therefore:

x = t - (t - y) = 1
because t = 4 and y is initialized to 1,
x = 4 - (4 - 1) = 4 - 3 = 1

the for loop then prints * consecutively on a line while i<x so the
first line prints one *

once the for loop completes, start a new line, y++, counter++
(we want to print lines until we have t *'s on a line)

the while loop continues and
x = 4 - (4 - 2) = 4 - 2 = 2

the for loop then prints *'s on a line while i<x so the second line
prints two **

once the for loop completes, start a new line, y++, counter++
and so on, while counter < t

I hope that clears up why I am using the extra variables mMarko.

Now, as for the advice from Adak,

The assignment asks for a fully recursive function to print the triangle.
We are not to use a for loop in main.

The function should receive the size from user input in main, and return
the triangle.

In other words, the entire triangle needs to be created recursively by
the function and then passed back to main.

I'm still stuck. any more advice out there?

Usually the recursive solution is much simpler than the iterative.

I won't show you this problem but I will show you recursion:

Code:

---

void SplitLine(int left,int right,int depth)
{
  static int count = 0;
  if (depth <= 0)
  {
        return;
  }

  int diff = right - left;
  std::cout << count << ": " << diff << std::endl;
  int mid = (left + right) / 2;
  ++count;

  SplitLine(left,mid,depth - 1);
  SplitLine(mid,right,depth - 1);
}

---

Thanks Bubba,

I think I understand recursion well enough even though
I am still a rather novice C programmer. And I agree, the
recursive problems for functions 1 through 6 of this
assignment came much easier than their iteration counterparts.

In fact, I just got Triangle 2 to work using recursion,
but I'm still having trouble with triangle 1.

Here's what I came up with for Triangle 2:

Code:

---

/* Print a Triangle of Stars on it's base
Input: a positive integer
Output: an n-sized triangle */
void TriangleTwo(int t)
{
    if (t < 1)
        return;        /* base case */
    else
    {
                TriangleTwo(t - 1);  /* recursive step */
       
        while(t > 0)
        {
            printf("*");
            t--;
        }
        printf("\n");
       
    }
}

---

It works great, but I'm still having problems flipping the triangle over.
I know the solution should be easy now that I have one version,
but Somehow I keep getting an infinite loop or a segmentation fault
whenever I try to manipulate the code I'm using for TriangleTwo to
create the flipped version for TriangleOne.

Any Suggestions?

Code:

---

void Triangle(int numGlyphs)
{
    if (numGlyphs <= 0)
    {
        return;
    }

    for (int i = 0;i < numGlyphs; ++i)
    {
        std::cout << "*";
    }
    std::cout << std::endl;
    Triangle(numGlyphs - 1);
}

---

Is that what you are looking for?

Code:

---

void TriangleTwo(int t)
{
    if (t < 1)
        return;        /* base case */
    else
    {
      TriangleTwo(t - 1);  /* recursive step */
       
        while(t > 0)
        {
            printf("*");
            t--;
        }
        printf("\n");
       
    }
}

---

I suspect this is your problem. You are calling back into the function before printing anything. Also:

Code:

---

if (t < 1)
        return;        /* base case */
    else

---

Should be:

Code:

---

if (t < 1)
{
  return;
}
else
{
  ...
}

---

You cannot just move your call below your print because you are decrementing the same variable that you are using to call back into the function. This means that 1 line will be printed and it will exit.

Wait a minute! I thought he couldn't use an iterative loop (for, while, do, etc.).

Maybe that's why I found it a brain teaser.

Code:

---

void printIt(int row, int star)
  {
  if(row)
      {
      putchar('*');
      --star;
      if(star == 0)
        {
        putchar('\n');
        star = row - 1;
        --row;
        }
      printIt(row, star);
      --row;
      }
  else
      {
      return;
      }
  }

---

Which is called initially with both row = 4 and star = 4.

Whether you can (or need to), integrate that into your larger program, I'll have to leave to you.

There was nothing in the post about not using this or that. He has to write the function using iteration and recursion. It said nothing of the what could be in the internals of either function.

I usually find that helper functions make recursion a lot more bearable. In this case they almost make the problem trivial:

Code:

---

// Print n asterisks and a newline
void asterisks(int n)
{
  if (n <= 0)
      putchar('\n');
  else
  {
      putchar('*');
      asterisks(n - 1);
  }
}

// Descending triangle (large at top, small at bottom)
void t1(int n)
{
  if (n > 0)
  {
      asterisks(n);
      t1(n - 1);
  }
}

// Ascending triangle (small at top, large at bottom)
void t2(int n)
{
  if (n > 0)
  {
      t2(n - 1);
      asterisks(n);
  }
}

---

However, you didn't mention being able to use helper functions.

Calling other functions from inside of recursive functions can increase the stack frame overhead significantly in some cases. I would not make a habit of it unless it was being called in the base case. You won't have any issues with this simple recursive function but later on you might. I call a CreateVertices() function in my base case for a function that creates a quad tree from a huge dataset. If I was to call CreateVertices() or any other function outside of the base case (and by chance if it called something else) I could easily get into a stack overflow.

You have all been a great help and I think that I may have
taken a little something from each of you in the way of
advice to finally finish the problem.

This is what I have come up with and they work within the
requirements of the assignment.

Code:

---

/* Print a Triangle of Stars on it's tip
Input: a positive integer
Output: an n-sized triangle */
void Triangle(int s)
{
       
    if (s == 1)
        printf("*");        /* base case */
    else
    {
                for(int i = 1; i <= s; i++)
                {
                        printf("*");
                }
        printf("\n");
        Triangle(s - 1); /* recursive step */
    }
}

/* Print a Triangle of Stars on it's base
Input: a positive integer
Output: an n-sized triangle */
void TriangleTwo(int t)
{
    if (t < 1)
        return;        /* base case */
    else
    {
                TriangleTwo(t - 1);  /* recursive step */
       
        while(t > 0)
        {
            printf("*");
            t--;
        }
        printf("\n");
       
    }
}

/* For user input of 4 in the program
Triangle prints:

****
***
**
*

and TriangleTwo prints:

*
**
***
****

Thanks for all the help! */

---

Ahh I thought you were supposed to write the recursive functions without using iteration. Anyway I'm glad you solved your problem.

P.S.

I'm sorry but I, still don't get your idea in the second iterative function :)

No matter what the values are ," x = t - (t - y)" is still the same as "x = y". If you don't trust me, try it :P.

I would write something like:

Code:

---

void TriangleTwo(int t)
{
    int i;
    int j=0;
   
    while(j<t)
    {
        for(i=0;i<=j;i++)
        {
            printf("*");
        }
        printf("\n");
        j++;
    }   
}

---

instead of:

Code:

---

void TriangleTwo(int t)
{
        int i = 0;
        int x = 0;
        int y = 1;
        int counter = 0;
       
        while (counter < t)
        {
                x = t - (t - y);
               
                for (i = 0; i < x; i++)
                {
                        printf("*");
                }
        printf("\n");
        y++;
        counter++;
        }
}

---

Basicaly it's the same thing, but why use x,y and counter when x=y=counter+1 all the time (well not all the time actualy, depends on where you check it, it's x=counter=y-1 on some places ;)). You can use just one variable for that.

...but then it's just me. It's your assignment after all :).

Code:

---

THIS IS MY PROGRAM, IT ONLY USES ONE FUNCTION. TRY IT



#include <iostream>
using namespace std;
void printstar(int nbofstar);

int main()
{
int numberofstar;
cout<<"PLEASE ENTER THE NUMBER OF STAR"<<endl;
cin>>numberofstar;
printstar(numberofstar);
return 1;
}

void printstar(int nbofstar)
{
if (nbofstar>0)
{int counter;
for(counter=1;counter<=nbofstar; counter++)
{cout<<"*";
}
cout<<endl;

printstar( nbofstar-1);

for(counter=1;counter<=nbofstar; counter++)
{cout<<"*";
}
cout<<endl;
}//end of if
}//end of the function

---

void mirror_triangle(int n)
{
if (n==1) printf("*");
else
{
printstar(n);
printf("\n");
mirror_triangle(n-1);
printf("\n");
printstar(n);
}
}

it prints (ex: n=5):
*****
****
***
**
*
**
***
****
*****
/*
you can use this recursion to print one line of stars instead of a loop:
void printstar(int n)
{
if (n==1) printf("*");
else
{
printstar(n-1);
printf("*");
}
}
*/