递 归冯文科一、递归的基本概念。

一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。

在程序设计中，函数直接或间接调用自己，就被称为递归调用。

二、递归的最简单应用：通过各项关系及初值求数列的某一项。

在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及n a 与前面临近几项之间的关系。

要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。

比如阶乘数列1、2、6、24、120、720……如果用上面的方式来描述它，应该是：⎩⎨⎧>==-1,1,11n na n a n n如果需要写一个函数来求n a 的值，那么可以很容易地写成这样：这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。

递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。

以上面求阶乘数列的函数)(n f 为例。

如在求)3(f 时，由于3不是特殊值，因此需要计算)2(*3f ，但)2(f 是对它自己的调用，于是再计算)2(f ，2也不是特殊值，需要计算)1(*2f ，需要知道)1(f 的值，再计算)1(f ，1是特殊值，于是直接得出1)1(=f ，返回上一步，得2)1(*2)2(==f f ，再返回上一步，得62*3)2(*3)3(===f f ，从而得最终解。

用图解来说明，就是下面再看一个稍复杂点的例子。

【例1】数列}{n a 的前几项为1、111+、11111++、1111111+++、……输入n ，编程求n a 的精确分数解。

分析：这个题目较易，发现11=a ，其它情况下有111-+=n n a a 。

如要求实数解的话，这基本已经可以写出递归函数了。

但由于题目要求精确的分数解，还需做一些调整。

设pq a n =-1，则由递归关系，有qp p pq a a n n +=+=+=-11111，再约分化简，即得n a 。

但发现一个问题：求出1-n a 时，需要返回两个整数：分子q 与分母p ，而通常的函数只能返回一个整数。

这个问题一般有两类解决办法，一种是让求值函数返回一个结构体变量，这样就可以返回两个变量了（其实还可以不只两个呢）；另一种是在求值函数的参数表中加入两个指针变量或引用变量，通过参数给带回数值。

但由于后一种做法会使程序结构不清晰——返回值是由参数表得到的，因此我们使用前一种方法。

另外，在通过p q a n =-1得出qp pa n +=后，n a 就已经是最简分数了，无须化简。

证明如下：若pq是最简分数，即说明q p ,的最大公约数为1，即对任何q r ≤<1，都有r q mod 与r p mod 不全为0，不防记a r q =mod 、b r p =mod ，则有r b a r q p mod )(mod )(+=+只要a 与b 不全为0，且r b r a <<,，就有a 与r b a mod )(+不全为0。

因此对任何的q r ≤<1，有r p mod 与r q p mod )(+不全为0。

而对于p r q ≤<的情况而言，记a r p =mod ，则有r q a r q p mod )(mod )(+=+由于r q r a <<<≤0,0，因此同样有r p mod 与r q p mod )(+不全为0。

所以对任意p r ≤<1，都有r p mod 与r q p mod )(+不全为0，因此它们的最大公约数为1，即q p p +是最简分数。

虽然这是个要求1-n a （即pq）是最简分数的结论，但由于数列第二项为21，是最简分数，因此可以证明第三项也是最简分数，同时也证明对所有的n a ，求出的qp p+就是最简分数，无须化简。

具体代码如下：)90(≤≤N N N -0i 1+i 2+i N N N i N i 12+i )1(2+i , MAX*sizeof(char));t[n]='\0'; for(i=0;i<n;i++) {t[q[i]]='Q'; cout<<t<<endl; t[q[i]]='.'; }cout<<endl; }bool test(int i, int k) {1 3 5 7 90 2 4 6 8int j;j=0;while(j<k && abs(j-k)!=abs(q[j]-i)) j++;if(j==k && mark[i]==false)return true;elsereturn false;}void search(int k){if(k==n){write();c++;return;}int i;for(i=0;i<n;i++)if(test(i, k)){mark[i]=true;q[k]=i;search(k+1);mark[i]=false;}六、练习【练习】为给定的表达式建立表达式树，并求值。

给定的表达式中，所有数字都是1位正整数，出现的符号可能为＋、－、*、/、（、）。

分析：这是一个与一般数据结构书上讲的用栈计算的方法本质不同的方法。

在详细说明这个算法之前，需要首先明确这个算法用到的概念1、单元：一个单元可能是用括号括起来的一个表达式，或是一个整数；2、项：一个项是指由*与/连接起来的若干单元；3、表达式：一个表达式是指由＋或－连接起来的若干项。

要建立表达式树，需要三个函数互相调用的函数：一个是getunit，用于建立一个单元；一个是getexpr，用于建立一个项，另一个就是build，用于建立一个表达式。

getunit函数较易，如果字符串首字母是（的话，那么从它后面的字符开始用build建立一个表达式，这个表达式就是一个单元；否则，就处理一个整数；getexpr函数是建立在getunit之上的，它先用getunit建立一个单元，然后不停地考察之后地连接符号是不是*或/，若是，则不停地重复读连接符、建立另一个单元、建立连接的操作，直到连接符号不是*或/为止。

build函数是用于最终建立表达式的，它先用getexpr建立一个项，再用符号将剩余的各项连接成二叉树。

代码如下：if(n>0){ hanoi(n-1 ,x,z,y); hanoi(n-1,y,x,z);}.w[10]中int knap(int s,int n){算法32是求n个数的和的递归算法。

算法33是相应的迭代版本。

假设n个数已存储在数组a的分量a[1]，…,a[n]中。

float sum(int n){.a[n]都置为0a[0]=1;*//* ---------------------------------------- */void main(){int i;for ( i = 0; i < 5; i++ )printf("%d! = %d\n",i,factorial(i));/*递归阶乘函数调用*/}/* ======================================== *//* 使用列印数组函数来说明递归调用*//* ======================================== */int list[6] = { 1, 2, 3, 4, 5, 6 }; /* 数组内容 *//* ---------------------------------------- *//* 递归数组反向列印函数*//* ---------------------------------------- */void invert_array(int j){if ( j < 6 ) /* 终止条件 */ {/* 递归链表列印函数调用 */invert_array(j + 1);printf("[%d]",list[j]); /* 列印元素资料 */}}/* ---------------------------------------- *//* 主程式: 反向列印数组内容. *//* ---------------------------------------- */void main(){int i;printf("数组的内容:\n");for ( i = 0; i < 6; i++ )printf("[%d]",list[i]); /* 列印元素资料 */printf("\n"); /* 换行 */printf("递归列印数组的内容:\n");invert_array(0); /* 调用列印函数 */printf("\n"); /* 换行 */}/* ======================================== *//* 递归阶乘函数来说明递归内部处理*//* ======================================== *//* ---------------------------------------- *//* 递归阶乘函数*//* ---------------------------------------- */int factrial(int j){int sum = 0; /* 阶乘总和变数 */ int temp = 0; /* 阶乘总和暂存变数 */if ( j == 0 ) /* 终止条件 */{sum = 1;printf("到达终止条件(j = 0)\n");}else{printf("从函数factrial(%d)调用前的状态: sum = %d\n",j, sum);temp = factrial(j - 1); /* 递归阶乘函数调用 */printf("返回函数factrial(%d)后的状态: sum = %d\n",j, sum);sum = j * temp; /* 计算j!的值 */printf(" ==> 在计算%d!阶乘后的状态: sum = %d\n",j, sum);}return sum;}/* ---------------------------------------- *//* 主程式: 计算整数 4 的阶乘. *//* ---------------------------------------- */void main(){printf("4! = %d\n",factrial(4)); /* 递归阶乘函数调用 */}/* ======================================== *//* 递归的链表建立和列印*//* ======================================== */#include <>struct list /* 链表结构宣告 */{int data; /* 节点资料 */struct list *next; /* 指向下一节点 */ };typedef struct list node; /* 定义新型态 */typedef node *link; /* 定义新型态指标 *//* ---------------------------------------- *//* 递归链表列印函数*//* ---------------------------------------- */void print_list(link ptr){if ( ptr != NULL ) /* 终止条件 */ {printf("[%d]",ptr->data); /* 列印节点资料 *//* 递归链表列印函数调用 */print_list(ptr->next);}}/* ---------------------------------------- *//* 递归链表建立函数*//* ---------------------------------------- */link create_list(int *array,int len,int pos){link head; /* 链表节点的指标 */if ( pos == len ) /* 终止条件 */ return NULL;else{/* 建立节点记忆体 */head = ( link ) malloc(sizeof(node));if ( !head )return NULL;head->data = array[pos]; /* 建立节点内容 */head->next = create_list(array,len,pos + 1);return head;}}/* ---------------------------------------- *//* 主程式: 建立链表后将内容印出. *//* ---------------------------------------- */void main(){int list[6] = { 1, 2, 3, 4, 5, 6 }; /* 数组内容 */link head; /* 指向链表开始 */head = create_list(list,6,0); /* 建立链表 */if ( !head ){printf("记忆体配置失败! \n");exit(1);}printf("链表的内容:\n");print_list(head); /* 列印链表 */ printf("\n"); /* 换行 */}/* ======================================== *//* 递归的链表建立和反向列印*//* ======================================== */#include <>struct list /* 链表结构宣告 */{int data; /* 节点资料 */struct list *next; /* 指向下一节点 */};typedef struct list node; /* 定义新型态 */typedef node *link; /* 定义新型态指标 *//* ---------------------------------------- *//* 递归链表反向列印函数*//* ---------------------------------------- */void print_list(link ptr){if ( ptr != NULL ) /* 终止条件 */ {/* 递归链表列印函数调用 */print_list(ptr->next);printf("[%d]",ptr->data); /* 列印节点资料 */ }}/* ---------------------------------------- *//* 递归链表建立函数*//* ---------------------------------------- */link create_list(int *array,int len,int pos){link head; /* 链表节点的指标 */if ( pos == len ) /* 终止条件 */ return NULL;else{/* 建立节点记忆体 */head = ( link ) malloc(sizeof(node));if ( !head )return NULL;head->data = array[pos]; /* 建立节点内容 */head->next = create_list(array,len,pos + 1);return head;}}/* ---------------------------------------- *//* 主程式: 建立链表后将内容印出. *//* ---------------------------------------- */void main(){int list[6] = { 1, 2, 3, 4, 5, 6 }; /* 数组内容 */link head; /* 指向链表开始 */head = create_list(list,6,0); /* 建立链表 */if ( !head ){printf("记忆体配置失败! \n");exit(1);}printf("链表的内容:\n");print_list(head); /* 列印链表 */ printf("\n"); /* 换行 *//* ======================================== *//* 河诺塔问题*//* ======================================== *//* ---------------------------------------- *//* 河内塔问题的递归函数*//* ---------------------------------------- */int hanoi(int dishs,int peg1,int peg2,int peg3){if ( dishs == 1) /* 终止条件 */ printf("盘子从 %d 移到 %d\n",peg1,peg3);else{hanoi(dishs - 1,peg1,peg3,peg2); /* 第一步骤 */printf("盘子从 %d 移到 %d\n",peg1,peg3);hanoi(dishs - 1,peg2,peg1,peg3); /* 第三步骤 */}}/* ---------------------------------------- *//* 主程式: 找出河内塔问题的解. *//* ---------------------------------------- */void main(){hanoi(3,1,2,3); /* 调用递归函数 */ }/* ======================================== *//* 应用递归来走迷宫*/ /* 数字 0: 表示是可走的路*//* 数字 1: 表示是墙壁,不可走的路 *//* 数字 2: 标示是走过的路*//* ======================================== */int maze[7][10] = { /* 迷宫的数组 */1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 0, 1, 0, 1, 0, 0, 0, 0, 1,1, 0, 1, 0, 1, 0, 1, 1, 0, 1,1, 0, 1, 0, 1, 1, 1, 0, 0, 1,1, 0, 1, 0, 0, 0, 0, 0, 1, 1,1, 0, 0, 0, 1, 1, 1, 0, 0, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };/* ---------------------------------------- *//* 走迷宫的递归函数*//* ---------------------------------------- */int find_path(int x,int y){if ( x == 1 && y == 1 ) /* 是否是迷宫出口 */{maze[x][y] = 2; /* 记录最后走过的路 */return 1;}elseif ( maze[x][y] == 0 ) /* 是不是可以走 */{maze[x][y] = 2; /* 记录己经走过的路 */if ( ( find_path(x - 1,y) + /* 调用递归函数往上 */find_path(x + 1,y) + /* 往下 */find_path(x,y - 1) + /* 往左 */find_path(x,y + 1) ) > 0 ) /* 往右 */return 1;else{maze[x][y] = 0; /* 此路不通取消记号 */return 0;}}elsereturn 0;}/* ---------------------------------------- *//* 主程式: 用递归的方法在数组迷宫找出口. *//* ---------------------------------------- */void main(){int i,j;find_path(5,8); /* 调用递归函数 */printf("迷宫的路径如下图所示:\n");for ( i = 1; i < 6; i++) /* 印出迷宫的图形 */{for ( j = 1; j < 9; j++)printf("%d",maze[i][j]); /* 印出各座标 */ printf("\n"); /* 换行 */}}/* ======================================== *//* 应用递归来解 N 皇后问题 *//* 数字 1: 表示是放置皇后*//* 数字 0: 表示没有放置*//* ======================================== */#define MAXQUEEN 8 /* 最大放置的皇后数 */int pad[MAXQUEEN][MAXQUEEN] = { /* N X N 的棋盘 */0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0 };/* ---------------------------------------- *//* 放 N 个皇后的递归函数 *//* ---------------------------------------- */int put_queen(int x,int y,int times){int i,j,result = 0;if ( times > MAXQUEEN ) /* 终止条件 */ return 1;elseif ( place(x,y) ) /* 检查是否可放置皇后 */{pad[x][y] = 1; /* 放置皇后 */for ( i = 0; i < MAXQUEEN; i++)for ( j = 0; j < MAXQUEEN; j++){/* 递归调用放置下一个皇后 */result += put_queen(i,j,times + 1);if ( result > 0 )break;}if ( result > 0 ) /* 找到了解 */return 1;else{pad[x][y] = 0; /* 清除皇后 */return 0;}}elsereturn 0;}/* ---------------------------------------- *//* 检查皇后是否有相互攻击*//* ---------------------------------------- */(End)第1页第2页第3页第4页第5页第6页第7页第8页第9页第10页第11页第12页第13页第14页第15页第16页第17页第18页递 归冯文科一、递归的基本概念。