启迪管理课程1
第 6章 递归
6.1 什么是递归
6.2 递归调用的实现原理本章小结启迪管理课程2
6.1.1 递归的定义在定义一个过程或函数时 出现调用本过程或本函数的成分,称之为递归。若调用自身,
称之为直接递归。若过程或函数 p调用过程或函数 q,而 q又调用 p,称之为间接递归。
6.1 什么是递归启迪管理课程3
例 6.1 以下是求 n!(n为正整数 )的递归函数 。
6.1 什么是递归
int fun(int n)
{ int x;
if (n==1) /*语句 1*/
return (1); /*语句 2*/
else /*语句 3*/
return(fun(n-1)*n); /*语句 4*/
}
在该函数 fun(n)求解过程中,直接调用 fun(n-1)(语句 4)自身,所以它是一个 直接递归函数 。又由于递归调用是最后一条语句,所以它又属于 尾递归 。
启迪管理课程4
6.1.2 何时使用递归递归使用的场合有如下三种:
1,定义是递归的数学公式、数列等的定义是递归的,例:
这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。
1!n1) ! *1(! 时,nnnn
1)2()1()2()1()( ffnfnfnf
6.1 什么是递归启迪管理课程5
2,数据结构是递归的有些数据结构是递归的。例如,单链表就是一种递归数据结构,其结点类型定义如下:
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LinkList;
该定义中,结构体 LNode的定义中用到了它自身,即指针域 next是一种指向自身类型的指针,所以它是一种递归数据结构。
6.1 什么是递归启迪管理课程6
求一个不带头结点的单链表 head的所有 data域 (假设为
int型 )之和的递归算法如下:
int Sum(LinkList *head)
{
if (head==NULL) return 0;
else return(head->data+Sum(head->next));
}
head a1 a2 an ^…...
非递归的算法,
p=head; sum=0;
while (p!=NULL) {sum=sum+p->data; p=p->next;}
6.1 什么是递归递归算法:
启迪管理课程7
3,问题的求解方法是递归的典型的有 Hanoi问题求解
6.1 什么是递归启迪管理课程8
6.1 什么是递归例:计算两个非负整数 a*b的算法
int Mul1(int a,int b)
{ int i,c=0;
for(i=0;i<a;i++)
c+=b;
return c;
}
2.递归方式,a*b=b+(a-1)*b1.迭代方式,a*b=a个 b之和
int Mul2(int a,int b)
{ if(a==0) return 0;
else return(b+Mul2(a-1,b)
}
启迪管理课程9
6.1 什么是递归
递归的关键点:
递归的实现,递归过程都是通过 栈 来实现的,
并且任何递归算法均可通过栈改写为非递归算法。
① 用 较简单 的 新问题 来表示较复杂的原问题。例如
n!=n(n-1)!或 n!=(n+1)!/(n+1) 前者 (n-1)!较 n!
简单,可行;后者 (n+1)!较 n!更复杂,不可行。
② 不能产生自己调用自己的 无穷序列,即必须有一个递归调用序列的,出口,,来终止递归调用。
启迪管理课程10
6.1 什么是递归
递归的特点,是程序设计的一个强有力的工具,它具有结构清晰,程序易编、易读、易调试,程序正确性易证明等优点;但运行效率低。
递归基本原理,是重复地把问题转化为与原问题相似的新问题,直到问题可以解决为止。
启迪管理课程11
6.1.3 递归模型递归模型 是递归算法的抽象,它反映一个递归问题的递归结构,由两部分构成对阶乘递归算法:
fun(1)=1 递归的终止条件,称递归出口
fun(n)=n*fun(n-1) n>1 递推关系,称递归体递归出口 递归的终止条件,其一般格式为:
f(s1)=m1
递归体 递推关系,其格式一般为:
f(sn+1)=g(f(si),f(si+1),…,f(s n),cj,cj+1,…,c m)
6.1 什么是递归启迪管理课程12
为了讨论方便,简化上述递归模型为:
f(s1)=m1
f(sn)=g(f(sn-1),c)
f(sn)的分解过程如下:
f(sn) f(sn-1) … f(s 2) f(s1)
6.1 什么是递归
g(f(s1),c1) g(f(s1),c1) … g(f(s 1),c1) m
f(sn)的求值过程如下:
启迪管理课程13
6.2递归调用的实现原理函数调用,子程序相同,但参量、输入数据不同代码共享现场保护:返回地址,当前参量值求阶乘 5!的递归过程
int fun(int n)
{ int x;
if (n==1) x=1;
else x=fun(n-1)*n;
return(x);
}
int fun(int n)
{ int x;
if (n==1) /*1*/
x=1; /*2*/
else /*3*/
x=fun(n-1)*n; /*4*/
return(x); /*5*/
}
求阶乘 5!的递归过程
//n=5
返址 n
//n=4
fun(4) 5
fun(3) 4
int fun(int n)
{ int x;
if (n==1) /*1*/
x=1; /*2*/
else /*3*/
x=fun(n-1)*n; /*4*/
return(x); /*5*/
}
求阶乘 5!的递归过程
//n=3
返址 n
//n=2
fun(4) 5
fun(3) 4
fun(2) 3
fun(1) 2
int fun(int n)
{ int x;
if (n==1) /*1*/
x=1; /*2*/
else /*3*/
x=fun(n-1)*n; /*4*/
return(x); /*5*/
}
求阶乘 5!的递归过程
//n=1
返址 n
fun(4) 5
fun(3) 4
fun(2) 3
x=2 fun(1) 2
fun(1) 2
int fun(int n)
{ int x;
if (n==1) /*1*/
x=1; /*2*/
else /*3*/
x=fun(n-1)*n; /*4*/
return(x); /*5*/
}
求阶乘 5!的递归过程返址 n
fun(4) 5
fun(3) 4
fun(2) 3
fun(2) 3
x=6
启迪管理课程18
求解 fun(5)的过程如下:
fun(5)
d1:fun(4)
d2:fun(3)
d3:fun(2)
d4:fun(1)
返回 1
fun(2)=2
fun(3)=6
fun(4)=24
fun(5)=120
启迪管理课程19
本 章 小 结本章基本学习要点如下:
(1)理解递归的定义和递归模型 。
(2)能够阅读递归算法,并在必要的时候能用递归编写算法 。
(3)重点掌握递归的执行过程 。
启迪管理课程20
作业:
设带头结点的线性表中元素值为非零正整数,试写出:
(1)求线性表中所有元素之和的递归函数 (空表返回 0)
(2)求线性表中元素最大值的递归函数(空表返回 0)
(3)求线性表中元素个数的递归函数(空表返回 0)
第 6章 递归
6.1 什么是递归
6.2 递归调用的实现原理本章小结启迪管理课程2
6.1.1 递归的定义在定义一个过程或函数时 出现调用本过程或本函数的成分,称之为递归。若调用自身,
称之为直接递归。若过程或函数 p调用过程或函数 q,而 q又调用 p,称之为间接递归。
6.1 什么是递归启迪管理课程3
例 6.1 以下是求 n!(n为正整数 )的递归函数 。
6.1 什么是递归
int fun(int n)
{ int x;
if (n==1) /*语句 1*/
return (1); /*语句 2*/
else /*语句 3*/
return(fun(n-1)*n); /*语句 4*/
}
在该函数 fun(n)求解过程中,直接调用 fun(n-1)(语句 4)自身,所以它是一个 直接递归函数 。又由于递归调用是最后一条语句,所以它又属于 尾递归 。
启迪管理课程4
6.1.2 何时使用递归递归使用的场合有如下三种:
1,定义是递归的数学公式、数列等的定义是递归的,例:
这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。
1!n1) ! *1(! 时,nnnn
1)2()1()2()1()( ffnfnfnf
6.1 什么是递归启迪管理课程5
2,数据结构是递归的有些数据结构是递归的。例如,单链表就是一种递归数据结构,其结点类型定义如下:
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LinkList;
该定义中,结构体 LNode的定义中用到了它自身,即指针域 next是一种指向自身类型的指针,所以它是一种递归数据结构。
6.1 什么是递归启迪管理课程6
求一个不带头结点的单链表 head的所有 data域 (假设为
int型 )之和的递归算法如下:
int Sum(LinkList *head)
{
if (head==NULL) return 0;
else return(head->data+Sum(head->next));
}
head a1 a2 an ^…...
非递归的算法,
p=head; sum=0;
while (p!=NULL) {sum=sum+p->data; p=p->next;}
6.1 什么是递归递归算法:
启迪管理课程7
3,问题的求解方法是递归的典型的有 Hanoi问题求解
6.1 什么是递归启迪管理课程8
6.1 什么是递归例:计算两个非负整数 a*b的算法
int Mul1(int a,int b)
{ int i,c=0;
for(i=0;i<a;i++)
c+=b;
return c;
}
2.递归方式,a*b=b+(a-1)*b1.迭代方式,a*b=a个 b之和
int Mul2(int a,int b)
{ if(a==0) return 0;
else return(b+Mul2(a-1,b)
}
启迪管理课程9
6.1 什么是递归
递归的关键点:
递归的实现,递归过程都是通过 栈 来实现的,
并且任何递归算法均可通过栈改写为非递归算法。
① 用 较简单 的 新问题 来表示较复杂的原问题。例如
n!=n(n-1)!或 n!=(n+1)!/(n+1) 前者 (n-1)!较 n!
简单,可行;后者 (n+1)!较 n!更复杂,不可行。
② 不能产生自己调用自己的 无穷序列,即必须有一个递归调用序列的,出口,,来终止递归调用。
启迪管理课程10
6.1 什么是递归
递归的特点,是程序设计的一个强有力的工具,它具有结构清晰,程序易编、易读、易调试,程序正确性易证明等优点;但运行效率低。
递归基本原理,是重复地把问题转化为与原问题相似的新问题,直到问题可以解决为止。
启迪管理课程11
6.1.3 递归模型递归模型 是递归算法的抽象,它反映一个递归问题的递归结构,由两部分构成对阶乘递归算法:
fun(1)=1 递归的终止条件,称递归出口
fun(n)=n*fun(n-1) n>1 递推关系,称递归体递归出口 递归的终止条件,其一般格式为:
f(s1)=m1
递归体 递推关系,其格式一般为:
f(sn+1)=g(f(si),f(si+1),…,f(s n),cj,cj+1,…,c m)
6.1 什么是递归启迪管理课程12
为了讨论方便,简化上述递归模型为:
f(s1)=m1
f(sn)=g(f(sn-1),c)
f(sn)的分解过程如下:
f(sn) f(sn-1) … f(s 2) f(s1)
6.1 什么是递归
g(f(s1),c1) g(f(s1),c1) … g(f(s 1),c1) m
f(sn)的求值过程如下:
启迪管理课程13
6.2递归调用的实现原理函数调用,子程序相同,但参量、输入数据不同代码共享现场保护:返回地址,当前参量值求阶乘 5!的递归过程
int fun(int n)
{ int x;
if (n==1) x=1;
else x=fun(n-1)*n;
return(x);
}
int fun(int n)
{ int x;
if (n==1) /*1*/
x=1; /*2*/
else /*3*/
x=fun(n-1)*n; /*4*/
return(x); /*5*/
}
求阶乘 5!的递归过程
//n=5
返址 n
//n=4
fun(4) 5
fun(3) 4
int fun(int n)
{ int x;
if (n==1) /*1*/
x=1; /*2*/
else /*3*/
x=fun(n-1)*n; /*4*/
return(x); /*5*/
}
求阶乘 5!的递归过程
//n=3
返址 n
//n=2
fun(4) 5
fun(3) 4
fun(2) 3
fun(1) 2
int fun(int n)
{ int x;
if (n==1) /*1*/
x=1; /*2*/
else /*3*/
x=fun(n-1)*n; /*4*/
return(x); /*5*/
}
求阶乘 5!的递归过程
//n=1
返址 n
fun(4) 5
fun(3) 4
fun(2) 3
x=2 fun(1) 2
fun(1) 2
int fun(int n)
{ int x;
if (n==1) /*1*/
x=1; /*2*/
else /*3*/
x=fun(n-1)*n; /*4*/
return(x); /*5*/
}
求阶乘 5!的递归过程返址 n
fun(4) 5
fun(3) 4
fun(2) 3
fun(2) 3
x=6
启迪管理课程18
求解 fun(5)的过程如下:
fun(5)
d1:fun(4)
d2:fun(3)
d3:fun(2)
d4:fun(1)
返回 1
fun(2)=2
fun(3)=6
fun(4)=24
fun(5)=120
启迪管理课程19
本 章 小 结本章基本学习要点如下:
(1)理解递归的定义和递归模型 。
(2)能够阅读递归算法,并在必要的时候能用递归编写算法 。
(3)重点掌握递归的执行过程 。
启迪管理课程20
作业:
设带头结点的线性表中元素值为非零正整数,试写出:
(1)求线性表中所有元素之和的递归函数 (空表返回 0)
(2)求线性表中元素最大值的递归函数(空表返回 0)
(3)求线性表中元素个数的递归函数(空表返回 0)