循环（迭代）与递归的区别

1.循环&迭代&回溯&递归&递推

循环：不断重复进行某一运算、操作。

迭代：不断对前一旧值运算得到新值直到达到精度。一般用于得到近似目标值，反复循环同一运算式（函数），并且总是把前一次运算结果反代会运算式进行下一次运算

递推：从初值出发反复进行某一运算得到所需结果。-----从已知到未知，从小到达（比如每年长高9cm，20年180，30后270）

回溯：递归时经历的一个过程。

递归：从所需结果出发不断回溯前一运算直到回到初值再递推得到所需结果----从未知到已知，从大到小，再从小到大(你想进bat，那么编程就的牛逼，就得卸载玩者农药，努力学习）。递归(Recursion)是从归纳法(Induction)衍生出来的。

一个运算（操作），可以通过不断调用本身的运算形式，往往需要通过前一次的结果来得到当前运算的结果，因而，程序运行时，总是先一次次地「回溯」前一次的结果（回溯过程中这些结果是未知的，直到回溯到初值令回溯终止，再层层递推回来得到当前要求的值）

一个完整的递归应该有下面三个条件，否则就是不合格的递归

明确递归的终止方法（一个递归必须有他递推到头的界定，否则将会是无限递归）
明确的终止时处理方法
重复调用自身并缩小问题规模

死循环不会栈溢出而无限递归会出现栈溢出情况，详情推荐阅读：《[递归-程序之美，及其与循环的区别](https://zhuanlan.zhihu.com/p/34841160 递归-程序之美，及其与循环的区别)》，但实际上业务模型几乎不会遇到。

kidneyball知乎回答总结会精辟

在有循环的语言里，有的人认为尾递归优化除了炫技之外是完全无用的。其实不然，尾递归写法在我看来有以下好处

强迫你把循环写成单独的函数。这又有什么好处呢？这会影响你的编程风格，习惯使用尾递归之后，你的写出一个几百行大函数的机率会小得多。
保证没有副作用，统一使用不可变数据。在循环里，循环变量就是一个可变数据。作为人肉开发者，如果想保证自己的某段程序没有副作用，最好的做法就是根本不要写任何带副作用的东西，这样代码审查时一眼看过去就能知道有没有副作用。至于避免副作用有什么好处，这又可以写一篇文章，这里就不展开了。
转换成惰性序列时比较好看。在某些语言里，尾递归形式基本上只要去掉循环变量（变成无限递归）, 把初始状态作为首元素，就是一个能直接拿来用的惰性序列。

“递归”是一种思路，这种思路的特点是：我不关注问题本身，我只关注这个问题如何可以用一种可重复的方式分解为一些规模更小的子问题，以及这些子问题与原问题的关系。再加上当问题的规模足够小的时候，存在一个简单直接的解法。

递推和递归还是迷糊，show code

//递归求解
function fib(n){
   
    return n <2?1:fib(n-1) + fib(n-2);
}
//递推求解
function fib(n){
   
    let start=0;
    let fn=1;
    for (let i=0;i<n;i++) {
   
        let t=fn;
        fn=fn+start;
        start=t;
    }
    return fn;
}

不难看出，

程序的一般写法就好比是数列的通项公式。
程序的递归写法就好比是数列的递推公式。

2.递归算法与迭代算法

递归算法与迭代算法的设计思路区别在于：函数或算法是否具备收敛性，当且仅当一个算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法。当然，从理论上说，所有的递归函数都可以转换为迭代函数，反之亦然，然而代价通常都是比较高的。但从算法结构来说，递归声明的结构并不总能够转换为迭代结构，原因在于结构的引申本身属于递归的概念，用迭代的方法在设计初期根本无法实现，这就像动多态的东西并不总是可以用静多态的方法实现一样。这也是为什么在结构设计时，通常采用递归的方式而不是采用迭代的方式的原因，一个极典型的例子类似于链表，使用递归定义及其简单，但对于内存定义(数组方式)其定义及调用处理说明就变得很晦涩，尤其是在遇到环链、图、网格等问题时，使用迭代方式从描述到实现上都变得很不现实。
递归其实是方便了程序员难为了机器。它只要得到数学公式就能很方便的写出程序。优点就是易理解，容易编程。但递归是用栈机制实现的（c++），每深入一层，都要占去一块栈数据区域，对嵌套层数深的一些算法，递归会力不从心，空间上会以内存崩溃而告终，而且递归也带来了大量的函数调用，这也有许多额外的时间开销。所以在深度大时，它的时空性就不好了。

循环其缺点就是不容易理解，编写复杂问题时困难。优点是效率高。运行时间只因循环次数增加而增加，没什么额外开销。空间上没有什么增加。
局部变量占用的内存是一次性的，也就是O(1)的空间复杂度，而对于递归（不考虑尾递归优化的情况），每次函数调用都要压栈，那么空间复杂度是O(n)，和递归次数呈线性关系。
递归程序改用循环实现的话，一般都是要自己维护一个栈的，以便状态的回溯。如果某个递归程序改用循环的时候根本就不需要维护栈，那其实这个递归程序这样写只是意义明显一些，不一定要写成递归形式。但很多递归程序就是为了利用函数自身在系统栈上的auto变量记录状态，以便回溯。
原理上讲，所有递归都是可以消除的，代价就是可能自己要维护一个栈。而且我个人认为，很多情况下用递归还是必要的，它往往能把复杂问题分解成更为简单的步骤，而且很能反映问题的本质。

3.两者异同点

3.1.相同点

首先，递归和递推又一定的相似性（当然了，不然怎么会提出这个问题？）

这两个问题都可以描述为以下形式：

$f (n) = g (f (n - 1) ， \dots ， f (0))$
这是二者的共同特点。

3.1.不同点

1，从程序上看，递归表现为自己调用自己，递推则没有这样的形式。

2，递归是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题

是逆向的。递推是从简单问题出发，一步步的向前发展，最终求得问题。是正向的。

3，递归中，问题的n要求是计算之前就知道的，而递推可以在计算中确定，不要求计算前就知道n。

4，一般来说，递推的效率高于递归（当然是递推可以计算的情况下）

由于一切递归问题都可以转化为循环求解，因此我们可以定义广义递归：

如果转化为循环后，需要自己维护堆栈，则仍称为是递归的。

在这个定义下，有些问题适用于用递归求解，如梵塔问题有些问题适用于用递推来做，如求满足N!>M条件时最小的N。有些问题二者都可以，如给定N时的阶乘问题。至于可读性，与问题有关，不能一概而论。

**递归其实就是利用系统堆栈，实现函数自身调用，或者是相互调用的过程。**在通往边界的过程中，都会把单步地址保存下来，知道等出边界，再按照先进后出的进行运算，这正如我们装木桶一样，每一次都只能把东西方在最上面，而取得时候，先放进取的反而最后取出。递归的数据传送也类似。但是递归不能无限的进行下去，必须在一定条件下停止自身调用，因此它的边界值应是明确的。就像我们装木桶一样，我们不能总是无限制的往里装，必须在一定的时候把东取出来。比较简单的递归过程是阶乘函数，你可以去看一下。但是递归的运算方法，往往决定了它的效率很低，因为数据要不断的进栈出栈。这时递推便表现出它的作用了，所谓递推，就是免除了数据进出栈的过程。也就是说，不需要函数不断的向边界值靠拢，而直接从边界出发，直到求出函数值。比如，阶乘函数中，递归的数据流动过程如下：

$f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}$

而递推如下：

$f (0) - - > f (1) - - > f (2) - - > f (3)$

**由此可见，递推的效率要高一些，在可能的情况下应尽量使用递推。但是递归作为比较基础的算法，它的作用不能忽视。**所以，在把握这两种算法的时候应该特别注意。