CODEWITHSUNDEEP
crecursionprintffunction-definition
user13387446
user13387446

Reputation:

Stacks and Recursion in C

#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

Upvotes: 0

Views: 138

Answers (5)

Vlad from Moscow
Vlad from Moscow

Reputation: 310990

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.

Upvotes: 2

Lundin
Lundin

Reputation: 213862

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.

Upvotes: 0

chqrlie
chqrlie

Reputation: 144770

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.

Upvotes: 0

paradx
paradx

Reputation: 74

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%10 value and so on.

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

Upvotes: 1

0___________
0___________

Reputation: 67546

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.

Upvotes: 0

Related Questions