unable to understand how recursion works

Question

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?

Properly indent the code, explain in detail what you expect, why you expect that, what you observe, etc. For example you are missing a `return` statement in the `if` part. Apart from that: there are tons of tutorials available explaining recursion. — luk2302, Mar 08 '22 at 10:19
Both cause undefined behaviour due to the missing `return` value when `i > 1`. Recursive functions work *exactly* like non-recursive functions. — molbdnilo, Mar 08 '22 at 10:20
Ignoring the undefinedness for a moment, imagine that `fun(i-1)` actually says `other_fun(i-1)`. Then you have "print `i`, then do whatever `other_fun(i-1)` does, then print `i` again, then exit without a return value", and you have no problems understanding the flow of that. — molbdnilo, Mar 08 '22 at 10:27
The best way to understand the flow control of a program is to run it line by line in a [debugger](https://stackoverflow.com/q/25385173/12149471). — Andreas Wenzel, Mar 08 '22 at 10:40

score 0 · Answer 1 · answered Mar 09 '22 at 21:47

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;
    }
}

molbdnilo · Answer 2 · 2022-03-08T12:44:04.300

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).

unable to understand how recursion works

2 Answers2