cfunctionif-statementrecursion

In this pattern program, why does value start to increase in star()?


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.


Solution

  • Let's analyse the behavior of star and logic:

    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");
    }
    

    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);
        }
    }