I'm confused by recursion in my "convert decimal to binary string" code

Question

void print_binary(int number)
{
    if (number){
        print_binary(number/2);
        putc((number % 2) ? '1' : '0', stdout);
    }
}
int main(void) {
    print_binary(8);
}

The code above returns "1000". But when I reverse the two lines in print_binary() and write it like this:

void print_binary(int number)
{
    if (number){
        putc((number % 2) ? '1' : '0', stdout);
        print_binary(number/2);
    }
}

the string is "0001".

I can't understand why this happens. Any explanation is appreciated. Thanks

Thanks for the link, but i'm still confused as how the output is reversed in order when the two lines in function are swapped. — Nam Hoang, May 23 '20 at 01:36

score 1 · Answer 1 · answered May 23 '20 at 01:38

1

In first code sample, execution goes like this:

print_binary(8/2)
    print_binary(4/2)
        print_binary(2/2)
            print_binary(1/2)    // 1/2 = 0 => this is terminating condition of recursion
                                 // stack windup from here
            putc((1 % 2) ? '1' : '0', stdout);   --> output 1
        putc((2 % 2) ? '1' : '0', stdout);  --> output 0
    putc((4 % 2) ? '1' : '0', stdout);   --> output 0
putc((8 % 2) ? '1' : '0', stdout);    --> output 0

Hence, the output is 1000.

In second code sample, execution goes like this:

putc((8 % 2) ? '1' : '0', stdout);    --> output 0
print_binary(8/2)

    putc((4 % 2) ? '1' : '0', stdout);   --> output 0
    print_binary(4/2)

        putc((2 % 2) ? '1' : '0', stdout);  --> output 0
        print_binary(2/2)

            putc((1 % 2) ? '1' : '0', stdout);   --> output 1
            print_binary(1/2)    // 1/2 = 0 => this is terminating condition of recursion
                                 // stack windup from here and nothing to do after last 
                                 // recursive call

Hence, the output is 0001.

answered May 23 '20 at 01:38

H.S.

11,654
2
15
32

wow thank you so much, very concise and easy to understand! So it seems like when I call my function, it saves the value in stack and then calculate with the stack windup. Let just say i'm not used to this yet haha, it seems so strange to me. Thanks again! – Nam Hoang May 23 '20 at 01:48
Great answer.If I wasn't lazy I would do the same as you did :))) – El. May 23 '20 at 01:52
@H.S. can i bother you some more? If the order goes 8->4->2->1 and then when putc() it goes 1->2->4->8 isn't that LIFO? I thought the stack was FIFO? – Nam Hoang May 23 '20 at 02:06
@NamHoang Seems you are confused with LIFO and FIFO. Read about [Stack data structure](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)). Also, you might be interested in reading about [Queue data structure](https://en.wikipedia.org/wiki/Queue_(abstract_data_type)). – H.S. May 23 '20 at 02:08
@H.S. wait what there was a reply right below saying stack is FIFO and another guy in the original post saying that stack is FIFO and give me this [link](https://stackoverflow.com/questions/5631447/how-recursion-works-in-c), turns out they're wrong now?? – Nam Hoang May 23 '20 at 02:21
@NamHoangI have seen many confused with LIFO/FIFO concept when using stack. Just think about the way it works. The element that goes last in the stack comes out first (LIFO). – H.S. May 23 '20 at 02:30

score 0 · Answer 2 · 2020-05-23T02:41:23.307

When you call a function, program puts the current address into stack memory where stack pointer points so it could come back when the execution ends and jumps to function's address. Stack is a LIFO (Last In First Out) structure so when you call a function, program finishes the instructions in the function than it turns back where it been. that's why putting order changes.

void print_binary(int number)
{
    if (number){
        putc((number % 2) ? '1' : '0', stdout);  // 1st instruction
        print_binary(number/2); // 2nd instruction
    }
}

The program works like this:

8%2 is 0 so print 0. // 1st instruction of 1st instance
A new function appeared. jump to it and push current address to stack. //2st instruction of 1st instance
4%2 is 0 so print 0. //1st instruction of 2nd instance
A new function appeared. jump to it and push current address to stack. //2nd instruction of 2nd instance
2%2 is 0 so print 0 // 1st instruction of 3rd instance
A new function appeared. jump to it and push current address to stack. //2nd instruction of 3rd instance
1%2 is 0 so print 1 //1st instruction of 4th instance
...

So the output is 0001

I understood the second one quite well, just had difficulty wondering how the first one operates. The comment below did save me! Thanks for your help too! — Nam Hoang, May 23 '20 at 01:53
You are right. The process that I mention on answer is LIFO behaviour as you noticed. Sorry for my dizziness I edited it. — , May 23 '20 at 02:40

I'm confused by recursion in my "convert decimal to binary string" code

2 Answers2