递归还是迭代

还是那本书<冒号课堂>,上看来的,这本书好处就是纠正了我一些错误的认知

先打自己的脸

我单纯的觉得迭代就是递归,或者是for循环 (啪~

递归定义

递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法.递归一词还较常用于描述以自相似方法重复事物的过程.例如: 当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的.也可以理解为自我复制的过程. (wiki)

迭代定义

迭代是重复反馈过程的活动,其目的通常是为了接近并到达所需的目标或结果.每一次对过程的重复被称为一次 "迭代",而每一次迭代得到的结果会被用来作为下一次迭代的初始值. (wiki)

在计算机科学中,迭代是程序中对一组指令(或一定步骤)的重复。它既可以被用作通用的术语(与 “重复” 同义),也可以用来描述一种特定形式的具有可变状态的重复。

看到知乎一个关于这个问题的答案interesting

递归:
】】】
】】】】】】
...
】】】】】】】】】
】】】】】】】】】】】】
】】】】】】】】】
...
】】】】】】
】】】

迭代:
】】】
】】】
】】】
】】】
...
】】】
】

举个栗子,计算n阶乘:

function fact(n) {  
    if (n === 1) {
        return 1;
    } else {
        return n * fact(n-1);
    }
}

这个实现里,函数不断调用自身,所以这是一个迭代,它将一个大规模的问题,不断分解成小的问题进行求解.

function fact(n) {  
    function fact_iter(product, count, n) {
        if (count > n) {
            return product;
        } else {
            return fact_iter(product*count, count+1, n);
        }
    }
    return fact_iter(1, 1, n);
}

这个实现里,fact_iter也调用了自身,所以,在这种实现里,它是迭代也是递归

function fact(n) {  
    var result = 1;
    for(var i = i; i <= n; i ++) {
        result *=i;
    }
    return result;
}

第三种实现里,它是迭代,但是它并不是递归, 他在循环中对result不断赋值,这种改变赋值----或者叫做可变状态---是迭代的特征

计算过程展开

fact(5); 我们把计算过程展开看看

fact(5);

5 * fact(4);

5 * 4 * fact(3);

5 * 4 * 3 * fact(2);

5 * 4 * 3 * 2 * fact(1);

5 * 4 * 3 * 2 * 1;

20 * 3 * 2 * 1;

60 * 2 * 1;

120 * 1;

120
fact(5);

fact_iter(1, 1, 5);

fact_iter(1*1, 1+1, 5);

fact_iter(1*2, 2+1, 5);

fact_iter(2*3, 3+1, 5);

fact_iter(6*4, 4+1, 5);

fact_iter(24*5, 5+1, 5);

120
fact(5);

result = 1;

result = 1*1;

result = 1*2;

result = 2*3;

result = 6*4;

result = 24*5;

result = 120;

120;

如你所见递归有一个展开到收缩的过程,而迭代没有.

递归过程中, 问题的规模在缩小,这样最终得到问题的解;而迭代是一种由远变近的逼近,问题的规模不见得缩小了,但是慢慢在调整接近答案。递归求解 n 的阶乘过程,非常符合这个描述;

迭代是逐渐逼近,用新值覆盖旧值,直到满足条件后结束,不保存中间值,空间利用率高。 递归是将一个问题分解为若干相对小一点的问题,遇到递归出口再原路返回,因此必须保存相关的中间值,这些中间值压入栈保存,问题规模较大时会占用大量内存。

所以,以我的理解,函数调用了自身,就是递归.

不断重复一个过程,逐步逼近结果,则是迭代;

优缺点

迭代是在局部内存进行重复计算,递归需要展开栈空间进行每一步的函数现场存储和结果存储。迭代没有这个展开的开销

参考

-- Ming