for-looprecursion

Difference between recursion and using for loop?


I can calculate factorial using recursion or for loop as below?

Recursive factorial

int recursiveFactorial(int n){
    if(n<0)
        return;
    if(n==0 || n==1)
        return 1;
    else
        return n*recursiveFactorial(n-1);
}

and using for loop

int forFacotrial(int n){
    if(n<0)
        return;
    if(n==0 || n==1)
        return 1;
    else{
       int fact=1;
       for(int i=2;i<=n;i++)
       {
             fact=fact*i;
       }
       return fact;
    }
}

What is the difference between the both is it in terms of performance? What else difference does it have?


Solution

  • You will pay a penalty with the recursive version, because along with the overhead for the call, you will repeatedly compare the value of n against <0, ==0 and ==1, which is unnecessary in the loop version.

    A slightly more efficient recursive version could be:

    int F(int n)
    return n < 3 ? n : n * F(n-1)
    

    called from

    int G(int n)
    return n < 2 ? 1 : F(n)