递归算法的优缺点有哪些？递归算法的优缺点总

 C允许函数调用它自己，这种调用过程称为递归（recursion）。递归有时难以捉摸，有时却很方便实用。结束递归是使用递归的难点，因为如果递归代码中没有终止递归的条件测试部分，一个调用自己的函数会无限递归。可以使用循环的地方通常都可以使用递归。有时用循环解决问题比较好，但有时用递归更好。递归方案更简洁，但效率却没有循环高。

 1 揭秘递归

 我们通过一个程序示例，来学习什么是递归。示例程序01的main()函数调用up_and_down()函数，这次调用称为“第1级递归”。然后up_and_down()调用自己，这次调用称为“第2级递归”。接着第2级递归调用第3级递归，以此类推。该程序示例共有4级递归。为了进一步深入研究递归时发生了什么，程序不仅显示了变量n的值，还显示了存储n的内存地址&n。

 /* recur.c -- recursion illustration */#includevoid up_and_down(int);int main(void){ up_and_down(1); return 0;}void up_and_down(int n){ printf("Level %d: n location %p\n", n, &n); // 1 if (n < 4) up_and_down(n+1); printf("LEVEL %d: n location %p\n", n, &n); // 2}

 输出结果为：

 : Level 1: n location 0x7ffe9db9ce7c

 : Level 2: n location 0x7ffe9db9ce5c

 : Level 3: n location 0x7ffe9db9ce3c

 : Level 4: n location 0x7ffe9db9ce1c

 : LEVEL 4: n location 0x7ffe9db9ce1c

 : LEVEL 3: n location 0x7ffe9db9ce3c

 : LEVEL 2: n location 0x7ffe9db9ce5c

 : LEVEL 1: n location 0x7ffe9db9ce7c

 我们来仔细分析程序中的递归是如何工作的。

 首先，main()调用了带参数1的up_and_down()函数，执行结果是up_and_down()中的形式参数n的值是1，所以打印语句#1打印Level-1。

 然后，由于n小于4，up_and_down()（第1级）调用实际参数为n + e1（或2）的up_and_down()（第2级）。于是第2级调用中的n的值是2，打印语句#1打印Level 2。与此类似，下面两次调用打印的分别是Level 3和Level 4。当执行到第4级时，n的值是4，所以if测试条件为假。up_and_down()函数不再调用自己。第4级调用接着执行打印语句#2，即打印LEVEL 4，因为n的值是4。此时，第4级调用结束，控制被传回它的主调函数（即第3级调用）。在第3级调用中，执行的最后一条语句是调用if语句中的第4级调用。被调函数（第4级调用）把控制返回在这个位置，因此，第3级调用继续执行后面的代码，打印语句#2打印LEVEL 3。然后第3级调用结束，控制被传回第2级调用，接着打印LEVEL 2，以此类推。

 注意，每级递归的变量n都属于本级递归私有。这从程序输出的地址值可以看出（当然，不同的系统表示的地址格式不同，这里关键要注意，Level 1和LEVEL 1的地址相同，Level 2和LEVEL 2的地址相同，等等）。

 如果觉得不好理解，可以假设有一条函数调用链——fun1()调用fun2()、fun2()调用fun3()、fun3()调用fun4()。当fun4()结束时，控制传回fun3()；当fun3()结束时，控制传回fun2()；当fun2()结束时，控制传回fun1()。递归的情况与此类似，只不过fun1()、fun2()、fun3()和fun4()都是相同的函数。

 2 递归的基本原理

 初次接触递归会觉得较难理解。为了帮助读者理解递归过程，下面以程序清单9.6为例讲解几个要点。

 第1，每级函数调用都有自己的变量。也就是说，第1级的n和第2级的n不同，所以程序创建了4个单独的变量，每个变量名都是n，但是它们的值各不相同。当程序最终返回up_and_down()的第1级调用时，最初的n仍然是它的初值1（见图9.4）。

 Recursion variables.

 第2，每次函数调用都会返回一次。当函数执行完毕后，控制权将被传回上一级递归。程序必须按顺序逐级返回递归，从某级up_and_down()返回上一级的up_and_down()，不能跳级回到main()中的第1级调用。

 第3，递归函数中位于递归调用之前的语句，均按被调函数的顺序执行。例如，程序清单9.6中的打印语句#1位于递归调用之前，它按照递归的顺序：第1级、第2级、第3级和第4级，被执行了4次。

 第4，递归函数中位于递归调用之后的语句，均按被调函数相反的顺序执行。例如，打印语句#2位于递归调用之后，其执行的顺序是第4级、第3级、第2级、第1级。递归调用的这种特性在解决涉及相反顺序的编程问题时很有用。稍后将介绍一个这样的例子。

 第5，虽然每级递归都有自己的变量，但是并没有拷贝函数的代码。程序按顺序执行函数中的代码，而递归调用就相当于又从头开始执行函数的代码。除了为每次递归调用创建变量外，递归调用非常类似于一个循环语句。实际上，递归有时可用循环来代替，循环有时也能用递归来代替。

 第6，递归函数必须包含能让递归调用停止的语句。通常，递归函数都使用if或其他等价的测试条件在函数形参等于某特定值时终止递归。为此，每次递归调用的形参都要使用不同的值。例如，示例程序01的up_and_down(n)调用up_and_down(n+1)。最终，实际参数等于4时，if的测试条件(n < 4)为假。

 3 尾递归

 最简单的递归形式是把递归调用置于函数的末尾，即正好在return语句之前。这种形式的递归被称为尾递归（tailrecursion），因为递归调用在函数的末尾。尾递归是最简单的递归形式，因为它相当于循环。下面要介绍的程序示例中，分别用循环和尾递归计算阶乘。一个正整数的阶乘（factorial）是从1到该整数的所有整数的乘积。例如，3的阶乘（写作3！）是1×2×3。另外，0！等于1，负数没有阶乘。，第1个函数使用for循环计算阶乘，第2个函数使用递归计算阶乘。

 示例02：

 // factor.c -- uses loops and recursion to calculate factorials#includelong fact(int n);long rfact(int n);int main(void){ int num; printf("This program calculates factorials.\n"); printf("Enter a value in the range 0-12 (q to quit):\n"); while (scanf("%d", &num) == 1) { if (num < 0) printf("No negative numbers, please.n"); else if (num > 12) printf("Keep input under 13.\n"); else { printf("loop: %d factorial = %ld\n", num, fact(num)); printf("recursion: %d factorial = %ld\n", num, rfact(num)); } printf("Enter a value in the range 0-12 (q to quit):\n"); } printf("Bye.\n"); return 0;}long fact(int n) // loop-based function{ long ans; for (ans = 1; n > 1; n--) ans *= n; return ans;}long rfact(int n) // recursive version{ long ans; if (n > 0) ans= n * rfact(n-1); else ans = 1; return ans;}

 测试驱动程序把输入限制在0~12。因为12!已快接近5亿，而13!比62亿还大，已超过我们系统中long类型能表示的范围。要计算超过12的阶乘，必须使用能表示更大范围的类型，如double或long long。

 下面是该程序的运行示例：

 This program calculates factorials.

 Enter a value in the range 0-12 (q to quit):

 5

 loop: 5 factorial = 120

 recursion: 5 factorial = 120

 Enter a value in the range 0-12 (q to quit):

 10

 loop: 10 factorial = 3628800

 recursion: 10 factorial = 3628800

 Enter a value in the range 0-12 (q to quit):

 q

 Bye.

 使用循环的函数把ans初始化为1，然后把ans与从n~2的所有递减整数相乘。根据阶乘的公式，还应该乘以1，但是这并不会改变结果。

 现在考虑使用递归的函数。该函数的关键是n! = n×(n-1)!。可以这样做是因为(n-1)!是n-1~1的所有正整数的乘积。因此，n乘以n-1的阶乘就得到n的阶乘。阶乘的这一特性很适合使用递归。如果调用函数rfact()，rfact(n)是n*rfact(n-1)。因此，通过调用rfact(n-1)来计算rfact(n)，如程序清单9.7中所示。当然，必须要在满足某条件时结束递归，可以在n等于0时把返回值设为1。

 示例02中使用递归的输出和使用循环的输出相同。注意，虽然rfact()的递归调用不是函数的最后一行，但是当n>0时，它是该函数执行的最后一条语句，因此它也是尾递归。

 既然用递归和循环来计算都没问题，那么到底应该使用哪一个？一般而言，选择循环比较好。首先，每次递归都会创建一组变量，所以递归使用的内存更多，而且每次递归调用都会把创建的一组新变量放在栈中。递归调用的数量受限于内存空间。其次，由于每次函数调用要花费一定的时间，所以递归的执行速度较慢。那么，演示这个程序示例的目的是什么？因为尾递归是递归中最简单的形式，比较容易理解。在某些情况下，不能用简单的循环代替递归，因此读者还是要好好理解递归。

 4 递归和倒序计算

 递归在处理倒序时非常方便（在解决这类问题中，递归比循环简单）。我们要解决的问题是：编写一个函数，打印一个整数的二进制数。二进制表示法根据2的幂来表示数字。例如，十进制数234实际上是2×102+3×101+4×100，所以二进制数101实际上是1×22+0×21+1×20。二进制数由0和1表示。我们要设计一个以二进制形式表示整数的方法或算法（algorithm）。例如，如何用二进制表示十进制数5？在二进制中，奇数的末尾一定是1，偶数的末尾一定是0，所以通过5 % 2即可确定5的二进制数的最后一位是1还是0。一般而言，对于数字n，其二进制的最后一位是n % 2。因此，计算的第一位数字实际上是待输出二进制数的最后一位。这一规律提示我们，在递归函数的递归调用之前计算n % 2，在递归调用之后打印计算结果。这样，计算的第1个值正好是最后一个打印的值。

 要获得下一位数字，必须把原数除以2。这种计算方法相当于在十进制下把小数点左移一位，如果计算结果是偶数，那么二进制的下一位数就是0；如果是奇数，就是1。例如，5/2得2（整数除法），2是偶数（2%2得0），所以下一位二进制数是0。到目前为止，我们已经获得01。继续重复这个过程。2/2得1，1%2得1，所以下一位二进制数是1。因此，我们得到5的等价二进制数是101。那么，程序应该何时停止计算？当与2相除的结果小于2时停止计算，因为只要结果大于或等于2，就说明还有二进制位。每次除以2就相当于去掉一位二进制，直到计算出最后一位为止（如果不好理解，可以拿十进制数来做类比：628%10得8，因此8就是该数最后一位；而628/10得62，而62%10得2，所以该数的下一位是2，以此类推）。程序清单9.8演示了上述算法。

 /* binary.c -- prints integer in binary form */#includevoid to_binary(unsigned long n);int main(void){ unsigned long number; printf("Enter an integer (q to quit):\n"); while (scanf("%lu", &number) == 1) { printf("Binary equivalent: "); to_binary(number); putchar('\n'); printf("Enter an integer (q to quit):\n"); } printf("Done.\n"); return 0;}void to_binary(unsigned long n) /* recursive function */{ int r; r = n % 2; if (n >= 2) to_binary(n / 2); putchar(r == 0 ? '0' : '1'); return;}

 在该程序中，如果r的值是0，to_binary()函数就显示字符'0'；如果r的值是1，to_binary()函数则显示字符'1'。条件表达式r == 0 ? '0' : '1'用于把数值转换成字符。

 下面是该程序的运行示例：

 Enter an integer (q to quit):

 9

 Binary equivalent: 1001

 Enter an integer (q to quit):

 255

 Binary equivalent: 11111111

 Enter an integer (q to quit):

 1024

 Binary equivalent: 10000000000

 Enter an integer (q to quit):

 q

 done.

 不用递归，是否能实现这种用二进制形式表示整数的算法？当然可以。但是由于这种算法要首先计算最后一位二进制数，所以在显示结果之前必须把所有的位数都存储在别处（例如，数组）。第15章中会介绍一个不用递归实现该算法的例子。

 5 递归的优缺点

 递归既有优点也有缺点。优点是递归为某些编程问题提供了最简单的解决方案。缺点是一些递归算法会快速消耗计算机的内存资源。另外，递归不方便阅读和维护。我们用一个例子来说明递归的优缺点。

 斐波那契数列的定义如下：第1个和第2个数字都是1，而后续的每个数字都是其前两个数字之和。例如，该数列的前几个数是：1、1、2、3、5、8、13。斐波那契数列在数学界深受喜爱，甚至有专门研究它的刊物。不过，这不在本书的讨论范围之内。下面，我们要创建一个函数，接受正整数n，返回相应的斐波那契数值。首先，来看递归。递归提供一个简单的定义。如果把函数命名为Fibonacci()，那么如果n是1或2，Fibonacci(n)应返回1；对于其他数值，则应返回Fibonacci(n-1)+Fibonacci(n-2)：

 unsigned long Fibonacci(unsigned n){ if (n > 2) return Fibonacci(n-1) + Fibonacci(n-2); else return 1;}

 这个递归函数只是重述了数学定义的递归。该函数使用了双递归（double-recursion），即函数每一级递归都要调用本身两次。这暴露了一个问题。

 为了说明这个问题，假设调用Fibonacci(40)。这是第1级递归调用，将创建一个变量n。然后在该函数中要调用Fibonacci()两次，在第2级递归中要分别创建两个变量n。这两次调用中的每次调用又会进行两次调用，因而在第3级递归中要创建4个名为n的变量。此时总共创建了7个变量。由于每级递归创建的变量都是上一级递归的两倍，所以变量的数量呈指数增长！在第5章中介绍过一个计算小麦粒数的例子，按指数增长很快就会产生非常大的值。在本例中，指数增长的变量数量很快就消耗掉计算机的大量内存，很可能导致程序崩溃。

 虽然这是个极端的例子，但是该例说明：在程序中使用递归要特别注意，尤其是效率优先的程序。