What is really happening in this code?

Question

I have a code which includes a recursive function. I have wasted a lot of time on recursion but I still couldn't get it really:

#include<stdio.h>
void count(int);

int main()
{
    int x=10,z;
    count(x);
}

void count(int m)
{
    if(m>0)
        count(m-1);
    printf("%d",m);
}

When the 1st time count is called with argument as 10. it fulfills the condition and then here starts the recursive part. what happens really when a function calls itself? I don't get it. Please explain with reference to stacks.

Answer 1

next time it calls itself it has a smaller value

count(int m)
{
 if(m>0)
 count(m-1); // now it is calling the method "count" again, except m is one less
 printf("%d",m);
}

So first it will call count with 10, then it will call it with 9, then 8, then 7..... all the way until this if statement isn't true:

if(m>0)

What might be confusing you is the if statement only applies to the next line (printf isn't part of the if statement)

so you have:

count(int m)
    {
     if(m>0)
     {
         count(m-1); // now it is calling the method "count" again, except m is one less
     }
     printf("%d",m);
    }

So, the recursive calls will stop once m is not > 0, and then it will call the printf.

After it calls printf for when m is 0, then it will return from that 'count' call, (Back to where m was equal to 1), and then it will call the printf when m is 1, and then when m is 2, .....

So the output should be:

"0 1 2 3 4 5 6 7 8 9 10"

EDIT: In terms of a stack:

This is what the stack is doing:

count(10) // push count(10)

->

count(9) // push count(9)
count (10)

->

...

->

count(0) // push count(0)
count(1)
count(2)
count(3)
count(4)
count(5)
count(6)
count(7)
count(8)
count(9)
count(10)

-> (and then it starts printing and popping the method off the stack)

// pop count(0), and printf(0)
count(1)
count(2)
count(3)
count(4)
count(5)
count(6)
count(7)
count(8)
count(9)
count(10)

->

// pop count(1), and printf(1)
count(2)
count(3)
count(4)
count(5)
count(6)
count(7)
count(8)
count(9)
count(10)

->

...

->

// pop count(9), and printf(9)
count(10)

->

// pop count(10), and printf(10)

Answer 2

Each number refers to the line number.

#include<stdio.h>
count(int);
main()
{
1int x=10,z;
2count(x);
}  
count(int m)
{
3if(m>0)
4   count(m-1);
5printf("%d",m);
}

The execution happens like this(with x=3) -

line number|value of x

1 3

2 3

3 3

4 2

3 2

4 1

3 1

4 0

5 0

5 1

5 2

5 3

Numbers printed on the screen 0 1 2 3

Answer 3

While m is greater than 0, we call count. Here is a representation of the stack calls:

 count (m = 10)  
   count (m = 9)  
     count (m = 8)  
       count (m = 7)  
         count (m = 6)    
           count (m = 5)     
             count (m = 4)     
               count (m = 3)     
                 count (m = 2)     
                   count (m = 1)
                     count (m = 0)
                     printf 0
                   printf 1
                 printf 2
               printf 3
             printf 4
           printf 5
         printf 6
       printf 7
     printf 8
   printf 9
 printf 10

Answer 4

When a function is called the return address (of the next code to execute) is stored on the stack along with its current arguments. Once the function finishes the address and arguments are popped so the cpu will know where to continue its code execution.

Let's write the addresses of the function (for the purpose of this example only)

count(int m)
{
(address = 100)  if(m>0)
(address = 101)     count(m-1); // now it is calling the method "count" again, except m is one less
(address = 102)  printf("%d",m);
}

For m = 1:

The if is fullfield so we execute code at address 101 with m = 1. address 102 and m = 1 are pushed to the stack and the function is executed again from address 100 with m = 0. Since m = 0 we execute address 102 and printing 0 on console. The function ends and the last return address (102) and argument m = 1 are popped and the line at address 102 is executed printing 1 on the screen.

Answer 5

If you want a more specific answer, then you have to look into how compilers work. But generally speaking the compiler will create machine code for the function that includes a preamble, in this code enough memory is allocated on the stack (by decrementing a stack pointer) that a copy of the functions variables can be placed on the stack (we can store the state of the function).

The function will have values stored in registers and memory and these must be stored on the stack for each (recursive) call, otherwise the new call will overwrite the precious data!. So very basically the machine code looks like this (pseudo code)

//store m on the stack 
store m,stack_pntr+m_offset
//put input values in designated register
a0 = m
//allocate memory on the stack
stackPntr -= stack_size_of(count_vars)
//store return address in allocated register
//jump to the first instruction of count
.
.

By changing some data used for computation we can go back and read the same instructions again and get a different result. The abstraction of recursive function allows us to manipulate the data we want to change in a nice "call by value" way so that we don't overwrite it unintentionally.

This is done by the compiler when it stores the state of the calling function on the stack so we don't have to manually store it.

Answer 6

1. The function count is called with an integer argument of 10.
2. Since the function argument m which is 10 is greater than 0 the function count calls itself with an integer argument of m which is 10 minus 1 which equals 9.
3. Step 2 repeats with varying arguments (m-1) until m is not greater than 0 and which point the program prints the value of m.

The recursive function just modifies the parameter given to it and calls itself with that modified value until the desired result is returned (in this case m not being greater than 0).