How to detect the root recursive call?

Question

Say we're writing a simple recursive function fib(n) that calculates the nth Fibonacci number. Now, we want the function to print that nth number. As the same function is being called repeatedly, there has to be a condition that allows only the root call to print. The question is: how to write this condition without passing any additional arguments, or using global/static variables.

So, we're dealing with something like this:

int fib(int n) {
    if(n <= 0) return 0;
    int fn = 1;
    if(n > 2) fn = fib(n-2) + fib(n-1);
    if(???) cout << fn << endl;
    return fn;
}

int main() {
    fib(5);
    return 0;
}

I thought that the root call differs from all children by returning to a different caller, namely the main method in this example. I wanted to know whether it is possible to use this property to write the condition and how.

Update: please note that this is a contrived example that only serves to present the idea. This should be clear from the tags. I'm not looking for standard solutions. Thanks.

Answer 1

The root recursive call is the point the recursion is invoked, namely the invocation in main. Given that, you could rewrite your code slightly (something like this):

int fib(int n) {
    if(n <= 0) return 0;
    int fn = 1;
    if(n > 2) fn = fib(n-2) + fib(n-1);
    return fn;
}

int main() {
    cout << fib(5) << endl;
    return 0;
}

Answer 2

Here comes a tricky way, although i'm not sure that's worth it :):

int fib(int n) {
//    if(n <= 0) return 0;
    int isRoot;
    if ( n <= 0 ){
        isRoot = 1;
        n = -n;
    }
    else isRoot = 0;
    int fn = 1;
    if(n > 2) fn = fib(n-2) + fib(n-1);
    if(isRoot) cout << fn << endl;
    return fn;
}

int main() {
    fib(-5);
    return 0;
}

But, the function requires you not to really mean sending a negative value :).

Answer 3

The way I would do this is with a helper function:

int _fib(int n) {
    if(n <= 0) return 0;
    int fn = 1;
    if(n > 2) fn = _fib(n-2) + _fib(n-1);
    return fn;
}

int fib(int n) {
    int fn=_fib(n);
    cout << fn << endl;
    return fn;
}

Alternatively, you could write it like this (c++):

int fib(int n, bool f=true) {
    if(n <= 0) return 0;
    int fn = 1;
    if(n > 2) fn = fib(n-2, false) + fib(n-1, false);
    if(f) cout << fn << endl;
    return fn;
}

Answer 4

If you really mean to ask whether C has access to some sort of API that allows code in a function body to find out from where the executing function was called, the answer is no.

Answer 5

I think You could get the return address from the stack and compare it somehow with the address of the fib function. The return address should be somewhere close to the parameter n unless n is passed in some register, but in standard C it shouldn't. You just have to know where the return address is relative to the parameter.