recursive function

[SHWOO]

I was given an assignment to write a recursive function to print a diamond comprised of astrisks (less the dashes) such as:

---*
--* *
-* * *
* * * *
-* * *
--* *
---*

The parameter is the number of astricks in the largest row. I have written the function which works fine but, I am lost when it comes to converting this function to a recursive function. Any help would be appreciated.

#include <iostream>
#include <iomanip>
using namespace std;



void diamond(int row);

int main()
{
    diamond(12);
}

void diamond(int row)
{

int spaces = row * 2;



    for (int i = 0; i <= row + 1; i++)
    {
        cout << setw(spaces);
        for (int j = 0 ; j < i - 1; j++)
            cout << "* ";
            cout << endl;
            --spaces;
    }    
         for (int i = 0; i < row; i++)
        {
            cout << setw(spaces+2);
            for (int j = row - 1 ; j > i; j--)
            cout << "* ";
            cout << endl;
            ++spaces;
        }
}

[mathematician]

Each time the function is called you need to print just one line of asterisks, and then recursively call the function to print the next line of asterisks. Obviously, with each call the line of sterisks will get longer, until the largest row is reached, and then you will need to set a flag (declared as a static variable) so that on subsequent calls the line starts getting shorter again. When, finally, the function is called to print a row 0 characters long, the function will do nothing except return, and all of the other recursive calls will then return.

Possibly, you will want to write a driver function to make the initial call to the recursive function.



Also, when testing a program containg a recursive function, bear in mind that you might overflow the stack if you make the maximum length of a row too large.

[Lazaro Claiborn]

I was given an assignment to write a recursive function to print a diamond comprised of astrisks (less the dashes) such as: ---* --* * -* * * * * * * -* * * --* * ---*

I'm not going to show you how do it but i'll show you a graphical way to think about it that might help you figure it out. The above ascii diagram has 7 lines. Each line would represent a one iterative call to say a function. It is defintely easier to do it without recursive functions. Assuming you know how recursive functions work ask yourself; For each call of the function to itself, how would it determine how many spaces and how many asterists to print? You might consider using, as mathematician had suggested, static variables - which will notify the functions to stop recursing, if the static variable is decremented each function call. You might consider just using parameters that are modified each recursive call instead of using the static way. Maybe you you'll use static variables for indicating how many recursive calls and how many spaces and asterists are to be printed per function call. Or, maybe, you can use the the static or parameter variable indicating the max amount of recursive calls to determine how many spaces and asterist should be printed. How about printing the spaces and asterists for the other half of the diamond upon return of the previous function call. How'd you do that? Here is an ascii example to clarify:

Call - Print

1. ___*
2. __**
3. _***
4. **** -All prints at this point might occur upon return
5. _***
6. __**
7. ___*

Just some ideas and angles of thinking that might help you.

Good luck with your assignment, LamaBot

[SHWOO]

So I was going to write a function to print "* " one astrick and a space and then depending on the parameter of the recursive function, which is an int to identify the number of astricks in the largest row. It would call the function to print "* " in the body of the recursive function depending on that parameter. If anyone can provide any more help I would greatful as I am still struggling on how to accomplish this task.

[Lazaro Claiborn]

So I was going to write a function to print "* " one astrick and a space and then depending on the parameter of the recursive function, which is an int to identify the number of astricks in the largest row. It would call the function to print "* " in the body of the recursive function depending on that parameter. If anyone can provide any more help I would greatful as I am still struggling on how to accomplish this task.

Here's an example of one way:

#include <iostream>
using namespace std;
int diamond(int aster) {
    if (aster==0) return 0;
    for (int i=0;i<4;i++)
        if (i>=aster)
          cout << "* ";
        else
          cout << " ";
    cout << endl;
    aster = diamond(--aster);
}
int main(void) {
    diamond(4);
return 0;
}

Here is a program that'll print only a half of a diamond. I'll leave the rest up to you. Also, there are other methods such as just using one for loop where you'd condition if aster would equal 4 and return, decrementing and using the return value to know how many space and asterits to print. There are other ways but this should give you an idea.

Good luck, LamaBot

[SHWOO]

So here is what I have so far. This Recursive function prints the top half of the diamond. For the bottom half should I create another recursive function to print the bottom half of the diamond and call it indirectly by the topDiamond function?

#include <iomanip>
#include <iostream>
#include "diamond.h"

using namespace std;

int diamond::botDiamond(int num)
{
    return 0;
}

int diamond::topDiamond(int num)
{
    static int x = 1;
        if (num == 0) return 0;
    
        cout << setw(num + 1);
        for (int i = 0; i < x; i++)
            cout << "* ";
        x++;
            cout << endl;
        if (num == 1)
        return botDiamond(num);

        return num = topDiamond(--num);
}

        diamond::diamond(int num)
        {
            if (num <= 0)
                cout << "Width of diamond must be greater than 0.";
            rows = num;
        }

        diamond::diamond()
        {
            rows = 10;
        }

[SHWOO]

I made a mistake here, I used a static int x in the topDiamond function but this doesn't work obviously. How do use a variable in a recursive function that is only static within the function?

[Narue]

>For the bottom half should I create another recursive function to print the
>bottom half of the diamond and call it indirectly by the topDiamond function?
You don't need to. Let's play a game. Get up from your computer and go to a nice empty spot in the room and start jumping up and down. I'll wait...

Did you have fun? :) Well, that jumping motion is how the entire process of recursion should look in your mind.

You start the recursion by jumping up. When you get as high as you can go, you reverse direction and come back down. Now, let's say you can jump really slowly and you want to count how many inches high you are. You jump up and say 1, 2, 3, 4, 5, 6, 7, 8, 9 and can't go any higher. So you start coming down and say 8, 7, 6, 5, 4, 3, 2, 1.

When you were counting up, that's the entry path of the recursive process. You're digging deeper and deeper into the recursion. When you couldn't get any higher, that's the base case for the recursion, the stopping case. But you're already deep into the recursive calls, so you still have to backtrack and come back out. That's the exit path of the recursive process, and you don't have to just let it happen silently. You can do actual work during the exit path (after the recursive call returns):

#include <stdio.h>

void jump ( int n )
{
  /* We can only jump 9 inches */
  if ( n < 9 ) {
    printf ( "Going up %d inches\n", n );
    jump ( n + 1 );
    printf ( "Going down %d inches\n", n );
  }
  else {
    printf ( "%d inches, can't go any higher\n", n );
  }
}

int main ( void )
{
  jump ( 1 );
  getchar();
  return 0;
}

Got it? Apply that to your diamond and see what happens. :)

[SHWOO]

I don't understand how that works. The Jump (n + 1) recursively calls Jump up to n =8 then why does going down keep getting called? there is no recursive call there

[Narue]

>I don't understand how that works.
Did you only read the code? I described it in detail and even took the time to come up with a description in clever layman's terms too.

>why does going down keep getting called? there is no recursive call there
That's because you're already in the recursion. It goes like this:

1
   2
      3
         4
            5
               6
                  7
                     8
                        9

You're already nine calls into the recursion. It doesn't just magically end, you have to go back out again:

1
   2
      3
         4
            5
               6
                  7
                     8
                        9
                     8
                  7
               6
            5
         4
      3
   2
1

Remember, a function has an entry and an exit, but recursion is just a long string of nested function calls.

[SHWOO]

Well that brings a whole new light to the subject. I didn't understand that the function stepped back out. I've been messing around with my code and I can't figure out where to put the loop to print the bottom half. I attempted to use your example code but that didn't seem to work for me. Any more hints for the newb?

[mathematician]

Print( int i, int incr, int stop )
{
     // if i equals stop value, return 
     // print i asterisks with spaces
     // Print( i + incr, incr, stop )      
     // return
}

PrintDiamond( int max )
{
       Print( 1, 1, max + 1 );  // print top half
       Print( max - 1, -1, 0 );  // print bottom half
       return;
}

[Narue]

>I attempted to use your example code but that didn't seem to work for me.
Not helpful. If it doesn't work, explain how it doesn't work. Did it simply not compile and run for you? Did it fail when you tried to make it print a diamond? What changes did you make? What result did you get? "It doesn't work" is the kind of useless reply that makes me want to smack people.

[SHWOO]

Well I used the jump function that you wrote and I tried to add the loop that prints the top half of the diamond where you have the going up code, then I put the code for the bottom half where you have the going down in inches code. No matter where I put the code for the bottom half of the diamond it doesn't print.

I tried it after the recursive call, I tried it before the recursive call, I tried it with a else after the recursive call. Every time I just get the first half of the diamond. I don't really understand where to put the loop for the bottom half so it will execute.

[Narue]

void print_n ( const char *s, int n )
{
  while ( --n >= 0 )
    printf ( "%s", s );
}

void jump ( int n )
{
  /* We can only jump 9 inches */
  if ( n < 9 ) {
    print_n ( "* ", n );
    putchar ( '\n' );

    jump ( n + 1 );

    print_n ( "* ", n );
    putchar ( '\n' );
  }
  else {
    print_n ( "* ", n );
    putchar ( '\n' );
  }
}

It works okay for me. The only part that's missing is the extra step of printing leading whitespace, and you can easily do that by adding a second argument to jump that counts down instead of up.