Question

Can explain how this function works?
#include <stdio.h>
int a(int n);
int main(void) {
printf("%d\n", a(4));
return 0;
}
int a(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return a( a(n-1) ) + a( n-a(n-1) );
}
}

Answer 1

"a" function - is a recursive function, each recursive call from return will call for additional four
calls of "a" function.
It would be continued till n will not reach to the 2 and base case return will turn the result.
Time of the execution is polynomial.
Result of execution would be 2, despite of amount of recursive calls part "a(a(n-1))" would return 1
and "a(n-a(n-1))" also return 1, in addition function return 2.