递归函数和非递归函数的转变

递归函数和非递归函数的转变

第6章 递归6.1 什么是递归6.2 递归算法的设计 6.3 递归算法到非递归算法的转换

本章小结

递归函数和非递归函数的转变

6.1 什么是递归6.1.1 递归的定义在定义一个过程或函数时出现调用本过程或本

函数的成分,称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用 p,称之为间接递归。

递归函数和非递归函数的转变

例 求n!(n为正整数) 。一般的方法：

n! = 1*2*…*(n-1)*n递归的方法：

1, 当n 0时 n! n ( n 1)!, 当 n 1 时

递归函数和非递归函数的转变

int factorial(int n) { int x; if (n==0) x=1; else x=factorial (n-1)*n; return(x); }

在该函数factorial (n)求解过程中,直接调用factorial (n-1)自身,所以它是一个直接递归函数。

递归函数和非递归函数的转变

递归函数和非递归函数的转变

n=4

int factorial(int n) { int x; if (n==0) x=1; else x=factorial (n-1)*n; return(x); }

n=3

n=2

n=1

n=0

递归函数和非递归函数的转变

6.1.2 何时使用递归 在以下三种情况下,常常要用到递归的方法。 1. 定义是递归的

2. 数据结构是递归的3. 问题的求解方法是递归的

递归函数和非递归函数的转变

1. 定义是递归的

有许多数学公式、数列等的定义是递归的。这些问题的求解过程可以将其递归定义直接转化为对应

的递归算法。例如,求Fibonacci数列:n, n 0,1 Fib(n) Fib(n 1) Fib(n 2), n 1

递归函数和非递归函数的转变

2. 数据结构是递归的 有些数据结构是递归的。例如,第2章中介绍过的单 链表就是一种递归数据结构,其结点类型定义如下：typedef struct LNode { ElemType data; struct LNode *next;

} LinkList;

递归函数和非递归函数的转变

对于递归数据结构,采用递归的方法编写算法既方 便又有效。例如,求一个不带头结点的单链表head的所 有data域(假设为int型)之和的递归算法：int Sum(LinkList *head) { if (head==NULL) return 0;

elsereturn (head->data+Sum(head->next)); }

递归函数和非递归函数的转变

3. 问题的求解方法是递归的 有些问题的解法是递归的,典型的有汉诺塔(Tower of Hanoi)问题求解：

盘片移动时必须遵守以下规则： 每次只能移动一个盘片； 盘片可以插在A,B和C中任一塔座； 不能将一个较大的盘片放在较小的盘片上。

递归函数和非递归函数的转变

Hanoi(n,a,b,c)

Hanoi(n-1,a,c,b);

move(n,a,c); Hanoi(n-1,b,a,c)

递归函数和非递归函数的转变

6.1.3 递归模型递归模型是递归算法的抽象,它反映递归问题的 递归结构,例如,前面的递归算法对应的递归模型如下： fun(0)=1 fun(n)=n*fun(n-1) n=0 (1) n>0 (2)

其中：第一个式子给出了递归的终止条件,我们称 之 为 递 归 出 口 ； 第 二 个 式 子 给 出 了 fun(n) 的 值 与 fun(n-1)的值之间的关系，我们称之为递归体。

递归函数和非递归函数的转变

一般地,一个递归模型是由递归出口和递归体两部 分组成, 前者确定递归到何时结束, 后者确定递归求解 时的递推关系。 递归出口的一般格式如下： f(s1)=m1 (6.1)

这里的s1 与m1 均为常量,有些递归问题可能有几个 递归出口。

递归函数和非递归函数的转变

递归体的一般格式如下：

f(sn+1)=g(f(si),f(si+1),…,f(sn),cj,cj+1,…,cm)

其中,

(6.2)

n,i,j,m均为正整数。sn+1是一个递归“大问题”, si,si+1,…,sn为递归“小问题”, cj,cj+1,…,cm是可以用非递归方法直接解决的问题 g是一个非递归函数,可以直接求值。

递归函数和非递归函数的转变

递归思路实际上, 递归思路是把一个不能或不好直接求解

的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题” 来解决,如此分解,直至每个“小问题”都可以直接解 决(此时分解到递归出口)。 但递归分解不是随意的分解,递归分解要保证“大

问题”与“小问题”相似,即求解过程与环境都相似。并且有一个分解的终点。从而使问题可解。