Stacks and Recursion in C-CodePudding

#include <stdio.h>

void fun(int a) {
    if (a > 0) {
        fun(a / 10);
        printf("%d", a % 10);
        fun(a / 10);
    }
}
int main() {
    fun(12345);
    return 0;
}

Here, as the function is calling itself at the start of the if block, shouldn't it print nothing, it will keep calling itself until the function argument becomes zero?

But instead, the output is 1213121412131215121312141213121

CodePudding user response：

shouldn't it print nothing, it will keep calling itself until the function argument becomes zero?

If I have understood correctly then you are right. The function will not output anything until a is equal to 0.

void fun(int a){
    if(a > 0){
        fun(a/10);   // calls itself.
        printf("%d",a % 10);
        //...

Thus for this number 12345 the first output will be the most significant digit 1.

As the function calls itself twice

void fun(int a){
    if(a > 0){
        fun(a/10);
        printf("%d",a % 10);
        fun(a/10);
    }
}

then for each digit of the number except the most significant digit the previous and next digits will be outputted twice on the left and on the right sides. For example

            1 2 1
        1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
and so on.

I used embedded spaces for make the output more clear.

CodePudding user response：

After the inner most function of the recursion has been finished (a>0) is evaluating to false it will execute the print statement and returns to the calling function. The caller will print it's a value and so on.

Not sure why you call fun(a/10) twice but this is why the output is printed twice.

CodePudding user response：

Yuo do not need the second call

void fun(int a)
{
    if(a)
    {
        fun(a/10);
        printf("%d", a % 10);
    }
}

https://godbolt.org/z/zWf64jjWe

Remember that it will not work for negative numbers.

CodePudding user response：

The function attempts to print the decimal conversion of a but the second recursive call produces extra output.

The function will indeed produce no output for values below 10, which might not be the expected behavior. Without the second recursive call the output would be 1234.

You should use this instead:

void fun(int a) {
    if (a >= 10)
        fun(a / 10);
    printf("%d", a % 10);
}

Note however that the above function only works for positive values.

CodePudding user response：

You can implement this is 3 different ways:

Either make the recursive call before you start printing. If so the printing starts from the deepest level of recursion. This is very inefficient but ensures that you get the expected order 1,2,3... Generally, a recursive function that doesn't have the recursive call at the very end is an incorrect solution to any problem.
Or make the recursive calls after you print. This would lead to everything getting printed backwards as you've currently written the function. However, a recursive function with the call at the end, so-called "tail call", can sometimes get optimized into nearly as efficient code as a loop. You could probably do this here too, if you come up with a different algorithm.
Or you can implement it as a loop. Super-fast, super-readable, no risk of excessive stacking, no overhead. This is the correct solution in some 99% of all cases and the correct solution in 100% of all cases a beginner might be facing.