Why recursion is not efficient?

3

I need the factorial of 100, I realize that I need to look for another alternative, could you help?

public class Main {
public static void main(String[] args) {
System.out.println(factorial(100));
}

public static long factorial(long num) {
if (num <= 1)
return num;

return num * factorial(num-1);
}
}

asked by Romulo Gallegos 12.08.2017 в 03:28
source

2

The problem of recursion arises when calculations are already calculated previously, the recursion calculates and repeats calculations until reaching the base case.

I'd better explain it with an image, the factorial (3) and the factorial (4) with recursion:

According to the image, to obtain the factorial(3) the factorial(2) and factorial(1) is calculated, then to obtain the factorial(4) it also calculates the factorial(2) and factorial(1) , then the recursion repeats calculations, that is very bad for execution times .

Why not save the results and use them when you need it? That way they will not be calculated again and again, you only calculate once and that's it.

The code I expose only calculates once and saves them,   for when I need it, that way I do not calculate again and again   time.

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
public static void main(String[] args) {
System.out.println(factorial(100));
}

public static double  factorial(int  n) {
double  result[]=new double   ;
result = 1;
for (int i = 1; i <= n; ++i) {
result[i] = i * result[i - 1];
}
return result[n];
}
}

according to comments, good observations !!!:

Iterative or recursive the problem that you mention would be given of all   forms and that certainly does not apply in this case. Useless   store the intermediate results if then they are going to discard all   except the last one

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
double  result[]=new double   ;
public Main(){
result = 1;
}
public static void main(String[] args) {
System.out.println(factorial(100));
}

public static double  factorial(int  n) {

if(!result[n]){
for (int i = 1; i <= n; ++i) {
result[i] = i * result[i - 1];
}
return result[n];
}else{
return result[n];
}
}
}

source
8

The problem is not the recursion but the value of the factorial of 100 is too big to enter the bits of a long , either in Java or another programming language that handles this type of data. Note that the maximum value of a long in Java is 0x7fffffffffffffffL or 9223372036854775807

In Java, this can be resolved using BigInteger , although it reduces the performance of the application.

Example:

public BigInteger factorial(int n) {
return (n < 0) ? new BigInteger(String.valueOf(n)) :
(n == 0 || n == 1) ? BigInteger.ONE :
new BigInteger(
String.valueOf(n))
.multiply( factorial(n-1) );
}

Result:

System.out.println(factorial(100));
//imprime 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

2

The iterative code you already had yourself, you only needed to change the data type from long to double since the factorial you were looking for is too big for long

public class Main {
public static void main(String[] args) {
System.out.println(factorial(100));
}

public static double factorial(double num) {
double suma = 1;

while(num > 1) {
suma *= num;
num --;
}

return suma;
}
}

That returns: 9.332621544394418E157