Thread: Recursive Triangle Function

  1. #1
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31

    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.

  2. #2
    Registered User
    Join Date
    Jan 2009
    Posts
    9
    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)
    Last edited by mMarko; 01-16-2009 at 12:32 PM. Reason: P.S. :)

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  4. #4
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31

    Thanks

    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?

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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);
    }
    Last edited by VirtualAce; 01-16-2009 at 07:03 PM.

  6. #6
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31
    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?

  7. #7
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.
    Last edited by VirtualAce; 01-16-2009 at 07:23 PM.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  9. #9
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  10. #10
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    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.

  11. #11
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  12. #12
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31

    Thank you everyone!

    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! */

  13. #13
    Registered User
    Join Date
    Jan 2009
    Posts
    9
    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 .
    Last edited by mMarko; 01-17-2009 at 05:36 PM.

  14. #14
    Registered User
    Join Date
    Apr 2009
    Posts
    1

    Wink Program

    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

  15. #15
    Registered User
    Join Date
    Nov 2010
    Posts
    1

    Wink this is much simpler... enjoy

    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("*");
    }
    }
    */

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 05:42 AM
  2. recursive function
    By tonderai76 in forum C++ Programming
    Replies: 11
    Last Post: 04-21-2004, 12:49 PM
  3. Replies: 5
    Last Post: 02-08-2003, 07:42 PM
  4. structure vs class
    By sana in forum C++ Programming
    Replies: 13
    Last Post: 12-02-2002, 07:18 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM

Tags for this Thread