C语言的函数递归探析
摘要：函数递归其有逻辑性强、结构层次清晰，可以用数学归纳法得出正确结论的优点。对C语言的函数递归进行了论述。
关键词：C语言；函数递归；程序
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<stdio.h>
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(BiTree T,Status(* Vistit)(TelemType e))
{
Status PrintElement(TelemType e)//输出元素e 的值
{
printf(e);
return ok;
}
if(T)递归函数c语言规则
{
if(Visit(T->data))//访问根结点
if(PreOrderTraverse(T->lchild,Visit))//先序遍历左子树
if(PreOrderTraverse(T->rchild,Visit)) return ok;//先序遍历右子树
return ERROR;//空二叉树
}else return ok;
}
在这个函数中，对先序遍历法的顺序和结构一目了然，同样在中序和后序遍历时，也完全可以如法炮制应用函数递归。当然递归函数也有自身缺点，突出缺陷是在调用自身函数时不停开辟存储空间，在占用存储空间的同时又耗费时间，简而言之，大量占用资源，运行速度相对缓慢。在小程序中使用并不会突显其缺点，在大程序中，要谨慎使用，如果使用递归请考虑开辟外存空间来降低内存消耗，同时又降低对运行速度的影响。这一部分，由于笔者的知识结构和篇幅原因，不再深入探讨。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。