# Recursive function

1. Apr 18, 2013

### sandy.bridge

1. The problem statement, all variables and given/known data
Hey, this isn't really homework, but my professor stated that any loop can be represented by a recursive function. Here is an example I made:

Following is a loop inside of a recursive function. I have it set up such that it takes n asterisks and prints them on a single line; prints a new line; prints n-1 asterisks; stops at n=0.

Code (Text):
void printStars(int n)
{
if (n > 0)
{
for(int i = 0; i < n; i++)
{
cout << '*';
}
cout << endl;
return printStars(n-1);
}
return;
}
If printStars(5) is called, then
Output:
*****
****
***
**
*

If I get rid of the for loop and attempt the utilize a recursive function for printing that line, the issue I have is that upon printing the line, once a new line is printed, n=0 and the second line cannot be printed. For example:

Code (Text):
void printStars(int n)
{

if(n > 0)
{
cout << '*';
return printStars(n-1);
}
cout << endl;

return;
}
What should I be doing such that n reverts back to what it was? Dummy variable?

2. Apr 18, 2013

### Staff: Mentor

Your second version of printStars prints one line of stars and then prints a newline character. As written, this version should be called (in main, typically) once for each line.

3. Apr 18, 2013

### sandy.bridge

Hmm, I don't have that option with the second one. The question states that only recursive functions can be used. The only code in the main function (which cannot be edited) is merely calling the function printStarts(n). Also, not supposed to use any loops in the function, only recursive calls to the function.

Edit: this is a practice problem on CodeLab. Our lectures are completed, I'm merely doing practice questions offered on the site.

4. Apr 18, 2013

### Staff: Mentor

So you need one recursive function that prints a specified number of lines, and another recursive function that prints a star or newline character (i.e., your printStars function). The first function would call printStars for each line that it prints.

Going over what you wrote, since main calls printStars, you'll need to rewrite printStars so that it calls the function that actually prints the stars for one line. I would prefer to have main call something named printLines, and printLines calls printStars, but it looks like you're stuck with what's already in main.

Say there is this line in main:
printStars(5);

Inside printStars you need to call printLine(5), which should print an *, then call itself to print an *, and so on for 5 asterisks, after which it prints a newline character.

The next recursive call to printStars will print a line of 4 asterisks, and the next will print a line of 3 of them, and so on.

5. Apr 18, 2013

### DrZoidberg

You can make 2 functions

Code (Text):
void printLine(int n)
{
if (n > 0)
{
cout << '*';
printLine(n-1);
}
else cout << endl;
}

void printStars(int n)
{
if (n > 0)
{
printLine(n);
printStars(n-1);
}
}

6. Apr 18, 2013

### sandy.bridge

Okay! Wanted to see if it were possible with one recursive function, rather than two. Thanks!

7. Apr 19, 2013

### DrZoidberg

Of course it's possible with only one function but I wouldn't recommend it.

Code (Text):
void printStars(int n, int m)
{
if(m < n)
{
cout << '*';
printStars(n, m+1);
}
else if (n > 0)
{
cout << endl;
printStars(n-1, 0);
}
}
And then you call the function with
printStars(5,0);

8. Apr 19, 2013

### sandy.bridge

Alright, so I have this recursive function working properly in eclipse (to my knowledge,) however, CodeLab is telling me that my input is wrong. Perhaps one of you can see where.

Code (Text):
#include <iostream>
using namespace std;

void printStars(int n)
{
if(n > 0)
{
cout << '*';
return printStars(n - 1);
}
cout << endl;
return;
}

void printTriangle(int n)
{
if(n > 0)
{
printStars(n);
return printTriangle(n - 1);
}
return;
}

int main() {
printTriangle(5);
return 0;
}

This is my code in eclipse. Console produces:
*****
****
***
**
*

Here is what codelab asks of me: Assume the availability of a function named printStars that can be passed a non-negative integer n and print a line of asterisks. Write a function named printTriangle that receives a non-negative integer n and prints a triangle of asterisks as follows: first a line of n asterisks, followed by a line of n-1 asterisks, and then a line of n-2 asterisks, and so on. For example, if the function received 5 it would print:
* * * * *
* * * *
* * *
* *
*

The function must not use a loop of any kind (for, while, do-while) to accomplish its job. The function should invoke printStars to accomplish the task of printing a single line.

From this, I deduce printStars is already existent, and all I really need is a single recursive function to invoke printStars n times. The code I submitted is:
Code (Text):
void printTriangle(int n)
{
if(n > 0)
{
printStars(n);
return printTriangle(n - 1);
}
return;
}
CodeLab is telling me that its wrong. Ideas?

9. Apr 19, 2013

### Staff: Mentor

I see two things.
1. The main function you show doesn't agree with what you said in post #3.
I'm sure you meant printStars(n). The code in post #8 shows printTriangle in main.
2. A void function does not return a value, so it should not have startements such as "return <whatever>". You can have a bare return statement (i.e., return;). Instead of writing, say,
Code (Text):
return printStars(n - 1);
just write
Code (Text):
printStars(n - 1);
I'm not certain that this is your problem, but at the least, it's flaky and should be changed.

10. Apr 19, 2013

### sandy.bridge

The question word for word on CodeLab is:
Assume the availability of a function named printStars that can be passed a non-negative integer n and print a line of asterisks. Write a function named printTriangle that receives a non-negative integer n and prints a triangle of asterisks as follows: first a line of n asterisks, followed by a line of n-1 asterisks, and then a line of n-2 asterisks, and so on. For example, if the function received 5 it would print:
* * * * *
* * * *
* * *
* *
*

The function must not use a loop of any kind (for, while, do-while) to accomplish its job. The function should invoke printStars to accomplish the task of printing a single line.

From this, I deduce that printStars already exists, and all I have to input on CodeLab is the printTriangle function, which calls on printStars to print a single line of n, then n-1, etc, stars. The function that i input on codelab is
Code (Text):
void printTriangle(int n)
{
if(n > 0)
{
printStars(n);
printTriangle(n - 1);
}
return;
}

EDIT: Figured it out; was missing the end line in between the function calls. ie:

Code (Text):
void printTriangle(int n)
{
if(n > 0)
{
printStars(n);
cout << endl;
printTriangle(n - 1);
}
return;
}

Last edited: Apr 19, 2013
11. Apr 21, 2013

### sandy.bridge

Hey guys. Looking for a little bit of advice on two simple recursive functions. I have them operating properly, but I have done so utilizing universal constants, which is something I have been told we should not use. Can any of you recommend how I can avoid using them in my code? Thanks in advance!

First recursive function returns a summation of all the elements in an array. One parameter is an array, the other is the size of the array. Here is my code(which functions properly):

Code (Text):
int total = 0;
int sum(int array[], int size)
{

if (size > 0)
{
total += array[size-1];
sum(array, size-1);
}
}

The next recursive function has a positive integer n as the paramter. It prints n stars, followed by n dollar signs, all on the same line. For example, printStarBucks(4) results in console displaying ****. My code works properly, but I want to avoid universal constants, which I couldn't seem to figure out. Here is my code:
Code (Text):
int count = 0;
void printStarBucks(int N)
{
if(N > 0)
{
cout << '*';
count--;
printStarBucks(n-1);

}
if (count < 0)
{
cout << '$'; count++; printStarBucks(count); } return; 12. Apr 22, 2013 ### sandy.bridge Sorry to bump, tomorrow is my final so if anyone can help me with my technique on those last two recursive functions I would greatly appreciate it! 13. Apr 22, 2013 ### cepheid Staff Emeritus If by "universal constants", you mean global variables, then I agree that these can and should be avoided. What's wrong with something like this: Code (Text): int sum(int* array, int size, int total) { if (size > 0) { total += (array[size-1] + sum(array, size-1, total)); } return total; } Here, total is a variable local to the sum function, and is passed to it as an argument. Then in your main program, you would have something like this to call the function: Code (Text): result = sum(array, size, 0); With result, array, and size all defined appropriately, of course. Notice how 0 is passed as the initial value for total. 14. Apr 22, 2013 ### cepheid Staff Emeritus For the printStarBucks function, you don't need a separate counter, because n is your counter. Also, you don't need two separate instances of printStarBucks(n-1) within the function. There should only be one call. Hint: when each function returns, it returns back to the function that called it, which can then do something else. 15. Apr 22, 2013 ### sandy.bridge Hey! Thanks for the response. The issue that I have with printStarBucks occurs when N gets to zero. I can print N stars, but once I count down N each recursive step, by the time I go to start printing the '$', N is already zero. I can't say if(N < 1) because then the function repeats infinitely.

16. Apr 22, 2013

### cepheid

Staff Emeritus
Again, as each function returns, it returns to the function that called it, so you get another n iterations for free, if you just do the prints statements in the right order.

17. Apr 22, 2013

### sandy.bridge

Perfect, thanks!