# 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

## 3 answers

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];
}
}
}
``````

answered by 12.08.2017 / 04:27
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
``````

answered by 12.08.2017 в 03:54
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`

answered by 12.08.2017 в 03:57