1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive function

  1. Apr 18, 2013 #1
    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. jcsd
  3. Apr 18, 2013 #2

    Mark44

    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.
     
  4. Apr 18, 2013 #3
    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.
     
  5. Apr 18, 2013 #4

    Mark44

    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.
     
  6. Apr 18, 2013 #5
    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);
        }
    }
     
  7. Apr 18, 2013 #6
    Okay! Wanted to see if it were possible with one recursive function, rather than two. Thanks!
     
  8. Apr 19, 2013 #7
    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);
     
  9. Apr 19, 2013 #8
    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?
     
  10. Apr 19, 2013 #9

    Mark44

    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.
     
  11. Apr 19, 2013 #10
    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
  12. Apr 21, 2013 #11
    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);
        }
        return total;
    }

    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;
     
     
  13. Apr 22, 2013 #12
    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!
     
  14. Apr 22, 2013 #13

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  15. Apr 22, 2013 #14

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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. :wink:
     
  16. Apr 22, 2013 #15
    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.
     
  17. Apr 22, 2013 #16

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  18. Apr 22, 2013 #17
    Perfect, thanks!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted