函数递归和迭代

1.什么是递归？

在C语言中递归就是自己调用自己。

看一下简单函数的递归：

上面的代码实现演示一下函数的递归，最终是会陷入死循环的，栈溢出。

1.1递归的思想：

把一个大型的问题一步一步的转换成一个个小的子问题来解决，直到子问题不能再被分解时，大事化小，就像剥洋葱一样。

1.2递归的限制条件

必须具备的两个条件：

递归存在限制条件，当满足限制条件时，递归便不再继续。
每次递归调用之后越来越越接近这个限制条件

2.递归的举例

2.1求 n 的阶乘

输入一个正整数并计算出该正整数的阶乘，规定 0！=1。

当输入的是0的话，则返回1

其余的按公式计算：Fact(n)=n*Fact(n-1), n>0

//用递归来写计算 n！的结果
//5!=5*4*3*2*1 = 5*4!
//4!=  4*3*2*1 = 4*3!
//3!=    3*2*1 = 3*2!
//2!=      2*1 = 2*1!
//1!=        1 = 1*0!
//0!=        1int Fact(int i)
{if (i == 0)return 1;elsereturn Fact(i - 1) * i;}int main()
{int n = 0;scanf("%d", &n);int ret=Fact(n);printf("%d\n", ret);return 0;
}

n 太大的话就会出现溢出的问题。

2.2输入一个整数，按照顺序输出

例如：输入：1234
输出：1 2 3 4

拆分过程：

1234 拆分为：打印 123 + 打印 4

重新赋值为：123

123 拆分为：打印 12 + 打印 3

重新赋值： 12

12 拆分为：打印 1 + 打印 2

打印： 1

重新赋值：n=n/10;

打印：n%10；

这样的话我们就可以实现先打印 1—>2—>3—>4

//输入一个整数，按照顺序输出 ——递归
//例如：输入：1234
//      输出：1 2 3 4void Print(int n)
{if (n > 9){Print(n / 10);}printf("%d ",n%10);
}int main() 
{int num = 0;scanf("%d", &num);Print(num);return 0;
}

3.递归与迭代

递归是一种很好的编程技巧，它要求程序员的技巧性更高，但是也可能会被误用，如前面的阶乘的例子，看见推导出的公式，很容易就写成递归形式：

int Fact(int i)
{if (i == 0)return 1;elsereturn Fact(i - 1) * i;}

死递归函数调用好多次后会导致栈溢出，但是里面并没有创建任何的变量，这是为什么呢？

这是因为有时即使函数里面没有任何的变量，但是每次的函数调用都会向内存栈区上申请一块空间，这一块空间主要用来存放函数中的局部变量和函数调用过程中的上下文的信息。这一块空间一般叫做：函数的运行时堆栈，也叫函数栈帧空间。编译会根据需要来进行开辟空间。

函数不返回，函数对应的栈帧空间就一种被占用着，所以如果函数调用中存在递归函数的话，每一次的递归函数调用都会开辟属于自己的栈帧空间，知道函数递归不再继续，开始回归，才逐层的释放栈帧空间。

所以如果采用函数递归的方式完成代码，递归层次太深，就会浪费太多的空间，也可能引起栈溢出的问题。

如果不使用递归的话，通常就是用迭代的方式（一般为循环的形式）。

重新实现阶乘：

int Fact(int n)
{int i = 0;int ret = 1;for (i = 1; i <= n; i++){ret *= i;}return ret;
}

上面的代码能够完成阶乘任务，并且效率比递归要好的多。

有许多的问题都是以递归的方式实现的，这仅仅因为它比非递归的形式更加清晰，但是这些问题的迭代实现往往比递归实现效率更高。

然而，当一个问题难以使用迭代的方式解释清楚时，此时递归的简洁性便可以补偿它所带来的运行时的开销。

例子：求第n个斐波那契数

斐波那契数是不适合用递归的方式来解决的。

int Fib(int n)
{int a = 1;int b = 1;int c = 1;while (n >= 3){a = b;b = c;c = a + b;n--;}return c;}int main()
{	int n = 0;printf("请输入第几位的数：");scanf("%d", &n);int ret = Fib(n);printf("%d", ret);return 0;}

当我们输入较小的数字时，运算的很快，当我们将 n 赋值为 50 时，上面的的代码是需要很长很长的时间才会运算出结果，这里就可以看见递归的缺点了，这是因为会进行很多的重复性计算，如下图所示：

我们可以简单地进行重复计算的次数：

int count = 0;
int Fib(int i)
{if (i == 3)count++;if(i<=2)return 1;elsereturn Fib(i - 1) + Fib(i - 2);}int main()
{int n = 0;printf("请输入第几个数字：");scanf("%d", &n);int ret=Fib(n);printf("%d",ret);printf("\ncount=%d\n", count);return 0;
}

当我们输入 40 时，Fib（3）被执行的次数：

上面的运行结果表示的是，第3个斐波那契数被计算了39088169次，可以看出有关斐波那契数的计算用函数的递归方式是相当不明智的，我们就得用迭代的方式来实现。

int Fib(int n)
{int a = 1;int b = 1;int c = 1;while (n >= 3){a = b;b = c;c = a + b;n--;}return c;}int main()
{	int n = 0;printf("请输入第几位的数：");scanf("%d", &n);int ret = Fib(n);printf("%d", ret);return 0;}

用迭代的方式去实现时，就可以感觉到迭代的效率很高。当我们再次输入50时，不会需要很过的时间和空间去进行计算。