迭代和递归有什么区别？

Question

是什么区别iteration和recursion为什么/时,是一个更好的:

while (true) {
    // Iterating
}

和

private void recursion() {
    if (true)
        recursion(); // Recursing

    return;
}

我看到很多recursive实现,而它可以在一个简单的循环中轻松完成.

Answer 1

递归和同一算法的迭代版本之间存在两个主要差异.

首先,有时候理解递归算法比迭代算法好几乎(至少如果你是经验丰富的程序员)那么它确实增加了表达能力,在某些情况下可以提高可读性(在其他情况下也可能导致完全相反) )

Expresivity在编程语言方面是一个巨大的优势,并且能够在5行中编写相同的代码而不是20行是一个巨大的交易.

在缺点方面,它会降低代码的性能.递归函数必须将函数记录保存在内存中,并从一个内存地址跳转到另一个内存地址,以调用它来传递参数和返回值.这使得他们表现非常糟糕.

总结:

迭代算法=快速性能但难以编写(有时难以阅读)

递归算法=快速写入但性能不佳(有时也更容易理解)

举个例子:

public static long fib(long n) {
    if (n <= 1) return n;
    else return fib(n-1) + fib(n-2);
}

VS

    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        long prev = 1, current = 1, next = 0;
        for (long i = 3; i <= n; i++) {
            next = prev + current;
            prev = current;
            current = next;
        }
        return next;
    }

资源:

http://www.csd.uwo.ca/Courses/CS1027a/code/FibonacciDemo.java

Answer 2

递归和迭代之间的主要区别在于内存使用.

对于每个递归调用,需要堆栈帧上的空间,从而导致内存开销.

让我给你举个例子.想象一下,在一个案例中,你忘了为你的递归函数编写基本案例,导致无休止的递归调用,而在其他情况下,你写了一个无限循环.

由于每个递归函数都会分配新的内存空间,因此在第一种情况下,您的代码将给出堆栈溢出异常,但在第二种情况下,它将永远保持运行.

因此,与使用Recursion相比,更好地使迭代代码更容易理解.