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