C语言中递归的分析及应用作者：杨新宇兰全祥来源：《电脑知识与技术》2020年第22期摘要：函数以及函数的递归调用是学习C语言必须要掌握的内容，且递归作为经典的算法思想被广泛应用于程序设计中。
从应用场景的角度出发，对C语言中递归的定义、特征以及适用场景进行了探讨，并对这些适用场景进行分析和举例。
最后，分析并探讨了递归的优缺点，并给出了递归的优化方法和将递归转换为非递归的方法。
关键词：C语言;递归;应用;非递归化中图分类号：TP311 文献标识码：A文章编号：1009-3044（2020）22-0237-02开放科学（资源服务）标识码（0SID）：1 背景随着时代的进步以及计算机编程语言的不断发展，从20世纪80年代传承至今的C语言始终是各大高校首选的计算机编程语言。
世界编程语言排行榜（ TIOBE）中C语言的热门程度自2002年至今始终稳居前三[1]。
由此可见，C语言的重要程度以及热门度。
另外，模块化设计是所有程序设计必须遵循的设计原则，而函数就是C语言模块化的重要组成部分[2]。
C语言函数以及函数的使用是学习C语言必须要掌握的内容。
递归作为经典的函数使用方法，应用范围广泛，是函数中不可或缺的重要内容，也是作为一个开发者应该掌握的重要算法之一。
2 遞归的概述2.1 定义张长海等人认为在定义一个函数时，若在定义函数的内部又出现对函数本身的调用，则称该函数是递归的或递归定义的[3];谭浩强等人认为递归就是函数自己直接或间接地调用自身的过程[4];丁雪晶认为递归就是把要解决的问题分解成与原问题有相同解法，且规模较小的问题，直到遇见终止条件[5]。
综上，笔者认为函数的递归就是直接或间接地调用自身进行人栈操作，遇到边界之后再进行出栈的过程，且在人栈过程中，由原始问题分解为的子问题始终向边界靠拢。
2.2 特征从上述定义可得出递归的以下特征：1）函数总是直接或者间接的调用自身;2）函数的递归必须有结束条件（即问题的边界），且在调用的过程中始终向某一个边界靠近;3）递归过程是一个不断人栈和出栈的过程。
2.3 应用场景递归的本质是将关于n的问题转化为同类解法的关于m的问题，其中n和m是问题的规模，且m比n更靠近问题的边界（递归结束条件）。
通过对常见递归应用的分析，笔者将递归应用场景分为三类：1）数据的初始化是递归的。
2）数据的结构是递归的。
3）问题的求解是递归的。
3 递归的案例根据上述对函数递归的定义、特征以及应用场景的总结，本文对上述递归的应用场景进行分析和举例。
3.1 数据的初始化是递归的示例：Fibonacci数列（兔子数列）描述：形如1，1，2，3，5，8，13，21I.….的数列被称为Fibonac-Cl数列，即第n个数等于第n-l个数和第n-2个数之和。
分析：根据上述定义，对数列进行数学归纳可得出数学递推公式。
根据分析可知，Fibonacci数列是典型的数据的初始化是递归的例子，即要对n进行初始化，必须知道n-l和n-2的值。
初始化Fibonacci数列的关键代码如下：int Fib（int n）{if（n ==1¨n==2）{return 1;）elsefreturn Fib（n-I）+Fib（n-2）;））3.2 数据的结构是递归的示例：二叉树描述：二叉树是结点的有限集合，该集合或者为空集，或者是由一个根和两棵互不相交的称为该根的左子树和右子树的二叉树组成[6]。
分析：由定义可知，一个根结点可能存在左子树和右子树，且左子树和右子树又是一颗更小的二叉树。
因此，二叉树从数据结构上来看是递归的，如图1所示，A的左子树、A的右子树以及C 的左子树都是一颗二叉树，且无论是二叉树的初始化还是遍历都能用递归来解决。
构造二叉树的关键代码如下：typedef struct BiTNode{char data; struct BiTNode，*rchild，*rchild;}BiTNode，a：BiTree;void CreateBiTree（BiTiree *T）{char c;scanf（”%c”，&c）;i“c==7#7）{*T=NULL;】elsef*T= （BiTNode*）new BiTNode;（*T）->data=c;CreateBiTree（&（*T）->lchild）;CreateBiTree（&（*T）->rchild）;）】由代码可以看出，在二叉树的构造中，输入根节点数据之后还需要递归调用CreateBiTree 函数对其左右子树进行构造，即要成功构造一颗二叉树，需要先构造出其左、右子树。
另外，二叉树的遍历也可采用递归的方法实现先序遍历、中序遍历与后序遍历。
3.3 问题的求解是递归的示例：汉诺塔描述：现有A，B，C三根柱子，在A柱有n个从上到下面积依次增大的盘子，现在想把A柱这n个盘子移动到C柱，但规定每一次只能移动一个盘子，且三根柱子的盘子始终都保持着面积大的盘子在下，面积小的盘子在上，问盘子移动的步骤。
分析：如果我们能先将A柱上层的n-1个盘子移动到B柱，然后将A柱的第n个盘子移动到C柱，再将B柱的n-1盘子移送到C柱，那么就完成了将A柱的n个盘子移动到C柱的操作。
也就意味着，我们将n的问题Q（n）分解为了Q（n-1）+l+Q（n-1）的问题。
从上述分析可以看出，汉诺塔是典型的问题的解是递归的。
即如果能解决Q（n-1）的问题，那么就能解决Q（n）的问题。
汉诺塔的关键代码如下：void hanoi（int n， char A，char B， char C）（if（n==1 1printf（”%c→%c＼n”，A，C）;elsefhanoi（ n-l，A，C，B）;printf（”%c→%c＼n”，A，C）;hanoi（ n-1，B，A，C）;在解决问题的过程中，原问题在不断地减小规模，且总是向边界不断的靠近。
4 递归的分析4.1 优点通过对递归的特征以及应用场景的分析，可以总结出以下优点：1）函数的递归调用可以使问题的解更直观、思路更清晰。
比如红黑树的插入、删除等。
2）使用遞归函数可以大幅度减少函数的代码量，使代码更简洁。
3）可以更便于使用数学方法证明算法的正确性、计算算法的时间与空间复杂度，也能更方便地将问题所对应的递归形式函数转化为相应的递归算法程序，如斐波拉契数列。
4.2 缺点函数的递归调用虽然在程序设计上更便捷，但是也存在着许多无法避免的缺点，如：时间复杂度高。
如Fibonacci数列的时间复杂度为0（211），是呈指数级增长的。
假设计算机Is可以计算出Fib（40），那么，当n=100时，计算机计算出Fib（100）所需要的时间大约需要16，000，000，000年，这个计算所需要的时间时不可等待的。
1）空间复杂度高。
递归是一个不断压栈和出栈的过程，在输入的数据量比较大的时候，很可能发生栈溢出。
如在二叉树的遍历中，若二叉树的深度较大时，递归调用时将进行大量压栈操作，致使空间效率大大降低，造成栈溢出。
4.3 递归的优化与非递归化为了解决函数递归调用可能会发生的空间爆炸和时间爆炸问题，可以考虑对递归进行优化和非递归化。
1）将递归与分治法相结合。
分治法的基本思想是将一个规模为n的问题费解为k个规模较小的子问题，这些子问题相互独立且与原问题相同，然后再将各个子问题的解合并，进而得到原问题的解。
如Fibonacci数列使用数学归纳法可以得证：因此采用矩阵与分治和递归相结合的方法计算Fibonacci数列，其时间复杂度为O （logn），大大提高了算法的效率。
2）将递归与动态规划相结合。
动态规划也是对原问题进行分解，但是所得到的子问题往往不是相互独立的[9]。
如Fibo-naccl数列使用数组逐个保存Fibonacci数列值，将问题转化为：x[n]=x[n- 1]+x[n -2]先记录x[n一1]和x[n一2]的值，然后通过已解决的子问题来求解原问题的解，其时间复杂度为O（n）。
关键代码如下：static int rec[100]{-1）;long long f'ib（int n）（iffn==01return 1：iffn==11return 1：if（rec[n]_=-1）rec[n]= fib（n-l）+ fib（n-2）;return rec[n];】3）将递归算法非递归化。
将递归算法转化为非递归算法还可以利用栈模拟、循环、递推等来进行转化[7-8]。
这样算法的执行效率与空间利用率将会大大提高。
5 结束语函数的递归在程序设计中是很常见的，所有使用递归算法来解决的问题都必然要具有收敛性（即问题的求解存在结束条件或者是边界），若满足这一个要求的源问题，就可以考虑用递归的方法来解决。
但是在实际开发过程中，需要考虑递归所带来的时间复杂度以及空间复杂度等问题，当时间复杂度过高时，则应考虑将递归算法进行非递归化。
在解决问题的过程中，是否采用递归算法，使用什么样的非递归转化方法，可以根据实际的情况进行选择。
参考文献：[1]兰全祥.地方应用型本科院校C语言课程改革探讨[J].西昌学院学报（自然科学版），2017，31（4）： 100-102，123.[2]袁凤玲.软件工程思想在程序设计公共课教学中的应用[J].辽宁科技学院学报，2015，17（1）： 44-45.[3]张长海，陈娟.C程序设计[M].北京：高等教育出版社，2004.[4]谭浩强.C程序设计[Ml.4版.北京：清华大学出版社，2010.[5]丁雪晶.C语言递归函数教学的设计与探讨[Jl.电脑知识与技术，2018，14（16）： 150-152.[6]陈慧南.数据结构与算法：C++语言描述[M].北京：高等教育出版社，2005.[7]孟林，李忠.递归算法的非递归化研究[J].计算机科学，2001，28（8）： 96-98.[8]汤亚玲.递归算法设计及其非递归化研究[J].计算机技术与发展，2009，19（11）： 85-88，93.【通联编辑：谢媛媛】基金项目：攀枝花学院大学生创新创业项目（项目编号：2019cxcy072）作者简介：杨新宇（2001-），男，四川巴中人，主要研究方向为算法设计与分析;兰全祥（1990-），通讯作者，男，四川攀枝花人，讲师，硕士，主要研究方向为软件开发。