汉扬编程 C语言入门 C语言的递归原理,尾递归,递归的优缺点,以及三个经典案例

C语言的递归原理,尾递归,递归的优缺点,以及三个经典案例

C语言的递归原理,尾递归,递归的优缺点,以及三个经典案例

C语言的递归原理,尾递归,递归的优缺点,以及三个经典案例

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

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

/* recur.c — recursion illustration */#include <stdio.h>void 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#include <stdio.h>long 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 */#include <stdio.h>void 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章中介绍过一个计算小麦粒数的例子,按指数增长很快就会产生非常大的值。在本例中,指数增长的变量数量很快就消耗掉计算机的大量内存,很可能导致程序崩溃。

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

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/cjia/6297.html

请问Visual Basic语言和C语言的区别

批量删除指定字符串(C语言基础)

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部