递归和迭代

1、知乎回答摘录

图解

---

递归是一个树结构，每个分支都探究到最远，发现无法继续的时候往回走，
每个节点只会访问一次。
迭代是一个环结构，每次迭代都是一个圈，不会拉掉其中的某一步，然后不断循环，
每个节点都会被循环访问。

---

给迭代举个通俗点的例子：假如你有一条哈士奇和一条中华田园犬，怎么让它们串出比较纯正的哈士奇呢？先让哈士奇与中华田园犬配对，生下小狗。再让哈士奇与小狗配对，当然要等小狗长大后。就这样一直让哈士奇与新生的小狗配对，一代一代地迭，最终你能得到比较纯正的哈士奇。
递归，简讲就是自己调用自己，自己包含自己。
用程序表述就是：void f(int n){f(n - 1);}不要在意这是死循环代码，只需知道这个函数中，又调用了函数自身，属于自己调用自己。

---

//迭代：
int func(n)
{
  int s=1;
  for(int i=1;i<=n;i++)
  {
    s*=i;
  }
  return s;
}
//递归：
int func(n)
{
  int s=1;
  if(n>1)
  {
    s=n*func(n-1);
  }
}
//递归：（递推到回归）不停调用自己，是迭代的特例，时间复杂度低，耗费空间。
//迭代：A不停调用B。

摘自：https://www.zhihu.com/question/20278387

---

小规模汉诺塔问题
摘自：http://chenqx.github.io/2014/09/29/Algorithm-Recursive-Programming/