函数递归和迭代（简单认识）

1.递归思想

把一个大型复杂问题层层转化为一个与原问题相似，但规模较小的子问题来求解；直到子问题不能再被拆分，递归就结束了。所以递归的思考方式就是把大事化小的过程。递归中的递就是递推的意思，归就是回归的意思，接下来慢慢来体会。

注意：在书写递归代码时要给定限制条件，满足条件时递归停下。

2.函数递归

函数递归其实就是函数自己调用自己。

下面我们用一个例子来说明：

用递归的代码完成输入一个数num，并按照顺序打印出来。

void Print(int num)
{
	if (num > 9)//当num为1位数时跳出if语句
	{
		Print(num / 10);//1234/10=123, 123/10=12; 12/10=1; 
 	}
	printf("%d ", num % 10);//1,12%10=2, 123%10=3,1234%10=4.
}

int main()
{
	int num = 0;
	scanf("%d", &num);
	Print(num);
	return 0;
}

在上述代码中如果我们输入1234.使用pint函数自己调用自己实现递归，在此过程中当num变为1位数时跳出if语句，这一过程就是“递”。下面就来到了“归”，在归中我们就开始从后往前的计算值。首先打印1，然后打印12%10、123%10、1234%10,然后打印出来就是1234.

然我们来看看结果：

到这里有些小伙伴还是有点懵，没关系我们再举个例子：

输入一个值n计算其的阶乘。

int  factorial(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
		return n*factorial(n - 1);

}
int main()
{
	int n = 0;
	scanf("%d", &n);
	 int ret=factorial(n);
	 printf("%d", ret);
	return 0;

}

在上述代码中我们定义了一个函数factorial用来计算阶乘，返回值类型为int ，4的阶乘为4*3*2*1,所以当我们输入1时直接返回1，当我们输入2时，进入else返回2*factorial（n-1）,此时的factorial（n-1）的值为1，所以返回2*1。被ret接收。

3.递归代码的缺陷

虽然递归代码写起来比较简单，但是我们的函数在每次调用自己时都需要在内存中申请内存，这样的话就会导致占用很多的内存空间，肯呢个会导致栈溢出。而且运算量较大。

我们用一个例子来说明：

用递归的方式查找斐波那契数列的位数的数值。

int seek(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else
		return seek(n -1) + seek(n -2);
 }
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret=seek(n);
	printf("%d", ret);
}

我们知道斐波那契数列为1 1 2 3 5 8........等，当我们查找的位数小于2时就是1，大于2时就是前两个数的和。虽然我们在这里输入5可以算出5当我们输入比较大的数时就会发现电脑算不出来了，这个就是因为运算过程较复杂。在这里可以试试其实当我们输入45时就很难算出来了。

4.迭代

迭代（Iteration）是程序中常用的一种控制流程方式，它让程序能够重复执行一段代码块，从而达到对一组数据或集合进行处理的目的。在C语言中，迭代常常与循环语句结合使用，例如for循环和while循环。迭代器（Iterator）则是一种辅助工具，它提供了对数据集合中元素进行遍历和访问的方法。

那我们来使用迭代的方式来解决这个问题：（在递归计算中有很多的重复步骤，占用了大量的内存，并且使运算量增大）

int seek(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = seek(n);
	printf("%d", ret);
	return 0;
}

这次用迭代的方式进行完成。这次我们再次输入45就可以立马计算出值，这是因为这种方式的计算过程更简单。