unable to understand how recursion works-CodePudding

I am trying to understand recursion but stuck on a very basic concept. The following code

int fun(int i) {
    if(i>1) {
        printf("%d---\n",i);
        fun(i-1);
        
        printf("%d***\n",i);
    }
    else {
        return i;
    }
}

int main() {
    // Write C code here
    int i=fun(5);
    printf(">>%d",i);
    return 0;
}

which gives the output

5---
4---
3---
2---
2***
3***
4***
5***
>>5

but code

int fun(int i){
    if(i>1){
        //printf("%d---\n",i);
        fun(i-1);
        
        // printf("%d***\n",i);
    }
    else {
        return i;
    }
}

gives

>>1

can anyone please explain the flow control?

CodePudding user response：

It works exactly like this non-recursive version, i.e. "print something, then call a function, then print something else":

int fun1()
{
    return 1;
}

int fun2() {
    printf("%d---\n",2);
    fun1();
    printf("%d***\n",2);
}

int fun3() {
    printf("%d---\n",3);
    fun2();
    printf("%d***\n",3);
}

int fun4() {
    printf("%d---\n",4);
    fun3();
    printf("%d***\n",4);
}

int fun5() {
    printf("%d---\n",5);
    fun4();
    printf("%d***\n",5);
}

int main() {
    int i = fun5();
    printf(">>%d",i);
    return 0;
}

As you can see, most of the function calls fail to return a value, which leads to undefined behaviour.
This is why you see different end results, and decent compiler will warn about this situation.

What's happening in practice is probably that you're printing the most recent value returned from any function.
With the printing, that's the value returned from the last printf, which returned 5 (printf returns the number of characters written; add or remove characters to your second printf and observe what happens).

CodePudding user response：

Main issue may be that in the recursive case (i>1) your function returns no explicit value, so return value is just taken from the stack. Using compiler flag such as -Wall with gcc should highlight this. Try:

int fun(int i) {
    if(i>1) {
        printf("%d---\n",i);
        int ret = fun(i-1);
        
        printf("%d***\n",i);
        printf("%d   \n",ret);
        return ret;
    }
    else {
        return i;
    }
}