英文:
Why is iteration faster than recursion in this java code
问题
我已经翻译好了代码部分:
递归阶乘代码:
public class RecursiveFactorial {
public static long factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
public static void main(String[] args) {
int number = 5;
long startTime = System.nanoTime();
long result = factorial(number);
System.out.println("Factorial of " + number + " is: " + result);
long endTime = System.nanoTime();
double executionTime = (endTime - startTime) / 1_000_000_000.0;
System.out.println("Execution time: " + executionTime + " seconds");
}
}
时间:0.0138802秒
迭代阶乘代码:
public class IterativeFactorial {
public static long factorial(int n) {
long result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
public static void main(String[] args) {
int number = 5;
long startTime = System.nanoTime();
long result = factorial(number);
System.out.println("Factorial of " + number + " is: " + result);
long endTime = System.nanoTime();
double executionTime = (endTime - startTime) / 1_000_000_000.0;
System.out.println("Execution time: " + executionTime + " seconds");
}
}
时间:0.0003859秒
英文:
I've implemented two Java codes for calculating the factorial of a number, one using recursion and the other using iteration. The iterative code seems to be faster than the recursive code in terms of execution time. However, I'm curious to understand why this performance difference occurs.
Recursive Factorial Code:
public class RecursiveFactorial {
public static long factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
public static void main(String[] args) {
int number = 5;
long startTime = System.nanoTime();
long result = factorial(number);
System.out.println("Factorial of " + number + " is: " + result);
long endTime = System.nanoTime();
double executionTime = (endTime - startTime) / 1_000_000_000.0;
System.out.println("Execution time: " + executionTime + " seconds");
}
}
time: 0.0138802 seconds
Iterative Factorial Code:
public class IterativeFactorial {
public static long factorial(int n) {
long result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
public static void main(String[] args) {
int number = 5;
long startTime = System.nanoTime();
long result = factorial(number);
System.out.println("Factorial of " + number + " is: " + result);
long endTime = System.nanoTime();
double executionTime = (endTime - startTime) / 1_000_000_000.0;
System.out.println("Execution time: " + executionTime + " seconds");
}
}
time: 0.0003859 seconds
I would appreciate if someone could shed light on the reasons behind the observed performance difference between the recursive and iterative implementations. Additionally, it would be interesting to see some random execution times for both codes to further illustrate the disparity.
答案1
得分: 1
Short Answer: 迭代不使用堆栈,因此比递归更快。
Description: 在递归方法中,每次调用都会在内存中保留。如果一个逻辑以递归方式调用一个方法90次,那么相同的方法将会被重复加载到内存堆栈中90次,带有重复的变量。而循环/迭代只会在内存堆栈中加载一次(当其方法加载时),并且大多数变量将被重复使用。
请参考:is-recursion-ever-faster-than-looping
英文:
Short Answer: An iteration does not use the stack so it's faster than recursion.
Description: In recursion method get in memory every-time it is called. If an logic calls a method 90 times recursively then same method will get load into memory stack 90 times with repeated variables. Where loop/iteration get load into memory stack only once (when its method will get load) and most of variables will be reused.
Please refer: is-recursion-ever-faster-than-looping
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论