Java中的迭代与递归

递归

提到迭代，不得不提一个数学表达式： n!=n*(n-1)*(n-2)*...*1

有很多方法来计算阶乘。有一定数学基础的人都知道n!=n*(n-1)!因此，代码的实现可以直接写成：

代码一

int factorial (int n) {
    if (n == 1) {
        return 1;
    } else {
        return n*factorial(n-1);
    }
}   

在执行以上代码的时候，其实机器是要执行一系列乘法的： factorial(n) → factorial(n-1) → factorial(n-2) → ... → factorial(1)。所以，需要不断的跟踪（跟踪上次计算的结果）并调用乘法进行计算（构建一个乘法链）。这类不断调用自身的运算形式称之为递归。递归可以进一步的分为线性递归和数形递归。信息量随着算法的输入呈线性增长的递归称之为线性递归。计算n!（阶乘）就是线性递归。因为随着N的增大，计算所需的时间呈线性增长。另外一种信息量随着输入的增长而进行指数增长的称之为树形递归。

迭代

另外一种计算n!的方式是：先计算1乘以2，然后用其结果乘以3，再用的到的结果乘以4....一直乘到N。在程序实现时，可以定义一个计数器，每进行一次乘法，计数器都自增一次，直到计数器的值等于N截至。代码如下：

代码二

int factorial (int n) {
    int product = 1;
    for(int i=2; i<n; i++) {
        product *= i;
    }
    return product;
}

和代码一相比，代码二没有构建一个乘法链。在进行每一步计算时，只需要知道当前结果（product）和i的值就可以了。这种计算形式称之为迭代。迭代有这样几个条件：1、有一个有初始值的变量。2、一个说明变量值如何更新的规则。3、一个结束条件。（循环三要素：循环变量、循环体和循环终止条件）。和递归一样。时间要求随着输入的增长呈线性的可以叫做线性迭代。

迭代 VS 递归

比较了两个程序，我们可以发现，他们看起来几乎相同，特别是其数学函数方面。在计算n!的时候，他们的计算步数都是和n的值成正比的。但是，如果我们站在程序的角度，考虑他们是如何运行的话，那么这两个算法就有很大不同了。

（注：原文中关于其区别写的有点扯，这里就不翻译了，下面是笔者自己总结内容。）

首先分析递归，其实递归最大的有点就是把一个复杂的算法分解成若干相同的可重复的步骤。所以，使用递归实现一个计算逻辑往往只需要很短的代码就能解决，并且这样的代码也比较容易理解。但是，递归就意味着大量的函数调用。函数调用的局部状态之所以用栈来记录的。所以，这样就可能浪费大量的空间，如果递归太深的话还有可能导致堆栈溢出。

接下来分析迭代。其实，递归都可以用迭代来代替。但是相对于递归的简单易懂，迭代就比较生硬难懂了。尤其是遇到一个比较复杂的场景的时候。但是，代码的难以理解带来的有点也比较明显。迭代的效率比递归要高，并且在空间消耗上也比较小。

递归中一定有迭代，但是迭代中不一定有递归，大部分可以相互转换。

能用迭代的不要用递归，递归调用函数不仅浪费空间，如果递归太深的话还容易造成堆栈的溢出。

数形递归

前面介绍过，树递归随输入的增长的信息量呈指数级增长。比较典型的就是斐波那契数列：

用文字描述就是斐波那契数列中前两个数字的和等于第三个数字：0,1,1,2,3,5,8,13,21……

递归实现代码如下：

int fib (int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

计算过程中，为了计算fib(5)，程序要先计算fib(4) 和 fib(3)，要想计算fib(4) ，程序同样需要先计算 fib(3) 和 fib(2)。在这个过程中计算了两次fib(3)。

从上面分析的计算过程可以得出一个结论：使用递归实现斐波那契数列存在冗余计算。

就像上面提到的，可以用递归的算法一般都能用迭代实现，斐波那契数列的计算也一样。

int fib (int n) {
    int fib = 0;
    int a = 1;
    for(int i=0; i<n; i++) {
       int temp = fib;
        fib = fib + a;
        a = temp;
    }
    return fib;
}

虽然使用递归的方式会有冗余计算，可以用迭代来代替。但是这并不表明递归可以完全被取代。因为递归有更好的可读性。