Как обнаружить корневой рекурсивный вызов?

Question

Допустим, мы пишем простую рекурсивную функцию fib(n), которая вычисляет n-е число Фибоначчи. Теперь мы хотим, чтобы функция напечатала это 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;
}

Я думал, что корневой вызов отличается от всех дочерних элементов, возвращаясь к другому вызывающему, а именно к основному методу в этом примере. Я хотел знать, возможно ли использовать это свойство для записи условия и как.

Обновление: обратите внимание, что это надуманный пример, который служит только для представления идеи. Это должно быть ясно из тегов. Я не ищу стандартных решений. Спасибо.

Answer 1

Я бы сделал это с помощью вспомогательной функции:

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

Answer 2

Корневой рекурсивный вызов - это точка, из которой вызывается рекурсия, а именно вызов в 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;
}

Answer 3

Если вы действительно хотите спросить, имеет ли C доступ к какому-либо API, который позволяет коду в теле функции выяснить, откуда была вызвана выполняемая функция, ответ будет no .

Answer 4

Вот хитрый путь, хотя я не уверен, что оно того стоит :):

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

Но функция требует, чтобы вы не имели в виду посылку отрицательного значения :).

Answer 5

Я думаю, вы можете получить адрес возврата из стека и сравнить его как-то с адресом функции fib. Адрес возврата должен быть где-то близко к параметру n, если только n не передан в некотором регистре, но в стандартном C это не должно быть. Вам просто нужно знать адрес возврата относительно параметра.