c语言函数递归好处,C语言函数递归探析.doc

C语言函数递归探析

C语言函数递归探析

摘 要：函数递归其有逻辑性强、结构层次清晰，可以用数学归纳法得出正确结论的优点。对C语言的函数递归进行了论述。??

关键词：C语言；函数递归；程序??

中图分类号：TP312 文献标识码：A 文章编号：1672-7800(2011)03-0075-02?お?

??

作者简介：於月红(１９83-)，女，浙江台州人，浙江广播电视大学黄岩分校助教，研究方向为计算机科学与技术。

1 函数递归??

所谓函数递归，是指在一个函数中有直接或间接调用函数本身。函数直接递归指函数直接在本函数中调用自身。函数间接递归指本函数调用其它函数，其它函数又调用本函数。直接递归和间接递归图解如图1所示。??

??

如图1所示，递归调用可以说是一种函数循环，程序中循环必须有中止条件，否则就会陷入死循环。所以，递归调用必须有中止条件，只有递归条件满足时才调用自身，否则(即满足中止条件)，函数就不再递归调用。C语言中函数递归有独特的作用。很多时候，巧用函数递归可以解决许多看似复杂难解的问题。??

2 函数递归特征??

那么什么时候函数可以用递归方法呢？递归函数有何特征？本文总结了3条规则：①函数中所需要计算的数值可以通过调用自身得到，所以递归函数必须有返回值;②函数参数值往往是有规律地递增或递减;③必须有中止条件，一般以限定函数参数值或递归函数返回值为中止条件。??

让我们先分析一下简单的递归函数：??求n!??

n!的数学表达式为：n!=n*(n-1)*(n-2)*……*2*1??

当n=1时，值为1??

当n>1时，n!=n*(n-1)!??

这个数学表达式能够满足3条规则，求n!的函数值为n乘以(n-1)!的函数值，函数参数只要递减1设置即可，另外设置中止返回值为1，即最后一个函数的值为1(因为1!=1)。????

该递归函数如下： ??

int f2(int n)??

{??

if(n<1) return 0;??

else if(n= =1) return 1;??

else ??

return n*f(n-1);??

}??

这个问题很简单明了，不再作深入分析。再看另外一题：求∑ n!??

此题的数学表达式为1!+2!+ ……+(n-1)!+n!??

上题已经得知n!可以通过递归函数得解。而这个函数看上去也有相似规律可循。设求此题的函数为f1(n);则当??

n=1时，f1(1)=1??

n=2时，f1(2)=1!+2!=f2(1)+f2(2)=f1(1)+f2(2)??

n=3时，f1(3)=1!+2!+3!=f1(2)+f2(3)??

……??

n=n时，f1(n)=f1(n-1)+f2(n) ??

显然f1(n)需要得到的数值包含f1(n-1)，且函数参为规律的递减，函数中止条件设返回值为1。满足了3个规则，可以用递归解决。??

#include??

long int f1(int n); //函数声明??

long int f2(int n);??

void main()??

{??

int n=20;??

printf(“%ld”,f1(n));??

}??

long int f1(int n)??

{??

if(n= =1) return 1;??

else return f2(n)+f1(n-1); //既调用函数f2，又递归调用函数f1??

}??

long int f2(int n)??

{??

if(n= =1)??

return 1;??

else ??

return n*f2(n-1);//函数f2递归调用 ??

}??

本函数为双层递归调用函数。通过以上例子的分析，不难看出函数递归的优点：逻辑性强，结构层次清晰，可以用数学归纳法得出正确结论。??

3 函数递归应用??

我们在学习数据结构时，发现递归调用经常出现在树和图的生成(也可以说是一种排序问题)和遍历(特殊的查找问题)中，特别是在数据排序和数据查找时被频繁地使用，充分体现了函数递归的优势和作用。??

如在数据结构课程遍历二叉树和线索二叉树时，给出的先序遍历递归函数：??

/*在以下的函数中，Status、TelemType为自定义的数据结构,BiTree为自定义的二叉树数据结构*/??

Status PreOrderTraverse