Факториал с использованием рекурсии (обратный путь против нового подхода) - PullRequest
Новая
       13

Факториал с использованием рекурсии (обратный путь против нового подхода)

0 голосов
/ 08 апреля 2019

Я пытаюсь научиться рекурсии. для начальной проблемы этого, который вычисляет факториал числа, я сделал это, используя два метода. первый из них - обычный обычный подход. второй я пытался сделать что-то другое. во втором я возвращаю значение n в конце, а не получаю начальное значение, как в первом, который использует возврат. мой вопрос заключается в том, что мой подход имеет какие-либо преимущества перед возвратом если спросить, какой из них будет лучшим решением?

// первый, 

ll factorial(int n)
{
   if(n==1)
     return 1 ;
   return n*factorial(n-1) ;
}
int main()
{
   factorial(25) ;
   return 0 ;
}

// второй - 

ll fact(ll i,ll n)
{    
   if(i==0)return n ;
     n=(n*i) 
   i--;
   n=fact(i,n);
}
int main()
{   
   int n ;
   cin>>n ;
   cout<<fact(n,1) ;
   return 0 ;
}

// ll long long int

1 Ответ

1 голос
/ 26 апреля 2019

Прежде всего я хочу отметить, что преждевременная оптимизация за счет читабельности почти всегда является ошибкой, особенно когда потребность в оптимизации проистекает из интуиции, а не из измерений.

"Мыследует забыть о малой эффективности, скажем, в 97% случаев: преждевременная оптимизация - корень всего зла. Но мы не должны упускать наши возможности в эти критические 3% », - Дональд Кнут

Носкажем, в этом случае мы заботимся о 3%, потому что все, что когда-либо делает наша программа, вычисляет много факториалов.Короче говоря: Вы никогда не будете умнее компилятора.

Если это кажется немного сумасшедшим, то это определенно относится к вам, и вам следует перестать думать о «микроуправлении / оптимизации вашего кода»,Если вы очень опытный программист на C ++, это все равно будет применяться к вам в большинстве случаев, но вы поймете, что можете помочь вашему компилятору.

Чтобы подкрепить это некоторым фактом, мы можем скомпилировать код (с автоматической оптимизацией) и (примерно) сравните вывод сборки.Я буду использовать замечательный сайт godbolt.org

Не смущайтесь сумасшедшим кодом ассемблера, нам не нужно его понимать.Но мы можем видеть, что оба метода

  1. в основном имеют одинаковую длину при компиляции, так как код ассемблера
  2. содержит почти одинаковые инструкции

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

...