语言递归

语言递归（共7篇）

语言递归 篇1

递归,作为C语言最经典的算法之一,是一种非常有用的程序设计方法。虽然用递归算法编写的程序结构清晰,具有很好的可读性,还往往使某些看起来不易解决的问题变得容易解决。但在递归函数中,由于存在着自调用过程,程序控制反复进入其自身,使程序的分析设计有一定困难,致使很多初学者往往对递归迷惑不解,也在这上面花了不少的时间,却收效甚微。那么,究竟什么是递归?怎么实现递归呢?

所谓递归,简而言之就是在调用一个函数的过程中又直接或间接地调用该函数本身,以实现层次数据结构的查询和访问。在函数中直接调用函数本身,称为直接递归调用。在函数中调用其它函数,其它函数又调用原函数,这就构成了函数自身的间接调用,称为间接递归调用。

而采用递归方法来解决问题,必须符合以下三个条件:

1、可以把要解决的问题转化为一个新问题,而这个新的问题的解决方法仍与原来的解决方法相同,只是所处理的对象有规律地递增或递减。

说明:解决问题的方法相同,调用函数的参数每次不同(有规律的递增或递减),如果没有规律也就不能适用递归调用。

2、可以应用这个转化过程使问题得到解决。

说明:使用其他的办法比较麻烦或很难解决,而使用递归的方法可以很好地解决问题。

3、必定要有一个明确的结束递归的条件。

说明:一定要能够在适当的地方结束递归调用。不然可能导致系统崩溃。

好知道是这样以后;我们来写一个众多教材上的程序:使用递归的方法求n!。当n>1时,求n!的问题可以转化为n*(n-1)!的新问题。比如n=4:

第一部分:4*3*2*1n*(n-1)!

第二部分:3*2*1(n-1)(n-2)!

第三部分:2*1 (n-2)(n-3)!

第四部分:1(n-4)!4-4=0,得到值1,结束递归。我给的源程序如下:

可以看到,加上两条printf()和getchar()语句后,可以察看各级调用及其中间答案,很清楚的看到程序的执行过程。运行结果如图1所示,当主函数第一次调用fac0函数的时候,由于n=4不等于0和1,并不立即返回结果1,而是执行c=n*fac(n-1),用实参n-1 (值为3)调用fac()函数自己,即递归调用fac(3)。于是进入第二层调用fac(),这时也没有得出结果,继续用实参n-1(值为2)调用fac()函数自己。同样经过第三层调用后进入第四层调用,这时候n=1,算出1!=1,满足结束递归的条件,然后把得出的结果1返回给第三次调用的fac函数,得出2*1!=2,然后把结果2返回给第二次调用的fac函数,得出3*2!=6,最后第一次调用的fac函数根据第二次调用的返回值算出4!=4*3!=4*6=24,结束整个递归调用,得出最终结果并输出。

我们做事情,一般都是从头开始的,而递归却是从末尾开始的。比如上面的函数,当n>1的时候,就只能求助于n-1,而(n-1)1时,就求助于n-2,然后……直到(n-k)=1时,函数fac终于有了返回值1了,它再从头开始计算,然后一直算到n为止。所以说,递归简直就是一个数学模型,它的工作过程就是自己调用自己。以下是几点对递归的说明:

1、当函数自己调用自己时,系统将自动把函数中当前的变量和形参暂时保留起来,在新一轮的调用过程中,系统为新调用的函数所用到的变量和形参开辟另外的存储单元(内存空间)。每次调用函数所使用的变量在不同的内存空间。

2、递归调用的层次越多,同名变量的占用的存储单元也就越多。一定要记住,每次函数的调用,系统都会为该函数的变量开辟新的内存空间。

3、当本次调用的函数运行结束时,系统将释放本次调用时所占用的内存空间。程序的流程返回到上一层的调用点,同时取得当初进入该层时,函数中的变量和形参所占用的内存空间的数据。

4、在开发过程中使用printf()和getchar()可以看到执行过程,并且可以在发现错误后停止运行。

很多人说所有递归问题都可以用非递归的方法来解决,能不用递归就不用递归。但是对于一些比较复杂的递归问题用非递归的方法往往使程序变得十分复杂难以读懂,而函数的递归调用在解决这类问题时能使程序简洁明了有较好的可读性,因此很多问题用递归可很容易解决。同时由于递归调用过程中,系统要为每一层调用中的变量开辟内存空间、要记住每一层调用后的返回点、要增加许多额外的开销,因此函数的递归调用通常会降低程序的运行效率(在许多情况下,速度的差别不太明显)。

我曾经碰到过这样一个动物繁殖问题:若一头小母牛,从出生起第四个年头开始每年生一头母牛,按此规律,第n年时有多少头母牛?

如果不用递归函数来做,每当母牛到第4岁的时候才会生下一头小母牛,所以,每年增加的新的1岁小母牛都是上一年3岁的母牛加上4岁的母牛生下数量之和,分析过程如图2所示,给出程序如下:

程序虽然简短,但是可读性太差,不易理解。那么如果用递归函数求此问题呢?

我们先写出函数表达式:f(n)=f(n-1)+f(n-3)

为什么f(n)=f(n-1)+f(n-3)呢,请看:

f(n)-f(n-1)=f(n-3)

因为第n年要比n-1年多的牛,都是大于三岁的牛生的小牛,而f(n-3正是那些在n年大于三岁的牛,然后它们在第n年生下相同数量的小牛。源代码如下:

运行结果如图3所示:

可见,递归函数的主要优点是可以把算法写的比使用非递归函数时更清晰更简洁,而且某些问题,特别是与人工智能有关的问题,更适宜用递归方法。递归的另一个优点是,递归函数不会受到怀疑,较非递归函数而言,某些人更相信递归函数。编写递归函数时,必须在函数的某些地方使用if语句,强迫函数在未执行递归调用前返回。如果不这样做,在调用函数后,它永远不会返回,造成无穷递归。在递归函数中不使用if语句,是一个很常见的错误。此外,象汉诺塔问题就只能靠递归才能解决,但是现实中很多问题都是比较简单的,没有象汉诺塔那么复杂,我们只要会用递归编程来为我们解决一些问题就行了,所以就不必深究了。

参考文献

[1]谭浩强:《C语言程序设计》,清华出版社,2008年11月第2版。

语言递归 篇2

计算阶乘n! = n*(n-1)*...*1.

如果利用递归思想的话，我们可以发现factorial（n） = n！=n*factorial（n-1）；这就是一个递归的形式。

[cpp]

int factorial(int n)

{

if(n==1)

return 1;

else

return n*factorial(n-1);

}

代码的第二行与第三行就是处理的基准情形。这是由于这个基准情形，使得程序不会变为死循环而不停的递归，直至耗尽内存空间。

当然上面的情形也可以用迭代的方法来解决

[cpp]

int factorial(int n)

{

int element = 1;

int i;

for(i=2;i

element *=i;

}

递归和迭代这两种方法都可以解决上面的问题，而且在数学上的表示是一致的，那么这两者是否等价呢？答案肯定是不等价的，

一般来说递归的时间与空间消耗要大于迭代，但是递归的形式非常简单，代码形式非常优美。迭代相当于一个从前向后的过程，而递归是一个从后向前再向后的过程。

递归和迭代一般情况下是可以相互转换的，但是有些情况下，用迭代来替代递归是相当痛苦的，比如说数据结构的定义等等。

递归一般有如下几点需要注意：

1） 基准情形：也就是递归停止的标志，这是递归所不能少的

2） 不断推进：每一次递归，都要使问题朝着基准情形前进，否则是无法结束递归的

3） 设计法则：假设所有的递归调用都能运行

基于数据结构的程序递归算法设计 篇3

关键词：递归；数据结构；算法实现

中图分类号：TP311.11 文献标识码：A文章编号：1007-9599 (2011) 08-0000-01

Program Recursive Algorithm Design Based on Data Structure

Yang Jun,Xiong Bicheng,Zhan Hongyun

(Jiangxi Tourism Business Vocational College,Nanchang330100,China)

Abstract:Recursive programming is an important approach,but in the teaching process has been a difficulty.From the methodological point of view of recursive program design make a systematic exposition,introduces the general recursive programming steps and methods,and how to divide and conquer and backtracking through strategies such as recursive programming.

Keywords:Recursion;Data structure;Algorithm

一、递归程序的实现策略

（一）分治。若操作对象可定义成由若干结构相同但规模更小的部分组成，则对原对象的操作可递归分解到其各组成部分上分别进行，如此递归分解直到不可再分时停止，此类求解策略称为分治。根据分治策略很容易得到相应的递归关系定义和递归边界，从而构造出具体的递归函数。

如非空的二叉树可看作为由根结点、根节点的左子树以及根结点的右子树三部分组成，每一部分又都是一颗树。如右图所示二叉树T可看作由根节点A、结点B、C构成的左子树和结点D、E、F构成的右子树组成。欲设计递归函数NodeCount（T）求二叉树T的结点总数，显然T的结点数是T的左子树结点数与T的右子树结点数之和再加1，这实际就是递归关系的定义：

int NodeCount（BiTree T）

{int n；

if（T==NULL）

n=0；

else

n=NodeCount（T->lchild）+NodeCount（T->rchild）+1；

return n；}

（二）回溯。回溯也是一种问题求解策略，通常指让计算机从某种可能的情况出发自动向前进行搜索，碰到符合的情况就输出或者保存起来，在一条路径上走到“尽头”后就回到原来的岔路口选择一条以前没有走过的路重新向前进行探测，直到找到解或者走完所有路径为止。回溯具体编程实现时通常都用递归：“向前进行搜索”对应递归调用，“尽头”对应递归边界。

比如N皇后问题。题目是说，一个N*N的国际象棋棋盘上主放置N个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行、同一列、同一条斜线上，要求输出所有可能的摆放方案。其实，题目就是要找出所有可能的合法情况，可以考虑用回溯法求解。

让计算机逐行前进，每行摆放一个棋子，若合法则前进到下一行。为此可设递归函数void NQueens（int arr[N][N]，int i）；第一个参数代表棋盘，第二个参数代表目前标号为0的行到标号为i-1的行已经各有一个棋子，且符合规则要求。递归函数第一次被调用时时形参i值应为0，函数体内递归调用语句应为NQueens（arr，i+1）。至此递归关系定义已经找到，但还有一个问题，即递归何时停止或者说计算机前进过程中如何判断是否“走到尽头”。分析可见共有两种情况：其一，当前行下完一个棋子后出现了非法情况，如同一列或同一斜线上出现了多个皇后，此时应抹掉该行所下棋子，在其右侧重新下一个棋子再重新检查；其二，当前行下完一个棋子后仍然合法，但恰巧当前行是最后一行，这实际意味着已经得到了一种合法的摆放方案，此时应输出该方案，之后抹掉该行所下棋子，在其右侧下一个棋子重新检查。由上述递归边界和递归关系定义可构造递归函数如下：

void NQueens（int arr[N][N]，int i）

{for（int j=0；j

{arr[i][j]=1；

if（Verify（arr，i）==0）{arr[i][j]=0；continue；}

else if（i==N-1）{PrintChessBoard（arr）；arr[i][j]=0；continue；}

else{NQueens（arr，i+1）；arr[i][j]=0；continue；}}}

通过上例可见，回溯法的主要特点是递归结束的条件在搜索的最后一步，关键是找到递归边界条件

二、递归存在的问题

使用递归进行程序设计思路清晰、代码简洁，但递归调用过程中，每一次发生调用系统都要将返回地址、局部变量等信息入栈保存，因此，递归程序的运行效率较低，而且递归次数过多还容易造成栈溢出。此外，尤其要避免重复递归调用的现象发生。比如求Fibnacci数列的第n项可通过递归函数实现：

long f（int n）

{int r；

if（n==1||n==0）r=1；

else r=f（n-1）+f（n-2）；

return r；}

假设n=4则递归执行过程中发生的递归调用如图3所示，可见n=4时f（1）已经被重复调用了3次。在Core 2CPU T5500、内存1G的机器上进行测试，计算f（40）约需20.374秒的时间，其主要原因在于计算f（40）时f（1）会被重复调用165580141次；而计算f（50）更是需要40多分钟！

参考文献：

[1]谭浩强.C程序设计[M].北京:清华大学出版社,2005,7

[2]王晓东.计算机算法设计与分析[J].北京:电子工业出版社,2007,5

C语言中递归调用的教学探析 篇4

函数是C语言中一个非常重要的部分, 所有程序都是由函数组成的, 如果没有掌握函数, 就不可能掌握C语言。在函数中, 递归函数是一类比较难以掌握的问题, 学生在学习过程中往往对这类程序的执行过程不了解, 对递归问题的认识不清楚, 难以写出正确的递归程序。针对递归问题的教学, 人们在实践中做了很多有益的探讨, 也有一些教材对这一问题做了较为细致的分析。但以上工作大都以汉诺塔问题进行讲解, 而汉诺塔问题本身较为复杂, 很多学生一下难以掌握该程序的执行过程。本文从实际教学出发, 首先分析递归的基本条件, 从简单程序开始分析, 写出递归程序, 然后一步一步分析递归程序的执行过程, 让学生对递归有更深入的理解, 然后写出递归程序的一般结构, 最后分析汉诺塔问题, 让学生自己写出程序。

二、递归的基本条件

一般情况下采用递归方法来解决问题, 必须符合以下三个条件:

1、可以把要解决的问题转化为一个新问题, 而这个新的问题的解决方法仍与原来的解决方法相同, 只是所处理的问题的规模有规律地递减。也就是说解决问题的方法相同, 调用函数的参数每次不同 (有规律地递减) , 如果没有规律也就不能运用递归方法求解。

2、每个子问题必须比原来问题的规模更小, 即使小一号也行, 如果能够迅速减小规模更好。

3、必定要有一个明确的结束递归的条件。当问题的规模达到一定程度时 (一般的时候应该是规模足够小) , 问题的解是已知的, 在这个地方能结束递归调用, 不然可能导致系统崩溃或陷入死循环。

三、递归问题分析

递归程序最少有两种方法可以写出。第一种是想办法把问题转化为数学表达式, 能用数学表达式写出的, 可以直接把数学表达式变为程序;第二种是按照递归的基本条件, 分析所给问题的结构, 一个问题总具有一定的规模, 想办法把规模变小, 使小规模的问题与原问题具有相同的解法, 当规模足够小时, 该问题的解是已知的, 这时可以套用后面所讲的一般递归程序的结构来写递归程序。

例1:求n!。经过分析n!可以表示为

假定n!是一个long型, 则直接写出程序如下:

例2:求Fibonacci数列 (非波纳契) 的第n项, 该数列表示如下:

按照例1的方法, 写出程序如下:

如输入n=4, 程序 (具体程序用行标号代替) 的执行过程如图1所示, 通过分析以上程序, 大部分学生对递归函数的执行过程有了较为清晰的认识。

例3:用递归的方法将一个正整数n按位输出, 如输入2008, 输出2 0 0 8, n的位数不确定, 可以是任意正整数。

分析:

(1) 函数应该是处理整数n, 并且是输出, 用PrintNum (int n) 来实现这一功能;

(2) 如果n的规模很小 (只有1位) , 可以直接输出后结束程序; (这里应该知道n的位数是问题的规模)

(3) 把问题的规模变小, 去掉n的某1位 (在实际讲解时是去掉个位, 因为去掉个位比较容易一些, 我们用k=n%10保存个位, n=n/10就可以去掉个位) , 余下位形成一个新的规模比原数小的数, 再在新数上递归调用函数, 这个新数按要求输出后, 去掉的这一位因为是个位, 所以应该把它输出到新数的后面。

通过以上分析, 写出程序如下:

void PrintNum (int n) /*该函数能把n按要求输出*/{int k;if (n<10) {printf ("%2d", n) ;return;}/*

如果规模很小, 则直接处理后结束程序*/

k=n%10;/*在n中提出个位数字*/

PrintNum (n/10) ;/*把规模更小的子问题递归调用函数来处理*/

printf ("%2d", k) ;}

通过以上三个例子, 学生对递归函数有了较为清晰的认识, 对递归程序的写法有了一定的掌握之后, 我们可以总结出一个一般递归程序的结构如下, 几乎所有递归程序都可以按照这个结构去分析并写程序。

ReturnType Function (问题描述及规模) /*在程序内部我们应该认为函数Function已经具备处理这类问题的功能, 它可以直接被调用*/

{当规模足够小的时候, 直接给出结果 (有可能什么都不做) , 返回;

把原问题分解为规模更小一些的子问题, 在这些子问题上递归调用函数, 并注意所有子问题都被处理到。}

我们根据这个结构, 要求学生回过来简单看一下前面的三个例子, 多数学生便会对递归有更为深入的认识。之后引入汉诺塔问题, 该问题的分析方法类似于例3, 并套用这个结构, 让学生自己试着写该问题的程序, 可以发现有一部分学生能自己写出递归函数来。

四、递归说明

1、当函数自己调用自己时, 系统将自动把函数中当前的变量和形参暂时保留起来, 在新一轮的调用过程中, 系统为新调用的函数所用到的变量和形参开辟另外的存储单元 (内存空间) 。每次调用函数所使用的变量在不同的内存空间。

2、递归调用的层次越多, 同名变量的占用的存储单元也就越多。一定要记住, 每次函数的调用, 系统都会为该函数的变量开辟新的内存空间。

3、当本次调用的函数运行结束时, 系统将释放本次调用时所占用的内存空间。程序的流程返回到上一层的调用点, 同时取得当初进入该层时, 函数中的变量和形参所占用的内存空间的数据。

4、所有递归问题都可以用非递归的方法来解决, 但对于一些比较复杂的递归问题用非递归的方法往往使程序变得十分复杂难以读懂, 而函数的递归调用在解决这类问题时能使程序简洁明了有较好的可读性;但由于递归调用过程中, 系统要为每一层调用中的变量开辟内存空间、要记住每一层调用后的返回点、要增加许多额外的开销, 因此函数的递归调用通常会降低程序的运行效率。

总结

在C语言中, 函数一直是学习的重点和难点, 递归又是最难掌握的一类函数, 本文从实际教学需要出发, 首先分析递归的基本条件, 从由易到难的顺序, 设计了一些教学实例, 重点让学生了解递归函数的写法以及执行情况, 最后总结出递归函数的一般程序结构, 使学生能正确设计递归程序, 在实际教学中取得了良好的效果。

参考文献

[1]Brian W.Kemighan, Dennis M.Ritchie.The C Programming Language (2nd Edition) .Prentice Hall, 2000年。

[2]Prata S.C Primer Plus.Sams, 2004年。

[3]谭浩强:《C程序设计》 (第二版) , 清华大学出版社, 1999年12月。

[4]项响琴:《递归问题的教学探讨》, 《合肥学院学报》, 2006, 16 (2) :63-65。

C++ 递归函数的详解 篇5

1.快速排序是什么呢?

快速排序的基本思想是：通过一趟快速排序，把待排记录分成两

个子序列，其中一个子系列中的记录都小于另一个子序列，然后，

分别对两个子序列进行快速排序。

可以看出，快速排序的核心就是划分子序列。

2.下面让我们了解一下递归函数快速排序的思想：

(1)将待排序的数据放入某数组中(如数组a[]) 中，下标从 low 到 high;

(2)对数组进行如下操作：从数组中取一个元素值作为枢轴

记录(一般取第 0 号元素，即 a[0])，存入 key(一个变量) 中;

(3)在数组 a 中，将 key 调整到适当位置，然后将比 key

大的元素都放在 key 的右边，比 key 小的数都放在 key

的左边。

(4)这一趟排序的结果是key 将原数组 a 分割成

了两个子数组，key 的左边的值都比key 小，右边的都比

key 大。

(5)此时，问题就成了如何都将这两个子数组进行排序的问题，显然

对这两个子数组调用上述方法即可，即进行递归调用上述方法，

直到排序完成。

(6)显然，通过上述过程，当我们处理完所有的元素时，最终结果

为：每个元素的左边的元素都不大于该元素，而右边的元素都不小

于该元素。

3.如何确定key的位置呢?

我们确定key的值后，利用 key 将数组 a 划分成两个子数组。

具体方法：

(1)取出数组的第 0 个元素，作为分界值放到 key 里，

即 key = a[0]; 此时，数组元素 a[0] 空闲，用一个左探针left

指示，即 left = 0;

(2)利用右探针 right 从右往左走，寻找小于 key 的元素，找到

后就将该元素的值放进 left 所指示的空闲位置，此时 right 所

指示位置成为空闲位置;

(3)让左探针 left 往右走，寻找比 key 大的元素，找到则将该

元素的值放进 right 所指示的空闲位置。此时 left 所指示位置

变为空闲;

(4)循环执行 2、3步，直到 right 不再大于 left为止(此时，

意味着将所有元素都与 key 进行了比较)，

left 与 right 相遇的

地方就是 key 的位置。

具体的代码：

#include

void QuickSort( int a[], int low, int high);

void main()

{

int a[] = { 32, 8, 65, 18, 19, 12, 61 };

int i;

QuickSort(a, 0, 6);

for(i=0; i<7; i++)

printf(“%4d”, a[i]);

}

//QuickSort方法，实现函数的快速排序

void QuickSort( int a[], int low, int high)

{

int key;

int left, right;

// 若待排序列为空或仅有一个元素，则无需排序

if( low >= high ) return ;

// 1 将待排记录划分成两个子序列

// 1.1 选择序列中第一元素作为轴记录

key = a[low];

// 1.2 根据轴记录 key 将待排序列划分成两个子序列

left = low;

right = high;

while( left< right )

{

while( left= key)

right--; // right从后向前扫描，跳过“大”的元素

a[left] = a[right];// 遇到“小”元素，移动到前面去

while( left

left++; //left 从前向后扫描，跳过小于轴记录的元素

a[right] = a[left]; // 遇到“大”元素，移动到后面去

}

// 1.3 放置轴记录

a[left] = key;

// 2.对两个子序列分别进行快速排序

QuickSort(a, low, left-1);

QuickSort(a, left+1, high);

语言递归 篇6

递归是近年来语言学研究中的一个热点话题之一,无论是转换生成语法,还是功能语法,它们都关注语言中的递归现象。在国内,关于语言递归的研究已经有十二年,其研究结果对于深刻认知语言现象、全面把握语言规律起到了积极的推动作用。本论文以2001年至2012年发表在各种外语核心期刊和各大院校学报上与语言递归研究相关的论文为探讨对象,对这些论文进行了宏观而具体的总结。下面分别从这些论文的研究内容、研究意义、存在的问题以及研究趋势等方面进行分析。

2 研究内容

本文先以表格的形式从这些论文发表的年份、发表期刊、期号以及论文作者等几个方面总览一下国内十二年来关于语言递归的研究情况:

2.1 国内语言递归研究论文总览

注:后面加*号的期刊即为核心期刊。

从以上表格中,我们可以清晰地看出国内关于语言递归的研究始于2001年,以广东外语外贸大学钱冠连教授以《语言的递归性及其根源》为题发表在《外国语》上的论文为开端。而沉寂了四年后,2006年开始外语界又就语言递归现象展开了研究,公开发表的论文有五篇之多,可见该话题四年之后逐渐引起了学者和教师的兴趣,其中,这五篇论文里面有两篇发表在外语类核心期刊上,这说明其研究成果和论文质量渐渐受到了业内的认可和肯定。此后,每年都有关于语言递归的论文公开发表。

该表格宏观而直接地为我们展现了学界自2001年起十二年来就语言递归进行研究的基本情况。下面,本论文就具体地阐述一下这些相关论文的研究内容。

2.2 研究内容

国内对语言递归的研究时间还不算长,但是研究内容基本涵盖了语言递归理论框架下的主要问题。按照十二年来国内刊物上发表的论文的内容与性质划分,大致可以分为以下五类:

第一种是探索介绍性质的,以广东外语外贸大学钱冠连教授于2001年发表在《外国语》上的论文《语言的递归性及其根源》为代表。在他的论文中,作者旨在将语言的递归性这一语言学术语引入国内,钱教授创造性地指出并说明了语言的递归性(recursiveness)和语言的任意性与线性一样,是语言的根本性质之一,他第一个定义了语言递归性,即“语言结构层次和言语生成中相同结构成分的重复和相套”(钱冠连,2001:10),接着作者揭示了语言递归性的根源:宇宙全息律(宇宙的递归结构)。2006年,詹全旺在《语言递归的层次与方式》一文中结合具体例子探索了语言递归的三个层次,即短语递归、句子递归和语篇递归,接着,作者仍旧结合实例介绍了三个层面上的三种递归方式,即并列递归、从属递归以及并列从属递归。詹全旺的论文是对语言递归现象的进一步探讨和分类。2009年,杨烈祥在论文《论语言的递归机制》中,着重介绍了语言的“递归机制”(recursive devices),这一术语在前面提到的钱冠连教授的论文中也有所提及,不过杨烈祥的论文对其进行了较为深入的阐述,值得注意的是,该论文还指出了递归基础,认为“生成语法中的语言递归性首先是建立在语言具有离散无限性的观察之上的。语言的离散性是指可以将意义按不同的方式进行无限重复、内嵌和合并等操作。从而生成意义不同的、结构更复杂、形态丰富多样的表达方式,以表达人类最细微、最复杂的思想。”(杨烈祥,2009:134)“除离散性外,语言递归的另一个根源是语言的梯级性(hierarchy),或者说语言的非线性(non-linearity)结构。”(杨烈祥,2009:135)杨烈祥论文中的观点跟钱冠连教授的观点是一脉相承的,他们一致认为“语言整体上的递归性和局部上的非递归性”(钱冠连,2001:8)是对立统一的,“语言中存在着局部非递归成分,但并不能改变语言递归的本质属性。”(杨烈祥,2009:136)

第二种是论述比较性质的,如代天善(2006)在《生物进化语境下的语言递归性——评乔姆斯基、杰肯道夫等人的语言机能进化观》一文中评述和对比了生物进化语境下对语言机能的研究中两种对立的观点:以豪泽、乔姆斯基和菲奇等学者为代表“提倡”的“唯递归性假设”(1)(the recursion-only hypothesis)以及以杰肯道夫和平克等另一派学者为代表提出的“语言适应性假设”(the language-as-adaptation hypothesis)。同年,代天善(2006)又发表了论文《唯递归性假设语境下的语言相对论》,该论文阐释了语言相对论(又称萨皮尔-沃尔夫假设“the Sapir-Whorf hypothesis”)跟“唯递归性假设”之间的关联和二者互补互济的关系。代天善(2006)在另一篇论文《语言递归性与语言相对论》中从语言哲学的角度阐述了语言递归性和语言相对论(language relativity)的关联,论文认为,虽然“语言相对论关注语言的多样性。生成语法研究语言的普遍性”(代天善,2006:18),但是“语言的多样性和语言的同一性并不矛盾,它们构成了一个问题的两面”(代天善,2006:18),“(从语言递归性的视野看语言相对论)生成语法对纷繁的语言现象剥离得越透彻,语言变异的成分就显露得越明显,语言相对论的成因就越容易定位”(代天善,2006:13)。正如论文结论中所说,“语言递归性和语言相对论,它们看似矛盾冲突,实际上互相补充,互相支持。它们在不同的领域,从不同的角度加深了我们对人类丰富多彩的语言现象的理论认识。”(代天善,2006:18)另外一篇归入此类的论文是杨烈祥于2012年1月发表在《外语教学与研究(外国语文双月刊)》上的《唯递归论的跨语言比较评述》,作者从语言理论和语言行为等方面综述了有关唯递归论(recursiononly claim)和语言递归性的跨语言比较研究,还讨论了语言演化研究的生物要求,最后得出结论“不管怎样,唯递归论极大地促进了语言学的跨学科研究,也极大地促进了生物语言学和语言演化研究的发展。可以预见,这是语言学未来的重要学科发展方向。”(杨烈祥,2012:62)

第三种是阐发解释性质的,这一类中的论文与第一种中的论文不同之处在于它们纯粹是对语言递归现象的演绎和说明,比如在《语篇结构中的递归现象》这篇论文中,作者通过考察不同语域语篇的结构模式及实际语篇,结合汉语和英语中的语言现象,发现“功能句法中讨论的两类递归(线性递归和嵌入递归)同样存在于语篇结构中”(王勇、黄国文,2006:288),论文的结论是“递归是语篇结构中较为普遍的现象……语篇结构的递归性具有可选性和理论上的无限性两个特点,这使得实际语篇的结构既有一定的基本规律又富于变化。递归性能够帮助我们透过表面上的纷繁变化把握语篇的基本模式和变化规律,这对语篇理解和说出/写出合乎规范的语篇都会有所裨益。”(王勇、黄国文,2006:294)另外三篇同类的论文是傅志海的《语篇结构分析中的递归现象透视》(2007)、《递归现象在语篇中的体现》(2007)和《语篇结构中的递归性特征和意义分析》(2008),他的这三篇论文大同小异,都结合例子解释了语篇结构(分析)中的递归现象,归纳了其特征,指出了其意义。还有一篇是田正玲和赵震红(2007)的《语言的递归性在直接成分分析法及转换生成语法中的体现》,这篇论文主要从句法的角度举例论证了理论语言学中直接成分分析和转换生成语法中存在的语言递归现象,作者通过讨论,发现“直接成分分析,以及转换生成语法具体的转换示例,都充分体现了语言的递归性。直接成分分析法重在体现短语结构的重复使用,转换生成语法则体现了短语结构的重复、句式重复和镶嵌(或相套)。语言的无限创造性要依赖于语言的递归性,语言的递归性使人们表达思想,进行交流成为可能。”(田正玲、赵震红,2007:274)所以,我们可以看到,归类于第三种性质的这五篇论文基本上是结合例子从语篇或句法角度对语言递归性进行的阐释。

第四种是应用创新性质的,以罗树林的《试论语言递归机制及其在对外汉语教学中的应用》(2011)为代表,尝试将语言递归性运用到汉语言教学中,作者在钱冠连(2001)、詹全旺(2006)以及杨烈祥(2009)等人对语言递归性做出的定义基础上提出了新的“语言递归”定义:“语言结构单位和语言结构规则的重复或相套”(罗树林,2011:58)。作者解释道,“语言结构单位包括语音、语义、语法这三个要素系统。”(罗树林,2011:58)“语言结构规则也就是语法规则系统,可以分出词法规则和句法规则两大子系统。”(罗树林,2011:58)该论文创造性地把语言递归分为“语音递归、语义递归、语法递归”三类,突破了以往递归研究仅限于“语法递归”的局限。论文考虑到汉语言的固有特性,结合实例提出语音递归中有声母递归、韵母递归和声调递归等类型,语义递归包括同义递归、反义递归、类义递归等形式,而语法递归中包含语素递归、词语递归、短语递归、句子递归这四个方面。除了短语递归、句子递归(以及语篇递归)在其他学者的论文中有过讨论外,罗树林的论文中提到的其他“X递归”都是第一次出现。这篇论文还分析了语言递归机制的特点和作用,指出了它在对外汉语教学应用过程中的理论意义和实践意义。同属于这一范围的论文还有凌永刚的《论递归性与对外汉语语音教学》(2012)及《论递归性与对外汉语词汇教学》(2012)。

第五种是批判质疑性质的,代表性论文是叶友珍(2012)的《论“唯递归性假说”的无效性》,作者从“唯递归性假说”术语的提出、“递归机制”的来源、生物比较研究方法的局限性等方面论证了“唯递归性假说”的无效性。作者以实事求是的研究态度,通过论证得出的结论是“将‘递归性’作为人类语言与动物语言的唯一区别性特征有失偏颇,‘唯递归性假设’是无效的。”(叶友珍,2012:131)很显然,叶友珍论文得出的结论是对“唯递归性假说”这一提法的质疑和对其合法的理论地位的辨伪。作者写这篇批判性的论文的初衷是告诫人们“如果不假思索地接受这一‘假说’,不仅是对Chomsky等人的误读,也会产生错误的研究导向。”(叶友珍,2012:131)笔者认为叶友珍这种敢于质疑、不人云亦云的态度值得我们学习,需要注意的是,她的论文只是论证了“唯递归性假说”这一概念的无效性,并没有否定语言的递归性和递归机制。反过来思考,论文作者对该假说(这一概念的总结者为Pinker和Jackendoff)的质疑正是对Hauser、Chomsky和Fitch等学者关于生成语法中语言递归性研究成果的支持和认可。

3 研究意义

总体上,这些论文的研究意义可以分为理论意义和实践意义,下面分别来说明一下:

3.1 理论意义

整体上看,作为学术论文,这十三篇论文都有较强的理论意义,比如钱冠连(2001)的论文第一个将语言递归性这一术语引进和介绍到国内,为国内语言学界和语言教学界进一步对该语言现象进行探索和研究奠定了基础,为人们深刻地认识语言的规律和现象提供了新的理论视角。詹全旺(2006)、杨烈祥(2009)等人的论文对语言递归层次和方式以及语言递归机制的探索和讨论有利于我们进一步认识语言的本质,认识语言和世界的关系,在语言哲学研究中有着重大的理论意义。

代天善(2006)和杨烈祥(2012)将语言递归研究与语言相对论、语言进化论或者与生物语言学、语言进化研究相结合,极大地语言学研究的跨学科、跨领域发展,为语言学研究提供了新的思路,丰富了研究的范围。

王勇、黄国文(2006)、傅志海(2007、2008)以及田正玲、赵震红(2007)的论文则有助于我们理解语篇结构中或直接成分分析及转换生成语法中的语言递归现象,同样有利于我们认识语言现象和语言规律。

罗树林(2011)的论文则大胆地对语言递归性进行了理论创新,结合汉语固有的特点,具体问题具体分析地提出了“语言递归”新的定义,对其种类进行了新的划分。这为我们将理论运用于实践有很大的启发意义。而叶友珍(2012)论文中的论证和剖析则有助于我们从理论层面正确解读Chomsky等西方学者在生成语法中展现的关于语言机能和语言递归性的研究成果和学术观点。

3.2 实践意义

国内对语言递归性研究的这些论文的实践意义可以归纳为以下八点:

(1)语言递归性的巨大意义甚至是全部意义就在于允许人们用少量的句型生成无限多的句子;(钱冠连,2001:8)语言递归层次与方式的研究使我们进一步认识了语言的本质,摸清了短语、句子和篇章生成的规律在实践上对计算机语言的开发也具有十分重要的指导作用;(詹全旺,2006:62)

(2)唯递归论概括了句法无限性的特征,是MP(2)的延伸和发展,使语言学研究最终成为生物学研究的一个分支又迈出了重要的一步;(杨烈祥,2009:136)

(3)跟过去纯粹思辨性、理论性的交锋相比,这场争辩(3)在结合自然科学研究方面是一个重要的跨越;(代天善,2006:74)

(4)从递归性入手,我们可以透过表面上的纷繁变化把握语篇结构的基本模式和变化规律,有裨于理解语篇和生成合乎规范的语篇;(王勇、黄国文,2006:288)

(5)语言的无限创造性要依赖于语言的递归性,语言的递归性使人们表达思想,进行交流成为可能;(田正玲、赵震红,2007:274)

(6)语言递归机制在对外汉语教学中具有十分重要的地位,合理运用能有利于提高课堂教学效果,它同样可以用于指导语言教材的编写;(根据罗树林论文概括出)

(7)对语言递归性相关理论(诸如“唯递归性假说”)的合理质疑和有效论证及时纠正了错误的理解倾向,能够避免相关研究往错误的方向发展。(由叶友珍论文归纳出)

事实上,理论与实践是矛盾的两个方面,二者相辅相成,理论意义和实践意义并没有十分明晰的界限,任何理论都需要人们发挥主观能动性去把它付诸实践,在实践中接受修正、检验和完善。所以,这些有关语言递归的论文的研究意义虽然在本论文中被分解为理论意义和实践意义,但是无论是理论意义还是实践意义都需要更多的学者继续去发现、论证和发展。

4 国内语言递归研究论文中存在的问题

国内有关语言递归的研究起步较晚,十二年来,语言学界对它的相关研究取得了诸多学术成果的同时,也不可避免地存在一些问题,主要表现在以下几个面:

首先,关注语言递归这一语言学现象(主要是在生成语法和功能语法的范畴下)的学者仅限于有限的十几位学者或老师,尤其是知名的学者更是寥寥无几。当然,这其中有研究兴趣等主客观影响因素,但是目前这种状况说明国内学术界对语言递归的关注还远远不够,亟待更多的研究者在这一领域继续展开探讨。

其次,从论文所发表的刊物上看,国内就语言递归研究发表在核心期刊上的论文数量占所有发表在期刊学报上的论文数量的比重偏低。十七篇论文中被核心期刊收录的只有七篇,仅占41.1%。(详细情况参见前文表格。)就该话题进行研究的高质量的论文需要在各位学者老师的共同努力下保质保量地多多发表。

再次,从时间跨度上分析,国内对语言递归研究的时间连续性较差,继2001年钱冠连教授的论文《语言的递归性及其根源》发表四年后才有其他学者接着于2006年就语言递归研究发表出论文,随后几年,在2008至2010年间对语言递归的研究差点出现“断层”现象。这种现象的存在表明国内对语言递归的研究情况尚不稳定,还没有形成一定的体系。

再者,这些论文中,大多数论文的内容是一脉相承而又相互独立的,即其主题都是对语言递归及其现象的阐释和说明,同时,后续论文又是对先发表的论文观点的补充和发展。然而,个别论文存在着剽窃现象,其论文内容将前人论文中的观点“拿来”后,只是将例子稍作更改便直接投稿发表出来,而参考文献中却隐去了所参照的论文,无疑,这种做法是对前面学者学术研究成果的亵渎。

此外,有些论文里提出的一些新的术语尚待考证,典型的如罗树林(2011)在其论文中提出的“语音递归”、“声调递归”、“语义递归”等概念,它们是否能够站得住脚,能否经得起其他学者的推敲和实践的检验,这都需要我们展开进一步的研究和论证。其实,正如王勇、黄国文(2006)所指出的“到目前为止,系统功能语言学对递归性的研究主要在句法方面,实际上递归现象还存在于其他层面上,如时态系统和词组/短语的结构中。”(王勇、黄国文,2006:289)所以,确切地说,罗树林提出的新的概念术语是针对于汉语教学而言的,而我们需要进一步探索是否在英语等西方语言的各个系统中也存在着“语音递归”、“语义递归”等现象。

最后,国内关于语言递归研究的论文纯理论性的东西大量存在,在与现实的结合方面有所欠缺,虽然也有少量论文提到了研究语言递归的实际意义,比如詹全旺(2006)指出,对语言递归层次和方式的研究对计算机语言的开发也有着十分重要的实践意义,罗树林(2011)认为语言递归机制运用到教学中有利于提高教学效果,但是这两篇论文的相关论述都只是一笔带过,并没有说明那样说的原因或说明究竟如何将其应用到对外汉语教学中。因此,我们需要在对语言递归进行理论研究的同时,加大对这一理论与现实生活和语言学习或教学的结合,使其更好地为语言学实践服务。

5 研究趋势及建议

纵观十二年来国内就语言递归进行的研究,尤其是最近几年来的研究情况,笔者发现其研究的发展方向如下:

第一,语言递归研究与其他学科领域诸如生物语言学、语言进化研究相结合,推陈出新,在不同理论观点的糅合与碰撞中实现理论创新和可持续发展。

第二,语言递归研究与语言实践尤其是语言教学实践相结合,走理论指导实践,一切为实际服务的研究路线。

第三,语言递归研究延续纯理论研究的路子,继续探讨和认识一些理论研究的盲区,比如递归场、时态系统中的递归现象,以及除了在短语/词组、句子、语篇层面上有语言递归的存在之外,语言系统中是否还有其他层面上的递归?

虽然关于语言递归的研究在国内开展的时间并不长,仍然有上文提到的这样那样的问题存在,但是从另外一个角度来看,它们也为国内学者老师们进一步研究奠定了基础,指明了研究方向。

6 结语

本论文从国内语言递归研究的研究内容、研究意义以及研究过程中存在的问题等方面回顾和总结了近十二年来国内学者老师对该话题的研究现状,在此基础上,预测了其研究趋势,并提出了一点儿建议,希望有更多的学者关注并继续对语言递归进行研究,发表出更多高质量的研究论文,为进一步认识语言现象、深入揭示语言规律、更好地服务于语言学实践起到积极的推动作用。

摘要：本论文在对十二年来国内语言递归研究进行梳理和综述的基础上,回顾了其研究特点和研究意义,指出了其存在的问题,然后预测了其研究的方向并提出了一些建议,以期通过这篇论文的反思吸引更多的研究者加入到语言递归研究的队伍中来,推动对语言现象的认识和对语言规律的揭示。

语言递归 篇7

递归作为一种算法在程序设计语言中广泛应用。它是调用一个函数的过程中又出现直接或者间接地调用该函数本身。递归是计算机科学的一个重要概念, 递归的方法是程序设计中有效的方法, 采用递归编写程序能使程序变得简洁和清晰。

递推算法是一种用若干步可重复的简运算 (规律) 来描述复杂问题的方法。递推是序列计算机中的一种常用算法。递推法的特点是从一个已知的事实出发, 按照一定规律推出下一个事实, 再从这个新的已知事实出发, 再向下推出一个新的事实。

2 问题提出

一场球赛开始前, 售票工作正在紧张进行中, 每张球票为50元, 现有m+n个人排队等待购票, 其中有m个人手持50元的钞票, 另外n个人手持100元的钞票。假设开始售票时售票处没有零钱, 求出这m+n个人排队购票, 使售票处不至出现找不开钱的局面的不同排队种数 (这里正整数m、n从键盘输入) 。

这个问题用一般的解决方法非常麻烦, 下面用递归和递推方法解决。

3 购票问题分析

这是一道组合计数问题。令f (m, n) 表示有m个人手持50元的钞票, n个人手持100元的钞票时共有的方案总数。

(1) n=0。

n=0意味着排队购票的所有人手中拿的都是50元的钞票, 那么这m个人的排队总数为1, 即f (m, 0) =1。

(2) m

当m

(3) 其它情况。

m+n个人排队购票, 第m+n个人站在第m+n-1个人的后面, 则第m+n个人的排队方式可由两种情况获得:①第m+n个人手持100元的钞票, 则在他之前的m+n-1个人中有m个人手持50元的钞票, 有n-1个人手持100元的钞票, 此种情况共有f (m, n-1) ;②第m+n个人手持50元的钞票, 则在他之前的m+n-1个人中有m-1个人手持50元的钞票, 有n个人手持100元的钞票, 此种情况共有f (m-1, n) 。

由加法原理得到f (m, n) 的递推关系:

f (m, n) =f (m, n-1) +f (m-1, n)

初始条件:

当m

当n=0时, f (m, n) =1

4 购票排队递归程序实现

5购票排队递推程序实现

6结语

递归和递推算法解决问题结构清晰、可读性强, 而且容易用数学归纳法来证明算法的正确性, 为设计算法、调试程序带来很大方便。且递推程序的运行速度要快于递归程序。

参考文献

[1]卢开澄, 卢华明.组合数学[M].第4版.北京:清华大学出版社, 2006.