1. The common iterative method of factorial
/** **@paramN factorial times star@return* /
static long factorIterative(long n) {
long r = 1;
for (int i = 1; i <= n; i++) {
r *= i;
}
return r;
}
static long factorRecursive(long n) {
return n == 1 ? 1 : n * factorIterative(n - 1);
}
Copy the code
2. Recursive call – tail recursion (tail – recursion)
/** * Recursive call - tail recursion (tail recursion) **@author houxiurong
* @dateThe 2019-10-02 * /
public class TailRecursiveMethod {
/** * Recursive call - tail recursion (tail recursion) **@paramN factorial number *@return1 * 2 * 3... *n */
static long factorTailRecursive(long n) {
return factorHelper(1, n);
}
private static long factorHelper(long acc, long n) {
return n == 1 ? acc : factorHelper(acc * n, n - 1);
}
public static void main(String[] args) {
System.out.println(factorTailRecursive(5)); }}Copy the code
conclusion
According to the above two different processing methods, to sum up the efficiency of the program execution. As Java users, we should strongly recommend using recursion over iteration. In general, the overhead of performing a recursive method call is much higher than iteratively performing branch treatments for a single machine. Each time a factorRecursive method call is executed, a new stack frame is created on the call stack (local variable table, operation stack, dynamic link, return address), and the user saves the state of each method call (the multiplication required), which guides the program through to completion. This means that the recursive method consumes memory in proportion to the input it receives. Finally, if you execute factorRecursive with a large input, you can easily result in StackOverflowError.
Execption in thread "main" java.lang.StackOverflowError
Copy the code
The above implementation is fine for small scale numerical recursion. Using functional languages provides a better way to do this: tail-recursion. This new type of iterative call is optimized to execute super fast. Recursive calls occur at the end of the method, and instead of saving the intermediate value of each recursive calculation on a different stack frame, the compiler is able to optimize the decision to reuse the stack frame for calculation, which is helpful for compiler optimization (escape analysis).