基于C语言下的递归算法应用研究(2)

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

2 递归

2。1 基本概念

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

（一共个连乘）

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

，

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

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

，

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

，

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

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

，

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

2。1。2 递归条件

使用递归函数调用编写程序时，要注意以下三个方面：

(1) 可以利用递归调用来缩小问题的规模，并且原问题与新问题要具有相同的形式，但是要求处理的对象需要具备一定的规律。换句话说，就是解决问题的方法相同，调用函数的参数要有规律地递减或递增。

(2) 递归函数必须具备一个确定的结束条件，要能够在适当的时候结束递归调用，否则程序会陷入死循环，最终导致系统崩溃。

(3) 有些使用递归算法求解的问题同样可以使用普通循环算法程序来实现，与循环程序相比，递归程序结构简单，逻辑清晰，但预先效率低，所以在有其他算法可以代替的情况下，要尽量避免使用递归算法。文献综述

2。2 递归分类

2。2。1 直接递归

程序设计过程中, 递归调用的含义是函数或过程直接或间接调用自己。子程序直接调用自己，这就被称为直接递归。

例1 利用递归的方法输出斐波那契数列中的前10 个元素。其中：

程序如下：

int fib(int n)

{

if(n==1||n==2) /*基本问题，无需再简化*/

return(1);

else

return(fib(n-1)+fib(n-2)); /*fib(n-1),fib(n-2)的复杂度比fib(n)低*/

}

main()

{ (责任编辑：qin)