Факторная проблема, дающая неправильный вывод в c ++

Question

Пытаюсь написать факториальную задачу для моей учебной работы, но получаю неправильный вывод.Не понимаю, что я делаю не так.Вот мой код.

int fact(int number) {
    if(number == 0) {
           return 1;
        }
     return  fact_i(number, 1);
}

int fact_i(int curNumber, int sum) {
    if(curNumber == 1) {
        return sum;
    } else {
        return fact_i(curNumber - 1, sum);
    }
}

Answer 1

1. Вы никогда не умножаете sum на число, поэтому оно не может быть больше единицы.Рекурсия должна быть:

   return fact_i(curNumber - 1, curNumber * sum);
   

2. Обратите внимание, что в этом случае стремление к оптимизации хвостового вызова не имеет смысла.Хотя компиляторы C ++ Generall могут сделать это ( Какие компиляторы C ++, если таковые имеются, выполняют оптимизацию хвостовой рекурсии? ), вы не можете на это полагаться, поскольку она не указана, иВы будете переполнены int, прежде чем сможете достичь любого предела стека.

Answer 2

Правильный способ сделать хвостовой рекурсивный факториал таков:

int fact(int number) {
    if(number == 0) {
           return 1;
        }
     return  fact_i(number, 1);
}

int fact_i(int curNumber, int sum) {
    if(curNumber == 1) {
        return sum;
    } else {
        return fact_i(curNumber - 1, sum*curNumber);
    }
}

Вы пропустили умножение curNumber на sum в строке return fact_i(curNumber - 1, sum);

Answer 3

Проблема

Ошибка в строке

return fact_i(curNumber - 1, sum);

Это должно быть:

return curNumber*fact_i(curNumber - 1, sum);

Без этого результат никогда не будет накапливаться.Вы просто продолжаете 1 вверх по цепочке рекурсивных вызовов.

Дальнейшая очистка

Вы используете два условия завершения - одно, если fact, и другое в fact_i.Вы можете использовать только одно завершающее условие для упрощения кода.

int fact_i(int curNumber, int sum) {
    if(curNumber == 1) {
        return sum;
    }

    // No need for an else here.
    return fact_i(curNumber - 1, (curNumber-1)*sum);
}

int fact(int number) {
   return  fact_i(number, number);
}