How can I trace recursion in C programming?

Question

I was trying to trace the recursion. In my logic answer should be 30, but the answer is 36. My question is how to trace this recursion?

#include<stdio.h>
int fun(int n)
{
    int static x=0;
    if(n>=0)
    {
        x=x+1;
        return(fun(n-1)+x);
    }
    return 0;
}

int main()
{
    int a=5;
    printf("%d",fun(a));    
}

You can run your program line by line in a [debugger](https://stackoverflow.com/q/25385173/12149471) while monitoring the [call stack](https://en.wikipedia.org/wiki/Call_stack) and the values of all variables. — Andreas Wenzel, Aug 01 '22 at 15:07
How would you trace a non-recursive program? In other words, what's your actual question? I feel like recursion isn't the real problem here. — Mad Physicist, Aug 01 '22 at 15:08

Ted Lyngmo · Answer 1 · 2022-08-01T15:29:15.177

If you are not used to using a debugger, it's probably a good time to start using one.

Until then, you could add printouts to see what your program is doing:

#include <stdio.h>

int fun(int n) {
    printf("n=%d\n", n);
    int static x = 0;
    if (n >= 0) {
        x = x + 1;        
        int res = fun(n - 1);
        printf("returning fun(%d)\t%d + %d = %d\n", n - 1, res, x, res + x);
        return res + x;
    }
    printf("termination point reached, x = %d\n", x);
    return 0;
}

int main() {
    int a = 5;
    printf("%d\n", fun(a));
}

Output:

n=5
n=4
n=3
n=2
n=1
n=0
n=-1
termination point reached, x = 6
returning fun(-1)   0 + 6 = 6
returning fun(0)    6 + 6 = 12
returning fun(1)    12 + 6 = 18
returning fun(2)    18 + 6 = 24
returning fun(3)    24 + 6 = 30
returning fun(4)    30 + 6 = 36
36

Vlad from Moscow · Answer 2 · 2022-08-01T16:11:34.620

Your function has undefined behavior because evaluations of the operands in the addition expression in the return statement

return(fun(n-1)+x);

are unsequenced. That is the value of x in the first call of the function can be evaluated before the next recursive call of the function. In this case x will be equal to 1. If the value of x will be evaluated after the next recursive call of the function it can have another value because the variable x has static storage duration.

From the C Standard (6.5 Expressions)

2 If a side effect on a scalar object is unsequenced relative to either a different side effect on the same scalar object or a value computation using the value of the same scalar object, the behavior is undefined. If there are multiple allowable orderings of the subexpressions of an expression, the behavior is undefined if such an unsequenced side effect occurs in any of the orderings.

So in different compilers you can get different results depending on how the compilers generate the object code.

How can I trace recursion in C programming?

2 Answers2