A Recursive Exercise in C

20 07 2017

By Photo: RK812, Doll carved by Zvezdochkin, painted by Malyutin

Recently someone asked an interesting question at StackOverflow about using recursion  in the C Programming Language to achieve the same result as code relying on a loop structure.  The question pertained to outputting a geometric pattern.The original poster (OP)  implemented a solution now available here.  The example iteratively invokes two recursive functions..  At this point, let’s consider  the difference between the two primary ways of  having code repeatedly execute, namely iteration and recursion.  Simply put, iteration achieves this repetition by using a loop structure, such as a for, while or do while loop.  Recursion allows for the code to repeat every time a function calls itself .  While some may regard a loop structure as syntactic sugar, recursion offers the potential benefit of clarifing code; see here.

Before plunging into the code,  consider what the result should be, namely a display as follows:

    
          *
         ***
        *****
       *******
      *********

If one takes a moment or two to study the pattern a bit, one may  grasp more easily what the  code entails.  In order to produce the first row with the top star centered above the other rows, four blank spaces must precede that solitary star. The next row contains two extra stars and one fewer of the blank spaces. Each successive row follows the same pattern, until the last row which consists only of stars,  still following the pattern of two more than the previous row.

To achieve this outcome, the OP designed two functions, one to display blank spaces and another to output stars, each of which I’ve modified, as follows:

#include <stdio.h>
 /**
  * printBlank()
  * recursively display blank space
  *
 **/
void printBlank( int numRows ) {
    printf(" ");
    if( numRows > 1) {
        printBlank( numRows - 1 );
    }
}

printBlank() stops only when the conditional becomes false, i.e. numRows evaluates as equal to or less than one.  Note, whether the printf() statement precedes the if-conditional,  thereby aiding a developer’s  comprehension, or follows it, as in the OP’s code,  the generated output remains the same.  The brief comment preceding the function definition  clarifies its purpose.

/**
  * printStar()
  * recursively display star(s)
  *
 **/
void printStar(int numStars) {
    printf( "*" );
    if( numStars > 1 )
    {
        printStar( numStars - 1 );
    }
}

printStar() also stops when its if-condition turns false under the same circumstances, i.e. numStars is equal to or less than one.

The iterative code in the OP’s source code can actually be replaced with yet another recursive function, as follows:

int recurse(int maxRows, int minStars) {
    printBlank( maxRows-- );
    printStar( minStars );
    printf("\n");
    if ( maxRows < 1){
    	return 0;
    }
    else
    {
    	 recurse( maxRows, minStars + 2);
    }
}

All that remains is to  invoke recourse(), as follows:

int main(void) {
   int endRows = 5;
   int startStars = 1;
   recurse( endRows, startStars );}

See live demo.

This work is licensed under a Creative Commons License

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: