为什么在这个Java代码中迭代比递归更快

huangapple go评论88阅读模式
英文:

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(&quot;Factorial of &quot; + number + &quot; is: &quot; + result);

        long endTime = System.nanoTime();
        double executionTime = (endTime - startTime) / 1_000_000_000.0;
        System.out.println(&quot;Execution time: &quot; + executionTime + &quot; seconds&quot;);
    }
}

time: 0.0138802 seconds
Iterative Factorial Code:

public class IterativeFactorial {

    public static long factorial(int n) {
        long result = 1;

        for (int i = 1; i &lt;= 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(&quot;Factorial of &quot; + number + &quot; is: &quot; + result);

        long endTime = System.nanoTime();
        double executionTime = (endTime - startTime) / 1_000_000_000.0;
        System.out.println(&quot;Execution time: &quot; + executionTime + &quot; seconds&quot;);
    }
}

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

huangapple
  • 本文由 发表于 2023年7月6日 21:11:49
  • 转载请务必保留本文链接:https://go.coder-hub.com/76629219.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定