Chapter: Divide and Conquer

Printing

• a row of 10 *s: **********
• a row of 7 &s: &&&&&&&
• a row of 8 .s: ........

Print a row of n Xs, where n is a non-negative integer and X is a character

To solve such a problem in C we need to write code implementing

void printrow(int n, char c)
/* Print a row consisting of n copies of the character c */

n copies of c can be considered to be a "hard" problem worthy of subdivision. How can we subdivide it?

Easy:

  printf("%c", c");  /* Print one copy of c */
  /* print n-1 copies of c */

But then how can we solve the problem of printing n-1 copies of c?

Well, it's a simpler version of our "original" hard problem. The function call to print n-1 copies of c is simply printrow(n-1, c). And yes, the printrow function is what we're in the process of writing! This is the essence of using recursion as a very important step in producing a divide-conquer-glue solution to a problem.

one.c contains the entire finished code to solve this problem, together with a main method that test it. Copy it now, save it on your own computer as one.c, compile it with gcc -o one one.c and test it by running ./one.

Q. 1

Did you notice how we terminate this recursion? Can you identify the base case and how it is handled?

Now over to you. Now that we have solved the problem of printing n copies of a character c on one line, let's use that solution to help us solve a harder problem.

Exercise 1

printTriangle(5,'5'); produces

55555
5555
555
55
5

and printTriangle(7,'*'); produces

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

Save your code in a file called ex1.c in your handin folder. Use the following main function to test your code, and include it in your ex1.c file:

int main() {
  printTriangle(5,'5');
  printTriangle(7,'7');
  printTriangle(7,'!');
  printTriangle(0, '*');
}