# 递归函数 一个函数在它的函数体内调用它自身称为递归调用，这种函数称为递归函数。执行递归函数将反复调用其自身，每调用一次就进入新的一层，当最内层的函数执行完毕后，再一层一层地由里到外退出。 求阶乘的递归公式如下。 $$ n! = \begin{cases} 1, (n=0, 1)\\ n*(n-1)!, (n>1) \end{cases} $$ 更具阶乘的递推公式代码如下。 ```c #include #include long factorial(int n); int main(int argc, char *argv[]){ int a; printf("Input a number: "); scanf("%d", &a); printf("Factorial(%d) = %ld\n", a, factorial(a)); //注意取数不要取太大，阶乘的数是很容易存储溢出的 system("pause"); return 0; } //求n阶乘 long factorial(int n){ if(n == 0 || n == 1){ return 1; } else{ return factorial(n-1)*n; } } ``` ## 递归函数扩展内容 factorial() 是最简单的一种递归形式——尾递归，也就是递归调用位于函数体的结尾处。除了尾递归，还有更加烧脑的两种递归形式，分别是中间递归和多层递归： - 中间递归：发生递归调用的位置在函数体的中间； - 多层递归：在一个函数里面多次调用自己。 递归函数也只是一种解决问题的技巧，它和其它技巧一样，也存在某些缺陷，具体来说就是：递归函数的时间开销和内存开销都非常大，极端情况下会导致程序崩溃。 ## 递归函数的空间开销 在程序占用的整个内存中，有一块内存区域叫做栈（Stack），它是专门用来给函数分配内存的，每次调用函数，都会将相关数据压入栈中，包括局部变量、局部数组、形参、寄存器、冗余数据等。 栈是针对线程来说的，每个线程都拥有一个栈，如果一个程序包含了多个线程，那么它就拥有多个栈。目前我们编写的程序都是单线程的，所以不必考虑多线程的情况。 对每个线程来说，栈能使用的内存是有限的，一般是 1M~8M，这在编译时就已经决定了，程序运行期间不能再改变。如果程序使用的栈内存超出最大值，就会发生栈溢出（Stack Overflow）错误。 栈内存的大小和编译器有关，编译器会为栈内存指定一个最大值，在 VC/VS 下，默认是 1M，在 C-Free 下，默认是 2M，在 Linux GCC 下，默认是 8M。当然，我们也可以通过参数来修改栈内存的大小。 发生函数调用时会将相关数据压入栈中，函数调用结束会释放这一部分内存，对于一般的函数来说，这不会有任何问题，但是对于递归函数，这会导致严重的问题！ 递归函数内部嵌套了对自身的调用，除非等到最内层的函数调用结束，否则外层的所有函数都不会调用结束。通俗地讲，外层函数被卡主了，它要等待所有的内层函数调用完成后，它自己才能调用完成。 每一层的递归调用都会在栈上分配一块内存，有多少层递归调用就分配多少块相似的内存，所有内存加起来的总和是相当恐怖的，很容易超过栈内存的大小限制，这个时候就会导致程序崩溃。 例如，一个递归函数需要递归 10000 次，每次需要 1KB 的内存，那么最终就需要 10MB 的内存。 为了演示由于栈溢出而导致程序崩溃的情形，下面我们用递归的方式来求 1+2+3+ ...... + (n-1) + n 的值： ```c #include #include long sum(int n); int main(int argc, char *argv[]){ printf("从1加到1000的值: %ld\n", sum(1000)); return 0; } long sum(int n){ //为了增加每次函数调用的内存，额外增加了一个无用的数组，它占用 1KB 的内存 int arr[250]; if(n<=1){ return n; } else{ return n + sum(n-1); } } ``` 这是因为，每次递归调用都需要超过 1KB 的内存（仅仅数组就占用了 1KB 内存），而要得到最终的结果需要 1000 次递归调用，这样一来，所有内存的总和就超过了 1MB。 上面我们说过，Visual Studio 默认的栈内存只有 1MB，超过这个界限程序就无法运行了，只能让它崩溃。使用其它的编译器也许程序不会崩溃，读者可以亲自尝试。 ## 递归函数的时间开销 每次调用函数都会在栈上分配内存，函数调用结束后再释放这一部分内存，内存的分配和释放都是需要时间的。每次调用函数还会多次修改寄存器的值，函数调用结束后还需要找到上层函数的位置再继续执行，这也是需要时间的。所有的这些时间加在一起是非常恐怖的。 下面我们以「求斐波那契数」为例来演示双层递归的时间开销。 ```c #include #include #include long fib(int n); int main(int argc, char *argv[]) { int a; clock_t time_start, time_end; printf("Input a number: "); scanf("%d", &a); time_start = clock(); printf("Fib(%d) = %ld", a, fib(a)); time_end = clock(); printf("\nrun time: %lf s\n", (double)(time_end-time_start)/CLOCKS_PER_SEC); printf("开始时钟: %d\n", time_start); printf("结束时钟: %d\n", time_end); printf("%ld\n", CLOCKS_PER_SEC); system("pause"); return 0; } long fib(int n) { if (n <= 2) { return 1; } else { return fib(n - 1) + fib(n - 2); } } ``` ## 使用迭代来替换递归函数 既然递归函数的解决方案存在巨大的内存开销和时间开销，那么我们如何进行优化呢？优化个毛，这是函数实现原理层面的缺陷，无法优化。其实，大部分能用递归解决的问题也能用迭代来解决。所谓迭代，就是循环。 许多问题是以递归的形式进行解释的，这只是因为它比非递归形式更为清晰。但是，这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性可能稍差一些。与递归函数相比，迭代不但没有额外的内存开销，也没有额外的时间开销。看来我之前当助教时有个优秀的学生问我如何用递归解决什么问题，具体什么问题我已经不记得了，但是我当时对她的解答时，你怎么用递归，最好不要用递归的话还是很有道理的，没有坑人家，虽然当时我还不知道这么多，哈哈。 下面我们分别用递归和迭代的方案来求斐波那契数，看看它们究竟孰快孰慢。 ```c #include #include #include long fib_recursion(int n); long fib_iteration(int n); int main(int argc, char *argv[]){ int a; clock_t time_start_recursion, time_end_recursion; clock_t time_start_iteration, time_end_iteration; printf("Input a number: "); scanf("%d", &a); //递归 time_start_recursion = clock(); printf("Fib_recursion(%d) = %ld\n", a, fib_recursion(a)); time_end_recursion = clock(); printf("recursion run time: %lf s\n", (double)(time_end_recursion-time_start_recursion)/CLOCKS_PER_SEC); //迭代 time_start_iteration = clock(); printf("Fib_iteration(%d) = %ld\n", a, fib_iteration(a)); time_end_iteration = clock(); printf("iteration run time: %lf s\n", (double)(time_end_iteration-time_start_iteration)/CLOCKS_PER_SEC); system("pause"); return 0; } long fib_recursion(int n){ if (n <= 2) { return 1; } else { return fib_recursion(n - 1) + fib_recursion(n - 2); } } long fib_iteration(int n){ long result; long previous_result; long next_older_result; result = previous_result = 1; while(n>2){ n -= 1; next_older_result = previous_result; previous-result = result; result = previous_result + next_older_result; } return result; } ``` 我输入一个较大的数来计算：可以看到惊人的结果。 Input a number: 44 Fib_recursion(44) = 701408733 recursion run time: 25.080000 s Fib_iteration(44) = 701408733 iteration run time: 0.000000 s 这递归和迭代两种解法的程序性能相差的也太大了吧！ 函数调用本来就存在内存开销和时间开销，递归一次这种开销就增加一倍，如果有成千上万次的递归，那么所有开销的总和就是巨大的。这是递归的致命缺陷，无法优化。所以建议大家尽量少用递归，能用迭代就用迭代吧。