文档介绍：C语言与程序设计 The C Programming Language
第12章递归 华中科技大学计算机学院 卢萍
8/27/2018
1
华中科技大学计算机学院C语言课程组
本章讲授内容
递归(recursion)是一项非常重要的编程技巧,可以使程序变得简洁和清晰,是许多复杂算法的基础。本章介绍
递归、递归函数的概念;
递归的执行过程;
典型问题的递归函数设计;
分治法与快速排序;
回溯法;
递归在动态规划等算法中的应用。
8/27/2018
2
华中科技大学计算机学院C语言课程组
递归概述
递归是一种函数在其定义中直接或间接调用自己的编程技巧。递归策略只需少量代码就可描述出解题过程所需要的多次重复计算,十分简单且易于理解。
递归调用:函数直接调用自己或通过另一函数间接调用自己的函数调用方式
递归函数:在函数定义中含有递归调用的函数
8/27/2018
3
华中科技大学计算机学院C语言课程组
【】用递归法计算阶乘n!
阶乘的计算是一个典型的递归问题。n!定义为:
这是递归定义式,对于特定的k,k!只与k和(k-1)!有关,上式的第一式是递归结束条件,对于任意给定的n!,将最终求解到1!或0!。
\源程序\
8/27/2018
4
华中科技大学计算机学院C语言课程组
计算4!的递归执行过程
图(a)是递归调用的过程,递归过程中每次n都减1,直到n等于1,即在计算出1!等于1时终止;
图(b) 是当递归过程终止时从每一步递归调用把值返回给调用者的过程,这个过程直到计算出并返回最终值为止。
8/27/2018
5
华中科技大学计算机学院C语言课程组
递归的两个要素
(1)递归结束条件。递归如果没有结束条件,递归过程将永不终止,即无穷递归。无穷递归的最后结果是耗尽内存,使系统不能正常工作甚至死机。
(2)递归定义。为了描述问题的某一状态,必须用到它的上一状态,而描述上一状态,又必须用到它的上一状态,……,这种用自已来定义自己的方法,称为递归定义。递归定义必须能使问题越来越简单,使问题向结束条件转化。
8/27/2018
6
华中科技大学计算机学院C语言课程组
递归算法的特点
递归算法的运行效率较低,耗费的计算时间较长,占用的存储空间也较多。
递归算法结构紧凑、清晰、可读性强、代码简洁。
大多数的简单递归函数都能改写为等价的迭代形式。什么情况下使用递归呢?如果用递归能容易编写和维护代码,且运行效率并不至关重要,那么就使用递归。例如,像二叉树这样的数据结构,由于其本身固有的递归特性,特别适合于用递归处理;像回溯法等算法,一般也用递归来实现。
8/27/2018
7
华中科技大学计算机学院C语言课程组
递归函数设计
递归是一种强大的解决问题的技术,其基本思想是将复杂问题逐步转化为稍微简单一点的类似问题,最终将问题转化为可以直接得到结果的最简单问题。在较高级的程序中,递归是一个很重要的概念。
8/27/2018
8
华中科技大学计算机学院C语言课程组
字符串的递归处理
字符串是以空字符('\0')结尾的字符序列。因此,可以把字符串看成“一个字符后面再跟一个字符串”,或者仅有一个空字符组成的空串。这个字符串的定义说明字符串是一种递归的数据结构,可以用递归的方法对一些基本的处理字符串函数进行编写。
8/27/2018
9
华中科技大学计算机学院C语言课程组
【】用递归实现标准库函数strcmp(s,t)
/* 用递归实现字符串比较函数。
为了区分,取名Strcmp */
int Strcmp(char *s,char *t)
{
if(*s!=*t||*s=='\0') /* 递归结束条件*/
return(*s-*t);
else
return(strcmp(++s,++t));/* 递归调用*/
}
8/27/2018
10
华中科技大学计算机学院C语言课程组