摘要: 递归算法是C语言程序设计中最经典的算法设计之一.用递归算法编写的程序结构清晰,形式简单,与我们的思维习惯相符合,并且比较容易被理解和阅读;对于一些复杂的数学问题我们也可以用递归的方法去解决,因此递归在计算机科学和数学中都是一个重要的问题求解工具.本文详细介绍了什么是递归算法,通过具体的实例进一步认识及了解递归算法在程序设计中的应用,对递归算法在数学方面的应用进行了简单的探讨.

 关键词:递归算法;程序设计;应用

Recursive Algorithm Research

Abstract: Recursive algorithm is one of the most classic C language program design in algorithm design. Recursive algorithm used in the preparation of the program structure clear, simple form, consistent with our habits of mind, and relatively easy to be understood and reading; for some complex mathematical problems we can also use recursive methods to solve the problem. Therefore, the recursive in computer science and mathematics are an important problem solving tools. This paper introduces the what is a recursive algorithm, through specific examples to further understanding and understanding of the application of recursive algorithm in the program design and the recursive calculation method in mathematics application has carried on the simple discussion.                                                                   Key words: Recursive algorithm; Program design; Application

目    录

摘要. 1

引言 2

预备知识 3

1.递归算法的介绍 3

1.1什么是递归算法 4

1.2递归算法的设计方法 9

2.递归算法的应用 10

2.1 HANOI(汉诺)塔问题 11

2.2斐波那契数列 13

2.3用递归方法求 14

2.4求数组中的最大值 15

结束语 16

参考文献 18

致谢 19

递归算法研究  

引言

算法是对解题方案完整而正确的描述,涉及到了众多的学科,其中包含了算法的设计、分析、实现和应用.自20世纪30年代以来,算法由原来只有数学家们关心、研究的课题,发展成为了在计算机科学领域的有力武器.而在今天算法已经成为计算机科学技术专业及相关专业的重要的基础课程.而递归就是最经典的算法设计之一.递归是计算机科学的一个重要概念,一般采用了递归思想的算法就被称为递归算法. 递归算法是直接或间接调用自己本身的一种算法.

本文所要介绍的递归是一种解决问题的方法即是将问题简化为同样问题的更小的子问题.既递归算法是把一个复杂的问题简化为一个与原问题相似的较为简单的问题来求解.而且递归算法在调用自身的过程中,充分利用了计算机系统的内部功能,把一些与原问题相关且必要的信息进行了保存以及恢复,从而就可以省略了一些求解过程中的细节描述.

在众多数学发展的分支中,计算机科学是其中的一个分支,随着当今社会的发展,人们越来越深的理解到计算机与数学是密不可分的．在参考文献[12]中,有涉及到递归的背景是数学归纳法,作者应用数学归纳法来证明了一个定理的成立,本文中也将对数学归纳法进行一些简单的介绍,通过对数学归纳法的介绍来初步了解递归的思想,从而让读者认识到将数学思想融入到算法构造以及程序设计中是十分重要的.因此我们能够认识到一些数学表达式是可以用递归的方法来定义的,例如数列的问题就可以用递归的方法来求解.在本文中将了解到有关数列的一些程序设计,比如斐波那契数列,求阶乘的问题等等.

为了说明递归方法,我们将研究一些应用和样例问题,从而证明递归方法可以富有成效地解决某些类型的问题.其中的一些例子比较简单,另一些例子则有些复杂.例如求数组中最大值的问题以及汉诺塔问题都是很著名的数学问题,我们可以递归算法对它们进行分析解决.我们知道没有哪一种算法是完美的,递归算法同样也存在一些局限性.比如递归算法占用的内存较大,在这一点上较为浪费.我们要知道并不是所有的语言都支持递归,因此这就需要我们更加深入地去研究递归算法.通过对递归算法的研究来掌握它的原理,再通过一些具体的实例来掌握递归算法的设计与实现并且会熟练运用.