C语言递归函数教学的设计与探讨

丁雪晶

摘要：针对《C语言程序设计》课程，在教学过程中递归函数部分普遍反映比较难，文章给出了递归函数的定义和设计思路，并通过对几大典型的递归问题给出求解思路和参考代码，加强学生对递归函数的理解，提高学生对递归函数的掌握和应用。

关键词：C语言；递归函数；教学设计；案例分析

中国分类号：G424 文献标识码：A 文章编号：1009-3044（2018）16-0150-03

1引言

《C语言程序设计》是高等学校计算机及相关专业的必修课，其以短小精悍、使用灵活、功能强大等特点深受人们的喜爱。函数作为C语言程序设计的基本组成单位，在教学过程中占据着非常重要的地位，而递归函数的设计则是函数教学中的重点和难点。

2递归函数概述

在编程语言中，函数直接或间接调用函数本身，该函数称为递归函数[1]。但递归也并不是简单的“自己调用自己”。递归算法的思想是：把要解决的问题分解成与原问题有相同解法，且规模较小的问题，直到遇见终止条件。

所以一般情况下，能采用递归函数来解决的问题，需满足以下两个条件：

（1）该问题可以缩小规模，且缩小后的问题与原问题有相同的解法；

（2）必定要有一个明确的结束递归的条件。

为了方便理解，以求n！为例，这是一个明显的可以用递归解决的问题：

n！可以表示为：[n！=n×n-1×n-2…×2×1=n×n-1！]

即有：

[n！=1 n=1n×n-1！ n>1 ]

或者

[f（n）=1 n=1n×f（n） n>1 ]

首先看看该问题是否满足递归的两个条件的：

当n>=2，求f（n）只需求出f（n-1），也就是说求n的阶乘问题，转化成了规模更小的求n-1阶乘问题；

而递归结束条件为，n=1时， fun（1） = 1。

因此，我们可以很容易的写出计算n！的递归程序：

int fac（int n）

{

if（n==1）

return 1；

else

return n*fac（n-1）；

}

在编写递归函数时，通常把判断递归结束的条件写在前面，以确保函数在遇到结束条件时能中止递归，否则会导致程序死循环。

3 典型案例分析

例1：求Fibonacci数列（斐波那契）的第n项值，表示如下：

[fibn=1 ，n=0或 n=1fibn-1+fibn-2， n>1]

此例将求规模为n的问题转化为规模较小的n-1和n-2问题，而递归结束条件为，一直转化到规模为1和0时。所以递归函数设计如下：

int fib（int n）

{

if（n==1 || n==2）

return 1；

else

return fib（n-1）+fib（n-2）；

}

void main（）

{

int num=fib（8）；

printf（"%d"，num）；

}

输出结果：21

例2：汉诺塔问题[1]：有三根杆子A，B，C。A杆上有若干盘子，把所有盘子从A杆移到C杆（可借助B杆）。规则是：每次只能移动一个盘子，且在移动过程中三根杆上都始终保持大盘在下，如图1所示。求移动的步骤和移动的次数。

实现这个汉诺塔问题的递归算法可以有如下步骤（n表示盘的个数，从上往下依次为第1个，第2个…第n个）：

当n=1时，即只有一个盘子，为递归算法的结束条件，从A盘移到C盘即可；

当n>=2时：

（1）先将A柱上面的n-1个盘子从A柱借助C柱，移到B柱；

（2）将A柱的第n个盘子从A柱移动C柱；

（3）再将B柱的n-1个盘子借助A柱，移到C柱。

将汉诺塔的规模为n的问题转化为规模小一点的n-1问题，通过递归会将规模继续减小，直到遇到结束条件的规模为1的问题。

递归算法hanoi实现如下：

#include

int num=0；

void hanoi（intn，charA，charB，char C）//将n个盘子从A柱，借助B柱，移动C柱

{

if（n==1）//结束条件

{

num++；

printf（"第%d次：%d号盘：%c——>%c＼n"，num，n，A，C）；

}

else

{

hanoi（n-1，A，C，B）； //n-1个盘子从A柱借助C柱，移到B柱

num++；

printf（"第%d次：%d号盘：%c——>%c＼n"，num，n，A，C）；

hanoi（n-1，B，A，C）；//n-1个盘子从B柱借助A柱，移到C柱

}

}

void main（）

{

hanoi（3，'A'，'B'，'C'）；//将3个盘子从A移到C

}

实验结果如图2所示：

例3：八皇后问题[2]

八皇后问题是一个以国际象棋问题：如何在8×8的棋盘上摆8个皇后，每行每列只能摆一个皇后，使得这8个皇后无法相互攻击，即任意的2个皇后不能在同一行、同一列或对角线上，如图3所示。当然这是八皇后问题的初始規则，现在可以将其推广为四皇后，五皇后等n皇后问题，此处的n须等于1或大于等于4，问题才有解。

解题思路：

从第一行开始摆放皇后，每摆放1行，递归一次，每次递归里面考虑8列， 即对每一行皇后有8个可能的位置可以放。找到一个与前面行的皇后都不会互相攻击的位置，然后再递归进入下一行。

在这里用一个一维数组来表示相应行对应的列，即k[i]=j表示，第i行的皇后放在第j列。皇后产生冲突的条件有3个：同行、同列、对角线。例如对于m行和n行摆放皇后时的冲突：同列：k[m]=k[n]。对角线有主对角线方向和副对角线方向。主对角线满足，两个皇后的行之差等于他们的列之差：m-n=k[m]-k[n]； 副对角线方向， 两个皇后的行之差等于其列之差的相反数：m-n=k[n]-k[m]。 只有当前皇后和前面所有已摆好的皇后都不会产生冲突时，才能进行下一个皇后的摆放，即下一级递归。

递归函数设计如下：

#include

intk[4]， n=4， num=0； //n设为4，即4行4列

void print（）{ //输出皇后矩阵，摆了皇后输出1，没摆皇后输出0

for（int i=0； i

for（int j=0； j

if（k[i]==j）

printf（"1 "）；

else

printf（"0 "）；

printf（"＼n"）；

}

printf（"＼n"）；

}

voidfun（int r）{

int flag=0；

if（r == n）{//当摆完最后一行时，输出皇后矩阵，递归结束条件

print（）；

num++；

return；

}

for（int i=0； i

k[r] = i；//第r行的皇后位置放在i列

flag=1；

for（int j=0； j

if（k[r]==k[j] || r-j==k[r]-k[j] || r-j==k[j]-k[r]）{//產生冲突的条件

flag=0；

break；

}

if（flag）

fun（r+1）； //进入下一级递归，即摆放第r+1个皇后

}

}

void main（）{

fun（0）；

printf（"共%d种摆放＼n"，num）；

}

实验结果如图4所示：

例4：二叉树的遍历[3]

一棵二叉树由根结点、左子树和右子树三部分组成，因而只要依次遍历这三个部分，就能遍历整棵二叉树的所有结点。遍历方式有先序遍历（先根结点，然后。左子树右子树）、中序遍历（先左子树，然后根结点，最后右子树）、后序遍历（先左子树、右子树，然后根结点），这三种遍历算法采用递归方式比非递归方式要简单得多：

//先序遍历

void PreOrder（BiTreebt） //bt为二叉树或某一子树根节点的指针

{

if（bt！=NULL） //如果bt为空，递归结束

{

visit（bt）；//访问根节点

PreOrder（bt->lchild）； //先序遍历左子树

PreOrder（bt->rchild）； //先序遍历右子树

}

}

//中序遍历

void InOrder（BiTreebt） //bt为二叉树或某一子树根节点的指针

{

if（bt！=NULL） //如果bt为空，递归结束

{

InOrder（bt->lchild）； //先序遍历左子树

visit（bt）；//访问根节点

InOrder（bt->rchild）； //先序遍历右子树

}

}

//后序遍历

void PostOrder（BiTreebt） //bt为二叉树或某一子树根节点的指针

{

if（bt！=NULL） //如果bt为空，递归结束

{

PostOrder（bt->lchild）； //先序遍历左子树

PostOrder（bt->rchild）； //先序遍历右子树

visit（bt）；//访问根节点

}

}

由此可见，采用递归方式，三种遍历算法的区别只在于访问根节点语句的位置不同，相比非递归算法要简单很多。

4结论

在C语言教学中，递归函数的设计一直是其中的重点和难点，本文首选分析了采用递归算法解决问题的基本条件，然后列举了几个比较经典的案例，对其进行分析执行，使学生能正确掌握递归函数的设计。

参考文献：

[1]潭浩强.C语言程序设计[M].北京：清华大学出版社，2017.

[2]樊艳芬，周琪云，吴帅.用Java语言实现八皇后问题的递归和非递归算法设计[J].计算机与现代化，2007（3）.

[3]严蔚敏.数据结构[M].北京：清华大学出版社，2013.