C语言中递归函数的教学方法

科技信息　０　ＩＴ论坛０　ＳＣＩＥＮＣＥ＆ＴＥＣＨＮＯＬＯＧＹ　ＩＮＦＯＲＭＡＴＩＯＮ　２０１０年第３５期　

谈Ｃ语言函数的递归和调用　张俊飞　（１．上饶职业技术学院江西上饶３３４１０９；２．华东交通大学江西南昌３３００００）　【摘　要】在一个大问题中包含若干个层次的子问题，并且这些子问题的性质相同只是规模教母问题较小，那么这时候我们可以采用递归和　调用的方式来解决此类问题　【关键词】若干个层次的子问题；递归；调用　０ｕ　ｔｈｅ　Ｃ　ｌａｎｇｕａｇｅ　ａｎｄ　Ｃａｌｌ　ｔｈｅ　Ｒｅｃｕｒｓｉｖｅ　Ｆｕｎｃｔｉｏｎ　【Ａｂｓｔｒａｃｔ］Ｃｏｎｔａｉｎｓ　ａ　ｍａｊｏｒ　ｐｒｏｂｌｅｍ　ｉｎ　ｓｅｖｅｒａｌ　ｌｅｖｅｌｓ　ｏｆ　ｓｕｂ—ｐｒｏｂｌｅｍｓ，ａｎｄ　ｔｈｅｓｅ　ｓｕｂ－ｐｒｏｂｌｅｍｓ　ｏｆ　ｔｈｅ　ｓａｍｅ　ｎａｔｕｒｅ　ｂｕｔ　ｓｍａｌｌｅｒ—ｓｃａｌｅ　ｐｒｏｂｌｅｍｓ　ｇｏｄｍｏｔｈｅｒ，ｔｈｉｓ　ｔｉｍｅ　ｗｅ　ｃａｎ　ｕｓｅ　ｒｅｅｕｒｓｉｏｎ　ａｎｄ　ｃａｌｌｓ　ｔｏ　ｒｅｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ．　【Ｋｅｙ　ｗｏｒｄｓ】Ｓｅｖｅｒａｌ　ｌｅｖｅｌｓ　ｏｆ　ｓｕｂ—ｐｒｏｂｌｅｍｓ；Ｒｅｃｕｒｓｉｖｅ；Ｃａｌｌ　０前言ｐｒｉｎｔｆ（“＼Ｉｌ％ｄ！＝％ｄ　ｋｎ”，ｍ，ｙ）；　，　、要　递　：可以直接（简单递归）或间接　｝’　（间接递归）地自己调自己。主要包括：　（１）ｃ语言函数可以递归调用。　３递归说明　（２）可以通过直接或间接两种方式调用。目前只讨论直接递归调　用。　１　递归条件　采用递归方法来解决问题，必须符合以下三个条件：　１．１可以把要解决的问题转化为一个新问题．而这个新的问题的解　决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或　递减。　１．２可以应用这个转化过程使问题得到解决。　１．３必定要有一个明确的结束递归的条件。　２递归实例　例：使用递归的方法求ｎ！　当ｎ＞ｌ时，求ｎ！的问题可以转化为ｎ　【ｎ一１）！的新问题。　比如ｎ＝５：第一部分：５＊４＊３＊２　１　ｎ　（ｎ一１）！　第二部分：４＊３　２＂１（ｎ—１）　（ｎ一２）！　第三部分：３＊２　１（ｎ一２）（ｎ一３）！　第四部分：２　１（ｎ一３）（ｎ一４）！　第五部分：１（ｎ一５）１　５－５＝０，得到值１，结束递归。　源程序：ｆａｃ（ｉｎｔ　ｎ１　｛ｉｎｔｔ；　ｉｆ（ｎ＝＝１）ｌｌ（ｎ＝＝Ｏ）ｒｅｔｕｒｎ　１；　ｅｌｓｅ　｛ｔ＝ｎ　ｆａｅ（ｎ－１）；　ｒｅｔｕｒｎｔ；　）　）　ｍａｉｎ（）　（ｉｎｔ　ｍ，ｙ；　ｐｒｉｎｆｆ（“Ｅｎｔｅｒ　ｍ：”１：　ｓｃａｎｆ（“％ｄ”，＆ｍ）；　ｉｆ（ｍ（０）ｐｒｉｎｔｔ（“Ｉｎｐｕｔ　ｄａｔａ　Ｅｒｒｏｒ！＼ｎ”）；　ｅｌｓｅ　｛ｙ＝ｆａｃ（ｍ）；　当函数自己调用自己时，系统将自动把函数中当前的变量和形参　暂时保留起来，在新一轮的调用过程中，系统为新调用的函数所用到　的变量和形参开辟另外的存储单元（内存空间）。每次调用函数所使用　的变量在不同的内存空间。　递归调用的层次越多．同名变量的占用的存储单元也就越多。一　定要记住．每次函数的调用，系统都会为该函数的变量开辟新的内存　空间。　当本次调用的函数运行结束时，系统将释放本次调用时所占用的　内存空间。程序的流程返回到上一层的调用点，同时取得当初进入该　层时，函数中的变量和形参所占用的内存空间的数据。　所有递归问题都可以用非递归的方法来解决，但对于一些比较复　杂的递归问题用非递归的方法往往使程序变得十分复杂难以读懂，而　函数的递归调用在解决这类问题时能使程序简洁明了有较好的可读　性；但由于递归调用过程中，系统要为每一层调用中的变量开辟内存　空间、要记住每一层调用后的返回点、要增加许多额外的开销，因此函　数的递归调用通常会降低程序的运行效率。　４程序流程　ｆａｅ（ｉｎｔ　ｎ１，术每次调用使用不同的参数　／　ｆ　ｉｎｔ　ｔ；　每次调用都会为变量ｔ开辟不同的内存空间　，　ｉ“ｎ＝＝１）ＩＩ（ｎ＝＝ｏ），半当满足这些条件返回１　，　ｒｅｔｕｒｎ　１；　ｅｌｓｅ　ｆ　ｔ＝ｎ＊ｆａｃ（ｎ一１）；　每次程序运行到此处会用ｎ一１作为参数再调用　一次本函数　此处是调用点　／　ｒｅｔｎｒｎ　ｔ：　只有在上一句调用的所有过程全部结束时才运行到此　处。　／　）　【参考文献】　［１］占跃华，编．Ｃ语言程序设计．北京邮电大学出版社，２００８　［２］ｈｔｔｐ：／／ｚｈｉｄａｏ．ｂａｉｄｕ．ｃｏｍ／ｑｕｅｓｔｉｏｒｄ３２０５７９５３．ｈｔｍ１．　［责任编辑：曹明明］　（上接第１５６页）演示基本数学概念、定理，有效的避免了传统教学枯　燥乏味的弊端　总之，在高等教育中，高等数学教学不仅是传授给学生基础知识，　更重要的是培养学生的数学素质及逻辑思维能力。作为２ｌ世纪的教　育工作者，我们有责任积极思考、积极探索出行之有效的培养学生能　力的教学方法，以适应新形势的需求。　【参考文献】　［１］同济大学数学教研室，编．高等数学：上、下册［Ｍ］．５版．北京：高等教育出版　社．２００４．　［２］王高峡．再谈美国的微积分教学改革［Ｊ］．数学教育学报，２０００，９（４）：７０．　［责任编辑：张慧］

C语言用递归方法求n阶勒让德多项式的值

勒让德多项式（Legendre Polynomial）是一类重要的正交多项式，经常在物理和数学中出现。在数值计算中，常常需要计算n阶勒让德多项式的值。下面将介绍使用递归方法求解n阶勒让德多项式的值。

首先，我们需要了解勒让德多项式的递归定义。n阶勒让德多项式Pn(x)可以通过以下递推关系定义：

P0(x)=1

P1(x)=x

Pn(x)=((2n-1)xPn-1(x)-(n-1)Pn-2(x))/n

其中P0(x)和P1(x)为已知的初始条件。根据递推关系，我们可以通过计算前面两项的值来递归地计算出Pn(x)的值。

接下来，我们将使用C语言来实现这个递归函数。首先，我们定义一个函数`legendre(int n, double x)`，该函数接受n和x作为参数，并返回n阶勒让德多项式在x处的值。

```c

#include

double legendre(int n, double x)

//初始条件

if (n == 0)

return 1; else if (n == 1)

return x;

//递归计算

return ((2 * n - 1) * x * legendre(n - 1, x) - (n - 1) *

legendre(n - 2, x)) / n;

int main

int n;

double x;

printf("请输入n的值：");

scanf("%d", &n);

printf("请输入x的值：");

scanf("%lf", &x);

double result = legendre(n, x);

printf("n阶勒让德多项式的值为：%lf\n", result);

return 0;

```

在主函数中，首先从用户输入中获取n和x的值，然后调用`legendre`函数计算n阶勒让德多项式在x处的值，最后输出结果。 使用递归方法求解n阶勒让德多项式的值的时间复杂度为O(n)，因为需要递归计算n次。需要注意的是，由于递归层数过多，当n较大时可能会导致栈溢出的问题。

函数的嵌套调⽤与递归（初学者）

1、函数的嵌套调⽤

嵌套定义是在定义⼀个函数时，其函数体内⼜包含另⼀个函数的完整定义。

然⽽，C语⾔不能嵌套定义函数，但可以嵌套调⽤函数，也就是说，在调⽤⼀个函数的过程中，⼜调⽤另⼀个函数。

例:

main()

{

a();

}

a()

{

b();

}

b()

{

return;

}

例题：计算s=2²！+3²！

思路：（1）可编写两个函数，⼀个是⽤来计算平⽅值的函数square，另⼀个是⽤来计算阶乘值的函数factorial。

（2）主函数先调square计算出平⽅值，再在square中以平⽅值为实参，调⽤factorial函数计算其阶乘值，再返回主函数，在循环程序中计算

累加和。

#include

#include

long square(int p);

long factorial(int q);

void main()

{

int i;

long s=0;

for(i=2;i<=3;i++)

{

s=s+square(i);

}

printf("%ld\n",s);

}

long square(int p)

{

int k;

long r;

k=p*p;

r=factorial(k);

return (r);

}

long factorial(int q)

{

long c=1;

int i;

for(i=1;i<=q;i++)

{

c*=i;

}

return c;

}

2、递归在调⽤⼀个函数的过程中⼜出现直接或间接地调⽤该函数本⾝，称为函数的递归调⽤。C语⾔的特点之⼀就在于允许函数的递归调⽤。

例：int flint (x)

{

int y,z;

z=flint(y);

return (2*z);

}

注：递归函数必须要有⼀个退出条件！

例：⽤递归的⽅法求n！

思路：求n！也可⽤递归的⽅法，即5！=4！*5，4！=3！*4……可⽤如下递归公式表⽰：

n=1 (n=0,1)

n*(n-1)! (n>1)

#include

#include

五个数中取三个数递归c语言

在C语言中，如果您想要从五个数中递归地选择三个数，您可以使用一种称为“组合”的概念。组合是从n个不同元素中选择k个元素的组合方式，而不考虑它们的顺序。在C语言中，您可以使用递归函数来计算组合数。

以下是使用C语言实现的一个简单示例，它计算从五个数中选择三个数的组合数。组合数可以用数学上的阶乘表示，组合公式为 C(n, k) =

n! / (k! * (n-k)!), 其中 n! 表示n的阶乘。

```c

#include

// 计算n的阶乘

int factorial(int n) {

if (n == 0) {

return 1;

}

return n * factorial(n - 1);

}

// 计算组合数C(n, k)

int combination(int n, int k) {

if (k > n) {

return 0;

}

return factorial(n) / (factorial(k) * factorial(n - k));

}

int main() {

int nums[5] = {1, 2, 3, 4, 5}; // 五个数

int n = 5; // 总数

int k = 3; // 选择的数目

// 计算从五个数中选择三个数的组合数

int result = combination(n, k);

printf("从五个数中选择三个数的组合数是: %d\n", result);

return 0;

}

```

这个程序首先定义了一个计算阶乘的函数 `factorial`，然后定义了一个计算组合数的函数 `combination`。在 `main` 函数中，我们定义了一个数组 `nums` 并初始化五个数，然后调用 `combination` 函数来计算并打印从这五个数中选择三个数的组合数。