I want to print a star pattern using recursion. I went with this method, but I don't know how this program works even though it has some flawed logic. For this particular program can someone help me understand why in the star()
function the input value starts to increase even if no such condition is given in the code?
#include <stdio.h>
int star(int n) {
if (n > 1) {
star(n - 1);
}
printf("* ");
}
int logic(int n) {
if (n > 1) {
logic(n - 1);
}
star(n);
printf("\n");
}
int main() {
int n = 3;
logic(n);
return 0;
}
For n = 3
, obtained pattern is.
*
**
***
Yes the program runs correctly somehow but I am finding it difficult to trace the logic flow.
Let's analyse the behavior of star
and logic
:
int star(int n) {
if (n > 1) {
star(n - 1);
}
printf("* ");
}
int
return type but does not return anything. Make it void
instead1
or less, it just outputs a *
followed by a space.*
and a space.3
are:
star(2)
, which itself:
star(1)
, which outputs *
*
*
* * *
int logic(int n) {
if (n > 1) {
logic(n - 1);
}
star(n);
printf("\n");
}
The logic()
function follows the same steps but instead of printing *
at each step, it calls star(n)
, which outputs a line of n
stars, and outputs a newline:
Note that both logic
and star
should not output anything for an argument of 0
or negative and it would be cleaner to avoid the trailing space at the end of each line.
Here are modified versions:
// print a line of stars with a trailing newline
void star(int n) {
if (n > 0) {
printf("*");
if (n > 1) {
printf(" ");
} else {
printf("\n");
}
star(n - 1);
}
}
void logic(int n) {
if (n > 0) {
logic(n - 1);
star(n);
}
}
The above star
function uses terminal recursion, ie: the recursive call is the last statement in the function so the compiler can turn it into a jump, avoiding recursive calls and thus preventing potential Stack Overflow for large arguments. The logic
function does not, so this potential problem is still present.
Note that the star
function can be simplified to avoid calling printf
which is a complex function, and minimize the use of if
statements, if you are allowed to use the ternary operator. Yet the compiler might be able to operate this optimisation directly:
void star(int n) {
if (n > 0) {
putchar('*');
putchar(n > 1 ? ' ' : '\n');
star(n - 1);
}
}
Recursion is taught early in CS classes for academic reasons, to make students think in terms of functional programming instead of loops and state modifications. This explains why you are only allowed to use if
and specifically not for
or while
. For illustration, here is a more idiomatic way to implement these functions in C, that avoids the potential Stack Overflow issue:
void star(int n) {
while (n-- > 0) {
putchar('*');
putchar(n ? ' ' : '\n');
}
}
void logic(int n) {
for (int i = 1; i <= n; i++) {
star(i);
}
}