Как обнаружить корневой рекурсивный вызов?
Скажите, что мы пишем простую рекурсивную функцию fib(n) это вычисляет энное Число Фибоначчи. Теперь, мы хотим, чтобы функция распечатала то энное число. Поскольку та же функция вызывается неоднократно, должно быть условие, которое позволяет только корневому вызову печатать. Вопрос: как записать это условие, не передавая дополнительных аргументов, или с помощью глобальных / статических переменных.
Так, мы имеем дело с чем-то вроде этого:
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;
}
Я думал, что корневой вызов отличается от всех детей путем возврата к другой вызывающей стороне, а именно, основной метод в этом примере. Я хотел знать, возможно ли использовать это свойство для записи условия и как.
Обновление: обратите внимание на то, что это - изобретенный пример, который только служит для представления идеи. Это должно быть ясно из тегов. Я не ищу стандартные решения.Спасибо.
5 ответов
Я бы сделал это с помощью вспомогательной функции:
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;
}
В качестве альтернативы вы могли бы написать это так (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;
}
Здесь идет хитрый путь, хотя я не уверен, что оно того стоит :):
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;
}
Но функция требует, чтобы вы на самом деле не имели в виду отправку отрицательного значения :).
Корневой рекурсивный вызов - это точка, в которой вызывается рекурсия, а именно вызов в main . Учитывая это, вы можете немного переписать свой код (примерно так):
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;
}
Я думаю, вы могли бы получить адрес возврата из стека и как-нибудь сравнить его с адресом функции fib. Адрес возврата должен быть где-то рядом с параметром n, если n не передается в каком-либо регистре, но в стандартном C этого не должно быть. Вам просто нужно знать, где находится адрес возврата относительно параметра.
Если вы действительно хотите спросить, имеет ли C доступ к некоторому API, который позволяет коду в теле функции узнать, откуда была вызвана выполняемая функция, ответ будет № .