Ряд Фибоначчи в С++: управление достигает конца непустой функции

Предположительно функция factorial должна возвращать n * factorial(n-1) для n > 0.

x=(factorial(n)*factorial(n-1)) следует читать x = n * factorial(n-1)

Изменять

else if (n==1)
        x=1;

to

else if (n==1)
        return 1;

Тогда fib() должно работать для всех неотрицательных чисел. Если вы хотите упростить его и заставить работать для всех чисел, сделайте что-то вроде:

int fib(int n) {
    if(n<=1) {
        cout << "zero reached \n";
        return 1;
    } else {
        return fib(n-1)+fib(n-2);
    }
}

«Управление достигает конца непустой функции»

Это предупреждение времени компиляции (которое можно рассматривать как ошибку с соответствующими флагами компилятора). Это означает, что вы объявили свою функцию не-void (в данном случае int), и все же есть путь через вашу функцию, для которого нет return (в данном случае if (n == 1)).

Одна из причин, по которой некоторые программисты предпочитают иметь ровно один оператор return для каждой функции, в самой последней строке функции...

    return x;
}

... заключается в том, что легко увидеть, что их функции возвращаются надлежащим образом. Это также может быть достигнуто за счет очень коротких функций.

Вы также должны проверить свою логику в своей реализации factorial(), у вас там бесконечная рекурсия.

Во втором базовом случае (n == 1) вы никогда не return x; или не возвращаете 1;

Раздел else вашей функции factorial() начинается:

    x=(factorial(n)*factorial(n-1));

Это приводит к бесконечной рекурсии. Должен быть:

    x=(n*factorial(n-1));

Иногда ваш компилятор не может сделать вывод, что ваша функция на самом деле не имеет отсутствия пропущенного возврата. В таких случаях существует несколько решений:

Предполагать

if (foo == 0) {
    return bar;
} else {
    return frob;
}

Реструктурируйте свой код

if (foo == 0) {
    return bar;
}
return frob;

Это хорошо работает, если вы можете интерпретировать оператор if как своего рода брандмауэр или предварительное условие.

прервать()

(см. комментарий Дэвида Родригеса.)

if (foo == 0) {
    return bar;
} else {
    return frob;
}
abort(); return -1; // unreachable

Соответственно вернуть что-то другое. Комментарий сообщает коллегам-программистам и вам самим, почему это здесь.

бросать

#include <stdexcept>

if (foo == 0) {
    return bar;
} else {
    return frob;
}

throw std::runtime_error ("impossible");

Не контрмера: единая точка выхода функции

Не возвращайтесь к одному возврату для каждой функции, также известному как точка выхода с одной функцией. обходной путь. Это устарело в C++, потому что вы почти никогда не знаете, где функция выйдет:

void foo(int&);

int bar () {
    int ret = -1;
    foo (ret);
    return ret;
}

Выглядит красиво и похоже на SFEP, но реверс-инжиниринг стороннего libfoo показывает:

void foo (int &) {
    if (rand()%2) throw ":P";
}

Кроме того, это может означать ненужную потерю производительности:

Frob bar ()
{
    Frob ret;
    if (...) ret = ...;
    ...
    if (...) ret = ...;
    else if (...) ret = ...;
    return ret;
}

так как:

class Frob { char c[1024]; }; // copy lots of data upon copy

Кроме того, каждая изменяемая переменная увеличивает цикломатическую сложность вашего кода. Это означает больше кода и больше состояния для тестирования и проверки, что, в свою очередь, означает, что вы высасываете больше состояния из мозга сопровождающего, что, в свою очередь, означает снижение качества мозга сопровождающего.

И последнее, что не менее важно: некоторые классы не имеют конструкции по умолчанию, и вам придется писать действительно фиктивный код, если это вообще возможно:

File mogrify() {
    File f ("/dev/random"); // need bogus init
    ...
}

Не делай это.

В операторах if-else нет ничего плохого. Код C++, применяющий их, похож на код других языков. Чтобы подчеркнуть выразительность C++, можно написать для факториала (например):

int factorial (int n) {return (n > 1) ? n * факториал (n - 1): 1;}

Эта иллюстрация с использованием «настоящего» условного оператора C/C++ ?: и других приведенных выше предложений не обеспечивает производительности. Потребуется принять меры против переполнения заполнителя (int или unsigned int) для результата и с рекурсивными решениями, переполняющими стек вызовов. Ясно, что максимальное n для факториала может быть вычислено заранее и служит для защиты от «плохих входов». Однако это можно сделать и на других уровнях косвенности, контролирующих n, поступающих в функцию factorial. Приведенная выше версия возвращает 1 для любого отрицательного n. Использование unsigned int предотвратило бы обработку отрицательных входных данных. Однако это не предотвратит возможную конверсионную ситуацию, созданную пользователем. Таким образом, также могут быть желательны меры против негативного воздействия.

Пока автор спрашивает, что технически не так с рекурсивной функцией, вычисляющей числа Фибоначчи, я хотел бы заметить, что изложенная выше рекурсивная функция решит задачу за время, экспоненциально растущее с n. Я не хочу препятствовать созданию из него идеального C++. Однако известно, что задача может быть вычислена быстрее. Это менее важно для малых n. Вам нужно будет обновить знания об умножении матриц, чтобы понять объяснение. Рассмотрим оценку степеней матрицы:

power n = 1  | 1 1 |
             | 1 0 | = M^1

power n = 2  | 1 1 |   | 1 1 |   | 2 1 |
             | 1 0 | * | 1 0 | = | 1 1 | = M^2

power n = 3  | 2 1 |   | 1 1 |   | 3 2 |
             | 1 1 | * | 1 0 | = | 2 1 | = M^3

power n = 4  | 3 2 |   | 1 1 |   | 5 3 |
             | 2 1 | * | 1 0 | = | 3 2 | = M^4

Вы видите, что матричные элементы результата напоминают числа Фибоначчи? Продолжать

power n = 5  | 5 3 |   | 1 1 |   | 8 5 |
             | 3 2 | * | 1 0 | = | 5 3 | = M^5

Ваша догадка верна (это доказывается математической индукцией, попробуйте или просто используйте)

power n      | 1 1 |^n         | F(n + 1) F(n)     |
             | 1 0 |   = M^n * | F(n)     F(n - 1) |

При перемножении матриц применяйте хотя бы так называемое «возведение в степень возведением в степень». Просто напомнить:

      if n is odd (n % 2 != 0), then M * (M^2)^((n - 1) / 2)
M^n = 
      if n is even (n % 2 == 0), then (M^2)^(n/2)

Без этого ваша реализация получит временные свойства итеративной процедуры (что все же лучше, чем экспоненциальный рост). Добавьте свой прекрасный C++, и это даст достойный результат. Однако, поскольку нет предела совершенству, это тоже можно улучшить. В частности, для чисел Фибоначчи существует так называемое «быстрое удвоение». Это будет иметь те же асимптотические свойства, но с лучшим временным коэффициентом для зависимости от времени. Когда кто-то говорит O (N) или O (N ^ 2), фактические постоянные коэффициенты будут определять дальнейшие различия. Один O(N) может быть еще лучше, чем другой O(n).