CODEWITHSUNDEEP
crecursionstack
Ahmed Abdelkader
Ahmed Abdelkader

Reputation: 1735

How to detect the root recursive call?

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.

Upvotes: 5

Views: 1003

Answers (5)

Maciej Hehl
Maciej Hehl

Reputation: 7995

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.

Upvotes: 0

Blindy
Blindy

Reputation: 67449

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

Upvotes: 5

Feyyaz
Feyyaz

Reputation: 3206

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

Upvotes: 1

reinierpost
reinierpost

Reputation: 8601

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.

Upvotes: 1

fbrereto
fbrereto

Reputation: 35935

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

Upvotes: 5

Related Questions