递归和迭代

1、知乎回答摘录

递归和迭代_第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


递归和迭代_第2张图片
小规模汉诺塔问题

摘自: http://chenqx.github.io/2014/09/29/Algorithm-Recursive-Programming/

你可能感兴趣的