对C语言中递归算法的深入解析

许多教科书都把计算机阶乘和菲波那契数列用来说明递归,非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们,看到阶乘计算第一个想法就是递归。但是在阶乘的计算里,递归并没有提供任何优越之处。在菲波那契数列中,它的效率更是低的非常恐怖。

这里有一个简单的程序,可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如:给出一个值4267,我们需要依次产生字符‘4',‘2',‘6',和‘7'。就如在printf函数中使用了%d格式码,它就会执行类似处理。

我们采用的策略是把这个值反复除以10,并打印各个余数。例如,4267除10的余数是7,但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7'的值。在ASCII码中,字符‘7'的值是55,所以我们需要在余数上加上48来获得正确的字符,但是,使用字符常量而不是整型常量可以提高程序的可移植性。‘0'的ASCII码是48,所以我们用余数加上‘0',所以有下面的关系:

‘0'+ 0 =‘0'
          ‘0'+ 1 =‘1'
          ‘0'+ 2 =‘2'
             ...
从这些关系中,我们很容易看出在余数上加上‘0'就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值,4267/10等于426。然后用这个值重复上述步骤。

这种处理方法存在的唯一问题是它产生的数字次序正好相反,它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。

我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看,函数似乎永远不会终止。当函数调用时,它将调用自身,第2次调用还将调用自身,以此类推,似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是,事实上并不会出现这种情况。

这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展,逐步迫近循环终止条件。递归函数也是如此,它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时,它便不在调用自身。

在程序中,递归函数的限制条件就是变量quotient为零。在每次递归调用之前,我们都把quotient除以10,所以每递归调用一次,它的值就越来越接近零。当它最终变成零时,递归便告终止。

/*接受一个整型值(无符号0,把它转换为字符并打印它,前导零被删除*/

代码如下:

#include <stdio.h>

int binary_to_ascii( unsigned int value)
{
          unsigned int quotient;

  quotient = value / 10;
     if( quotient != 0)
           binary_to_ascii( quotient);
     putchar ( value % 10 + '0' );
}

递归是如何帮助我们以正确的顺序打印这些字符呢?下面是这个函数的工作流程。
1. 将参数值除以10
2. 如果quotient的值为非零,调用binary-to-ascii打印quotient当前值的各位数字
3. 接着,打印步骤1中除法运算的余数

注意在第2个步骤中,我们需要打印的是quotient当前值的各位数字。我们所面临的问题和最初的问题完全相同,只是变量quotient的值变小了。我们用刚刚编写的函数(把整数转换为各个数字字符并打印出来)来解决这个问题。由于quotient的值越来越小,所以递归最终会终止。

一旦你理解了递归,阅读递归函数最容易的方法不是纠缠于它的执行过程,而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误,你的限制条件设置正确,并且每次调用之后更接近限制条件,递归函数总是能正确的完成任务。

但是,为了理解递归的工作原理,你需要追踪递归调用的执行过程,所以让我们来进行这项工作。追踪一个递归函数的执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时,它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量扔保留在堆栈上,但他们被新函数的变量所掩盖,因此是不能被访问的。

当递归函数调用自身时,情况于是如此。每进行一次新的调用,都将创建一批变量,他们将掩盖递归函数前一次调用所创建的变量。当我追踪一个递归函数的执行过程时,必须把分数不同次调用的变量区分开来,以避免混淆。

程序中的函数有两个变量:参数value和局部变量quotient。下面的一些图显示了堆栈的状态,当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色的阴影,表示他们不能被当前正在执行的函数访问。

假定我们以4267这个值调用递归函数。当函数刚开始执行时,堆栈的内容如下图所示:

执行除法之后,堆栈的内容如下:

接着,if语句判断出quotient的值非零,所以对该函数执行递归调用。当这个函数第二次被调用之初,堆栈的内容如下:

堆栈上创建了一批新的变量,隐藏了前面的那批变量,除非当前这次递归调用返回,否则他们是不能被访问的。再次执行除法运算之后,堆栈的内容如下:

quotient的值现在为42,仍然非零,所以需要继续执行递归调用,并再创建一批变量。在执行完这次调用的出发运算之后,堆栈的内容如下:

此时,quotient的值还是非零,仍然需要执行递归调用。在执行除法运算之后,堆栈的内容如下:


不算递归调用语句本身,到目前为止所执行的语句只是除法运算以及对quotient的值进行测试。由于递归调用这些语句重复执行,所以它的效果类似循环:当quotient的值非零时,把它的值作为初始值重新开始循环。但是,递归调用将会保存一些信息(这点与循环不同),也就好是保存在堆栈中的变量值。这些信息很快就会变得非常重要。

现在quotient的值变成了零,递归函数便不再调用自身,而是开始打印输出。然后函数返回,并开始销毁堆栈上的变量值。

每次调用putchar得到变量value的最后一个数字,方法是对value进行模10取余运算,其结果是一个0到9之间的整数。把它与字符常量‘0'相加,其结果便是对应于这个数字的ASCII字符,然后把这个字符打印出来。

输出4:

接着函数返回,它的变量从堆栈中销毁。接着,递归函数的前一次调用重新继续执行,她所使用的是自己的变量,他们现在位于堆栈的顶部。因为它的value值是42,所以调用putchar后打印出来的数字是2。

输出42:

接着递归函数的这次调用也返回,它的变量也被销毁,此时位于堆栈顶部的是递归函数再前一次调用的变量。递归调用从这个位置继续执行,这次打印的数字是6。在这次调用返回之前,堆栈的内容如下:

输出426:

现在我们已经展开了整个递归过程,并回到该函数最初的调用。这次调用打印出数字7,也就是它的value参数除10的余数。

输出4267:


然后,这个递归函数就彻底返回到其他函数调用它的地点。
如果你把打印出来的字符一个接一个排在一起,出现在打印机或屏幕上,你将看到正确的值:4267
使用递归一定要有跳出的条件:
这是一个最简单的递归, 不过它会一直执行, 可用 Ctrl+C 终止.


代码如下:

#include <stdio.h>
void prn(int num) {
    printf("%d/n", num);
    if (num > 0) prn(--num); 
}
int main(void)
{
    prn(9);
    getchar();
    return 0;
}

代码如下:

实例: 翻转字符串
#include <stdio.h>
void revers(char *cs);
int main(void)
{
    revers("123456789");
    getchar();   
    return 0;
}
void revers(char *cs)
{
    if (*cs)
    {
        revers(cs + 1);
        putchar(*cs);
    }
}

代码如下:

实例: 阶乘
#include <stdio.h>
int factorial(int num);
int main(void)
{
    int i;
    for (i = 1; i <= 9; i++)
    printf("%d: %d/n", i, factorial(i));
    getchar();   
    return 0;
}
int factorial(int num)
{
    if (num == 1)
        return(1);
    else
        return(num * factorial(num-1));
}

代码如下:

实例: 整数到二进制
#include <stdio.h>
void IntToBinary(unsigned num);
int main(void)
{
    IntToBinary(255); /* 11111111 */
    getchar();
    return 0;
}
void IntToBinary(unsigned num) {
    int i = num % 2;
    if (num > 1) IntToBinary(num / 2);
    putchar(i ? '1' : '0');
//    putchar('0' + i);  /* 可代替上面一句 */
}

代码如下:

剖析递归:
#include <stdio.h>
void prn(unsigned n);
int main(void)
{
    prn(1);
    getchar();
    return 0;
}
void prn(unsigned n) {
    printf("%d: %p/n", n, &n);  /* A */
    if (n < 4)
        prn(n+1);               /* B */
    printf("%d: %p/n", n, &n);  /* C */
}

例输出效果图:


分析:
程序运行到 A, 输出了第一行.
此时 n=1, 满足 < 4 的条件, 继续执行 B 开始了自调用(接着会输出第二行); 注意 n=1 时语句 C 还有待执行.
...如此循环, 一直到 n=4, A 可以执行, 但因不满足条件 B 执行不了了; 终于在 n=4 时得以执行 C.
但此时内存中有四个函数都等待返回(分别是 n=1、2、3、4 时), 咱们分别叫它 f1、f2、f3、f4.
f4 执行 C 输出了第五行, 函数返回, 返回给 f3(此时 n=3), f3 得以继续执行 C, 输出了第六行.
f3 -> f2 -> 继续 C, 输出了第七行.
f2 -> f1 -> 继续 C, 输出了第八行, 执行完毕!

如此看来, 递归函数还是很费内存的(有时不如直接使用循环), 但的确很巧妙.

(0)

相关推荐

  • C语言实现图的搜索算法示例

    本文实例讲述了C语言实现图的搜索算法.分享给大家供大家参考,具体如下: 在游戏中,常常遇到路径规划问题,用到图的相关算法,我们以简单图来学习. 图通常有两种表示方式,矩阵和邻接表.矩阵表示简单,运算快,但当矩阵是稀疏矩阵的时候就存在空间浪费的问题,并且效率也会下降,而邻接表节约空间,并且由于边是连续访问,时间效率也比较高.在本文中,我们将以邻接表来表示图. #include<queue> #include<stack> using namespace std; struct SE{

  • C++实现图的邻接表存储和广度优先遍历实例分析

    本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 0 2 0 3 2 3 2 4 1 4 输入结束(此行不必输入) 注:0 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2表示该图的第0个顶点和第2个定点有边相连,如上图中的a->c所示       2 3表示该图的

  • C语言实现魔方阵算法(幻方阵 奇魔方 单偶魔方实现)

    例如三阶魔方阵为: 魔方阵有什么的规律呢? 魔方阵分为奇幻方和偶幻方.而偶幻方又分为是4的倍数(如4,8,12--)和不是4的倍数(如6,10,14--)两种.下面分别进行介绍. 2 奇魔方的算法 2.1 奇魔方的规律与算法 奇魔方(阶数n = 2 * m + 1,m =1,2,3--)规律如下: 数字1位于方阵中的第一行中间一列:数字a(1 < a  ≤ n2)所在行数比a-1行数少1,若a-1的行数为1,则a的行数为n:数字a(1 < a  ≤ n2)所在列数比a-1列数大1,若a-1的列

  • c语言实现冒泡排序、希尔排序等多种算法示例

    实现以下排序 插入排序O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 希尔排序 O(n^1.25) 1.插入排序 O(n^2) 一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下:⒈ 从第一个元素开始,该元素可以认为已经被排序⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置⒋ 重复步骤3,直到找到已排序的元素

  • C语言使用回溯法解旅行售货员问题与图的m着色问题

    旅行售货员问题 1.问题描述: 旅行售货员问题又称TSP问题,问题如下:某售货员要到若干个城市推销商品,已知各城市之间的路程(或旅费),他要选定一条从驻地出发,经过每个城市一遍最后回到驻地的路线,使总的路线(或总的旅费)最小.数学模型为给定一个无向图,求遍历每一个顶点一次且仅一次的一条回路,最后回到起点的最小花费. 2.输入要求: 输入的第一行为测试样例的个数T( T < 120 ),接下来有T个测试样例.每个测试样例的第一行是无向图的顶点数n.边数m( n < 12,m < 100 )

  • 详解约瑟夫环问题及其相关的C语言算法实现

    约瑟夫环问题 N个人围成一圈顺序编号,从1号开始按1.2.3......顺序报数,报p者退出圈外,其余的人再从1.2.3开始报数,报p的人再退出圈外,以此类推.   请按退出顺序输出每个退出人的原序号 算法思想 用数学归纳法递推. 无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达O(nm),若nm非常大,无法在短时间内计算出结果.我们注意到原问题仅仅是要求出最后的胜利者的序号,而不是要读者模拟整个过程.因此如果要追求效率,就要打破常规,实

  • c语言 汉诺塔算法代码

    复制代码 代码如下: #include<stdio.h> void move(char a,char b) {     printf("%c->%c\n",a,b); } void han(int n,char a,char b,char c) {     if(n>0)     {         han(n-1,a,c,b);         move(a,b);         han(n-1,c,b,a);     } } int main() {   

  • C++实现图的邻接矩阵存储和广度、深度优先遍历实例分析

    本文实例讲述了C++实现图的邻接矩阵存储和广度.深度优先遍历的方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 1 0 2 1 0 3 1 2 3 1 2 4 1 1 4 1 输入结束(此行不必输入) 注:0 1 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2 1表示该图的第0个顶点和第2个定点有边相连,如上图中的a

  • C语言位图算法详解

    本文详细讲述了位图算法的定义与C语言实现方法,分享给大家供大家参考之用.具体如下: 位图法定义: 位图法就是bitmap的缩写,所谓bitmap,是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况.通常是用来判断某个数据存不存在的. 例如,要判断一千万个人的状态,每个人只有两种状态:男人,女人,可以用0,1表示.那么就可以开一个int数组,一个int有32个位,就可以表示32个人.操作的时候可以使用位操作.   数据结构: unsigned int bit[N]; 在这个数组

  • C语言实现图的遍历之深度优先搜索实例

    DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法.分享给大家供大家参考.具体方法如下: #include <iostream> #include <algorithm> #include <iterator> using namespace std; #define MAX_VERTEX_NUM 10 struct Node { int adjvex; struct Node *next; int info; }; typ

  • C语言经典算法例题求100-999之间的“水仙花数

    题目:打印出所有的 "水仙花数 ",所谓 "水仙花数 "是指一个三位数,其各位数字立方和等于该数本身. 例如:153是一个 "水仙花数 ",因为153=1的三次方+5的三次方+3的三次方. 实现代码如下 #include <iostream> #include <Cmath> using namespace std; /* 求100-999之间的水仙花数 */ int main() { int number,hun,ten

  • C语言实现的排列组合问题的通用算法、解决方法

    尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也

随机推荐