论文总字数：8731字

摘 要

递归是C语言中经常使用的将复杂问题简单解决的方法。递归作为一种算法在程序设计语言中应用广泛，其最基本的特点是自身调用自身，实现层次结构的查询与访问。本文阐述了递归算法的基本概念，成立的三个条件，直接和间接递归分类，通过实例深入分析递归的应用。

关键词：递归，算法，C语言

Abstract：Recursion is often used in C language of the complex simple problem solving method. Recursion as an algorithm is widely used in programming language, its most basic characteristic is its calls itself, realize the query and access of the hierarchical structure. In this paper, the basic concepts of the recursive algorithm, established three conditions, the direct and indirect recursive classification, through examples, this paper analyzes the recursive application.

Keywords：recursion, algorithm, C language

目 录

1 引言………………………………………………………………………… 4

2 递归………………………………………………………………………… 5

2.1 基本概念…………………………………………………………………… 5

2.2 递归分类…………………………………………………………………… 6

3 递归算法效率的改进……………………………………………………… 9

3.1 利用循环消除递归 ……………………………………………………………… 9

3.2 利用栈消除递归 ………………………………………………………………… 11

4 递归算法的应用………………………………………………………… 11

4.1 递归的数学应用………………………………………………………………… 11

4.2 实际生活中的应用…………………………………………………………… 12

结论 ………………………………………………………………………………… 15

参考文献……………………………………………………………………………… 16

致谢 ………………………………………………………………………………… 17

1 引言

现实生活中，如果需要使用计算机实现人们预先安排好的工作，首先要做的是设计出可以完成该工作的方法和步骤，也就是算法，接着再结合算法编写出程序。算法是对求解过程的一种精确描述，一种问题的求解通常有很多种方法可以选择，依据标准首先要看算法的可读性、可靠性、正确性等，其次还要考虑算法本身所需要存储的空间以及时间的消耗。算法设计可以说是一项非常复杂的过程，在实际问题的处理过程中，为了将复杂的问题简单化，设计时通常采用递归的方法。

递归调用是指一个函数在其函数体内调用其本身的过程。递归调用有两种表示方式，分别是直接调用自己和间接调用自己，也就是说在一个函数的执行过程之中出现了直接或者间接调用这个函数本身的行为。我们称前者为直接递归调用，称后者为间接递归调用。

递归的应用是通常是解决有“循环、迭代、嵌套”等特点的计算和判定问题的常用方法。其在实际中也得到了较为宽泛的运用，例如：数学中递归型函数的计算、图和树等数据结构的遍历、操作系统文件系统建立和删除文件操作算法的实现、计算机语言语法及词法分析、游戏软件研发、数据库访问等。递归模型中一些经典实例：如楼梯问题、八皇后问题、Hanoi塔等类似问题的递归解决，充分展现了递归算法的魅力，同时也给研究递归算法提供了很好的素材。

C语言是一门功能强大、应用广泛的计算机编程语言，在应用软件研发、系统开发、I/O控制编程等许多环境中都得到了广泛的使用。C语言代码有函数调用灵活方便、简练高效、变量类型有显著特色、数据类型丰富等优点，使得它在编写递归类程序时得到了更好的应用。

在C语言程序设计中，我们可以使用函数的递归调用，除了主函数以外所有的函数都可以进行递归调用。在此过程中，调用函数也是被调函数。在执行时递归函数会不断的调用其自身。每调用一次便在新的一层继续执行调用程序，如此反复。

在设计递归函数时，一定要避免无止境地重复调用其本身，否则将出现意想不到的问题，所以必须要谨慎处理。为了防止这种重复调用，在设计函数时，需要设置一个终止递归调用的方法。通常的方法是设置某一种条件进行判断，当其满足这个条件时就立即结束递归调用，接着再进行逐层返回操作。

递归模型在C语言程序的基础下，有助于我们高效、合理、安全地利用C语言来实现递归算法，从而更好地解决实际问题^[1-2]。本文综合介绍了有关递归的基本概念，并且结合C语言的有关知识，给出了递归算法在C语言中实现的详细方法和程序源代码。最后结合实例进行分析比较，得出结论。

2 递归

2.1 基本概念

如果要求幂函数的值，其中为实数，为非负整数，一种经典的计算是利用的次重复乘积：

（一共个连乘）

如函数是计算前面个正整数的总和，类似问题可以用重复相加的方法来解决：

，

遇到这样的问题，大家首先想到的是会用它的数学含义直接计算，但并不会想到运用“递归”。对于求，可以这样写，但如果我们运用同样的步骤计算的值，以上的加法过程就会再次重复。实际上，有一种更加简便的计算方法：

利用之前的运算结果加上11便得到了的值，即：

，

这种运算是利用了前次计算出的较小值结果简便了运算，最终得到了答案。我们一般称之为递归过程。现重新讨论幂函数，并在其基础下利用递归编写解决问题的方案。在2的后续幂值求值时，注意到能够利用前次幂值计算下次幂值。例如：

，

，

如果知晓了2的初始幂值（），将前次幂值乘2便可得到后续各幂次的值。由此便得到幂函数的递归定义，即用小的幂次值计算出其他某一值的过程。实数，的值有下式得出：

相同的，能够使用相似的递归定义描述上述函数，它的功能是求前个整数的和。最简单的情况是。通常，能够使用前个整数的和，求解出：

，

一般情况下，如果解决方案是将一个问题分解成多个较小的子问题，并且使用相同的算法解决这些小问题，那么便可以用递归运算。当子问题分解到可以直接解决时，分解进程便可终止。一般称这些子问题为终止条件，递归算法采用的就是“分而治之”的思想^[3-4]。

2.1.2 递归条件

剩余内容已隐藏，请支付后下载全文，论文总字数：8731字