How to detect the root recursive call?
Posted
by ahmadabdolkader
on Stack Overflow
See other posts from Stack Overflow
or by ahmadabdolkader
Published on 2010-04-22T16:05:47Z
Indexed on
2010/04/22
16:13 UTC
Read the original article
Hit count: 204
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.
© Stack Overflow or respective owner