Factorial using recursion(backtracking vs a new approach)

Question

I am trying to learn recursion. for the starting problem of it , which is calculating factorial of a number I have accomplished it using two methods. the first one being the normal usual approach. the second one i have tried to do something different. in the second one i return the value of n at the end rather than getting the starting value as in the first one which uses backtracking. my question is that does my approach has any advantages over backtracking? if asked to chose which one would be a better solution?

//first one is ,

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

// second one is ,

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 is long long int

You should define `better` in term of some metric. Does better mean faster or more readable or using less memory? Then you should measure those metric and deduce your answer from the data. — Davide Spataro, Apr 08 '19 at 15:06
Wich one would be better in terms of computing load? Faster? Does my approach make any difference first of all? — Saswat Panda, Apr 08 '19 at 16:08
Try to post this kind of question on https://codereview.stackexchange.com/. — Davide Spataro, Apr 09 '19 at 08:00
The second one does not compile since there is a missing `;`, and you do not return `n` at the end so you probably won't get what you expect. — Holt, Apr 09 '19 at 15:26
The second one is [tail recursive](https://stackoverflow.com/questions/33923/what-is-tail-recursion), which is "theoretically" better because you should not need to stack each call, but in practice for such small examples, both code are going to be converted to iteration versions with `-O1`. — Holt, Apr 09 '19 at 15:28
Wow , good to hear that, I now love recursion more. thanks a lot — Saswat Panda, Apr 10 '19 at 19:08

score 1 · Answer 1 · answered Apr 26 '19 at 17:59

First of all I want to point out that premature optimization at the expense of readibility is almost always a mistake, especially when the need for optimization comes from intuition and not from measurements.

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%" - Donald Knuth

But let's say we care about the 3% in this case, because all our program ever does is compute lots of factorials. To keep it short: You will never be smarter than the compiler.

If this seems slightly crazy then this definitely applies to you and you should stop thinking about 'micromanaging/optimizing your code'. If you are a very skilled C++ programmer this will still apply to you in most cases, but you will recognize the opportunities to help your compiler out.

To back this up with some fact, we can compile the code (with automatic optimization) and (roughly) compare the assembly output. I will use the wonderful website godbolt.org

Don't be discouraged by the crazy assembler code, we don't need to understand it. But we can see that both methods

are basically the same length when compiled as assembler code
contain almost the same instructions

So to recap, readability should be your number one priority. In case a speed measurement shows that this one part of your code really is a big performance problem, really think about if you can make a change that structurally improves the algorithm (i.e. by decreasing the complexity). Otherwise your compiler will take care of it for you.

Also consider reading the fairly concise paragraph on when to optimize on Wikipedia: https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize — Romeo Valentin, Apr 26 '19 at 18:01

Factorial using recursion(backtracking vs a new approach)

1 Answers1