递归和迭代详解

一.递归

什么是递归：

程序调用自身的编程技巧称为递归（ recursion）。

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接 调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问 题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。

int main()
{
     printf("hello!!!");
     main();
     return 0;
}

这就是一个简单的递归,但是如果像这样没有条件限制的情况下,在程序运行后会跳出下面的这种情况:

我们称这种情况叫做栈溢出，意思就是,系统给我们这个Main函数分配的空间被沾满,用图来表示就是:

栈溢出就是6块分配的内存全部使用完,造成溢出，为了防止出现这种情况的出现，我们对递归做出了限制，使用递归必须要有这两个必要条件：

1.存在限制条件，当满足这个限制条件的时候，递归便不再继续。

2.每次递归调用之后越来越接近这个限制条件。

下面举一个例子：

一.使用递归实现数字n的阶层：

int jc(int X)
{
    if(X>0)
    {
        return X*jc(X-1);
    }    
 
}
int main()
{
    int num=0;
    scanf("%d",&num);
    int c=jc(num);
    printf("%d阶层数为：%d",num,c);    
  return 0;
}

我用图的形式给大家讲解一下这个题递归的原理

通过图解清晰看出递归的工作原理,同时也符合上面所需的两个必要条件

二.迭代

什么是迭代:

迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。重复执行一系列运算步骤，从前面的量依次求出后面的量的过程。

int main(0
{
    int s=1;
    while(s!=5)
    {
        printf("%d",s);
        s++;
    }
    return 0;
}

如果让我们一个一个去比,工作巨大且效率也不高,使用了迭代可以去除重复多余的部分,所以迭代成为很好的选择

下面举一个例子：

一.做一个可以计算字符个数的函数

int my_strlen(char* str)
{
    int con=0;
    while(*str!='\0')
    {
        str++;
        con++;
    }
 return con;
}
int main()
{
  int d=0;
  char str[]="abcde";
  d=my_strlen(&str);
  printf("字符个数%d",d);
  return 0;
}

一个简易版的strlen函数就完成了,这里就是使用了迭代,不停的去和\0进行比较,没比较一次都会自增1,这样我们省下了很大的工作量。

三.递归和迭代

上面分别讲解了递归和迭代,两者之间有相同点也有不同的地方

1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。

2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。

3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。