Recursive Triangle Function

w2look · 01-16-2009, 10:53 AM

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.

mMarko · 01-16-2009, 12:15 PM

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)

Adak · 01-16-2009, 12:49 PM

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.

w2look · 01-16-2009, 05:21 PM

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?

**Bubba** · 01-16-2009, 06:49 PM

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);
}

w2look · 01-16-2009, 07:10 PM

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?

**Bubba** · 01-16-2009, 07:14 PM

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.

Adak · 01-16-2009, 08:30 PM

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.

**Bubba** · 01-16-2009, 10:38 PM

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.

arpsmack · 01-16-2009, 11:59 PM

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.

**Bubba** · 01-17-2009, 02:54 AM

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.

w2look · 01-17-2009, 11:50 AM

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

mMarko · 01-17-2009, 05:17 PM

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

.

amira18 · 04-01-2009, 02:39 AM

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

01-16-2009, 10:53 AM	#1
w2look Registered User 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.
w2look is offline

01-16-2009, 12:15 PM	#2
mMarko 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. :)
mMarko is offline

01-16-2009, 12:49 PM	#3
Adak Registered User Join Date: Sep 2006 Posts: 2,512	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.
Adak is offline

01-16-2009, 05:21 PM	#4
w2look Registered User 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?
w2look is offline

01-16-2009, 06:49 PM	#5
Bubba Super Moderator Join Date: Aug 2001 Posts: 7,472	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); } __________________ If you aim at everything you will hit something but you won't know what it is. Last edited by Bubba; 01-16-2009 at 07:03 PM.
Bubba is offline

01-16-2009, 07:10 PM	#6
w2look Registered User 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?
w2look is offline

01-16-2009, 07:14 PM	#7
Bubba Super Moderator Join Date: Aug 2001 Posts: 7,472	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. __________________ If you aim at everything you will hit something but you won't know what it is. Last edited by Bubba; 01-16-2009 at 07:23 PM.*
Bubba is offline

01-16-2009, 08:30 PM	#8
Adak Registered User Join Date: Sep 2006 Posts: 2,512	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.
Adak is offline

01-16-2009, 10:38 PM	#9
Bubba Super Moderator Join Date: Aug 2001 Posts: 7,472	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. __________________ If you aim at everything you will hit something but you won't know what it is.
Bubba is offline

01-17-2009, 02:54 AM	#11
Bubba Super Moderator Join Date: Aug 2001 Posts: 7,472	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. __________________ If you aim at everything you will hit something but you won't know what it is.
Bubba is offline

01-17-2009, 05:17 PM	#13
mMarko 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.
mMarko is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
recursive function	technosavvy	C Programming	1	02-29-2008 05:42 AM
recursive function	tonderai76	C++ Programming	11	04-21-2004 12:49 PM
Didn't quite know where to post this.......compiler problem...	incognito	C++ Programming	5	02-08-2003 07:42 PM
structure vs class	sana	C++ Programming	13	12-02-2002 07:18 AM
Contest Results - May 27, 2002	ygfperson	A Brief History of Cprogramming.com	18	06-18-2002 01:27 PM