java中的递归与迭代

1.递归

如这个阶乘函数：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成线性增长。 当信息量随着输入呈指数增长时，会发生另一种递归，即树递归。

2. 迭代

计算阶乘函数的不同观点是先乘以1，然后乘以3，然后乘以4，直到n。 更正式地说，程序可以使用从1到n的计数器并同时计算product，直到计数器超过n。 因此该程序可以写为：

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

与程序1相比，这个程序不构建一个乘法链。 在每一步中，计算机只需要跟踪product和 i 的当前值。 这种类型的程序被称作迭代，其状态可以通过固定数量的变量，描述变量应该如何更新一个固定的规则，并结束测试指定在其过程中应终止条件来概括。 与递归相同，当所需时间与输入线性增长时，我们称迭代线性递归。

3. 递归 vs 迭代

比较这两个过程，我们可以发现它们看起来几乎相同，特别是在数学函数方面。 它们都需要一些与n成比例的步骤来计算n !. 另一方面，当我们考虑这两个程序的运行过程时，它们的演变将大不相同。

在迭代的情况下，程序变量提供了状态的完整描述。 如果我们在中间停止计算，恢复它只需要向计算机提供所有变量。 但是，在递归过程中，信息由计算机维护，因此对程序“隐藏”。 这使得在停止程序后几乎不可能恢复程序。

4. 树递归

如上所述，当信息量随输入呈指数增长时，会发生树递归。 例如，考虑斐波那契数列的定义如下：

微信截图_20180321151402.png

根据定义，Fibonacci数字具有以下顺序，其中每个数字是前两个数字的总和：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程序在最后一行调用了两次。

另一方面，我们也可以用迭代的方式编写程序来计算斐波那契数。 下面程序是一个线性迭代。 上面的程序和迭代方法写的程序所需的时间差异很大，即使对于较小的输入。

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

但是，人们不应该认为树递归程序是无用的。 当我们考虑在分层数据结构而不是数字上运行的程序时，树递归是一个自然且强大的工具。 它可以帮助我们理解和设计程序。