归本程上太军 一、 递归的概念 SHANDONG UNIVERSITY OF TECHNOLOGY 器会合会品会3会 例3 Ackermani函数 前2例中的函数都可以找到相应的非递归方式定义： nl=1.2.3.(n-1)n - 本例中的Ackerman函数却无法找到非递归的定义。 2025年4月3日 11
2025年4月3日 11 一、递归的概念 例3 Ackerman函数 前2例中的函数都可以找到相应的非递归方式定义： n!= 1 2 3(n −1) n − − + = +1 +1 2 1 5 2 1 5 5 1 ( ) n n F n 本例中的Ackerman函数却无法找到非递归的定义
白东程子太军 一、递归的概念 HANDONG UNIVERSITY OF TECINOLOGY 3会清34合3会3会空A是会品 ●例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时， 称这个函数是双递归函数。 ●Ackerman函数A(n,m)定义如下： A(1,0)=2 A(0,m)=1 m≥0 A(n,0)=n+2 n≥2 A(n,m)=A(A(n-1,m),m-1) n,m≥1 2025年4月3日 12
2025年4月3日 12 一、递归的概念 ⚫ 例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时， 称这个函数是双递归函数。 ⚫ Ackerman函数A(n，m)定义如下： = − − = + = = , 1 2 0 ( , ) ( ( 1, ), 1) ( ,0) 2 (0, ) 1 (1,0) 2 n m n m A n m A A n m m A n n A m A
归本程上太军 递归的概念 SHANDONG UNIVERSITY OF TECINOLOGY 一、 ●例4排列问题 设计一个递归算法生成n个元素{r1,r2,.,rn}的全排列。 设R={1r2,rn}是要进行排列的n个元素，R=R-{r。 集合X中元素的全排列记为perm(X)。 (r)perm(X)表示在全排列perm(X)的每一个排列前加上前 缀r得到的排列。R的全排列可归纳定义如下： 当n=l时，perm(R)=(r),其中r是集合R中唯一的元素； 当n>l时，perm(R)由(r1)perm(R),(r2perm(Rz),. (rn)perm(Rn)构成。 2025年4月3日 13
2025年4月3日 13 一、递归的概念 ⚫例4 排列问题 设计一个递归算法生成n个元素{r1 ,r2 ,.,rn }的全排列。 设R={r1 ,r2 ,.,rn }是要进行排列的n个元素，Ri=R-{ri }。 集合X中元素的全排列记为perm(X)。 (ri )perm(X)表示在全排列perm(X)的每一个排列前加上前 缀ri得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n>1时，perm(R)由(r1 )perm(R1 )，(r2 )perm(R2 )，.， (rn )perm(Rn )构成
白东程子太军 SHANDONG UNIVERSITY OF TECINOLOGY 华绿修空点冷华会品品 ●template<class T:> void perm(T list[],int k,int m) 思想：当首项和最后一 ●{W产生Iist[k:m]的所有排列 项相等，说明排列结束 ●if(k==m) ● {川单元素排列 就需要输出了 ● for (int i=0;i<=m;i++)cout <list[i]; 当首项和最后一 ● cout <endl; 项不同，首先利用循环 ● } 把首项和循环中的每一 ●else 项对调作为首字符（或 ● {川多元素序列，递归产生排列 数字)，之后进行从后 ● for (int i=k;i<=m;i++) ● 一 位开始的全排列。再 ● swap(list[k],list[i]); 循环中需要把交换过去 ● perm(list,k+1,m); 的，再换回来一边下一 ● swap(list[k],list[i]); 次进行循环时候使用。 ● ● 2025年4月3日 14
2025年4月3日 14 ⚫ template <class T> ⚫ void perm(T list[], int k, int m) ⚫ {//产生list[k:m]的所有排列 ⚫ if (k==m) ⚫ {//单元素排列 ⚫ for (int i=0; i<=m; i++) cout << list[i]; ⚫ cout << endl; ⚫ } ⚫ else ⚫ {//多元素序列，递归产生排列 ⚫ for (int i=k; i<=m; i++) ⚫ { ⚫ swap(list[k],list[i]); ⚫ perm(list,k+1,m); ⚫ swap(list[k],list[i]); ⚫ } ⚫ } 思想：当首项和最后一 项相等，说明排列结束 就需要输出了 当首项和最后一 项不同，首先利用循环 把首项和循环中的每一 项对调作为首字符（或 数字），之后进行从后 一位开始的全排列。再 循环中需要把交换过去 的，再换回来一边下一 次进行循环时候使用
归本程子末军 一、递归的概念 SHANDONG UNIVERSITY OF TECINOLOGY 华器会空空合安会器空会的会路 ●例5整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2++nk, 其中n1≥n2≥.≥nk21,k21。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。 例如：正整数6有如下11种不同的划分： 6: 5+1: 4+2,4+1+1: 3+3,3+2+1,3+1+1+1: 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1。 2025年4月3日 15
2025年4月3日 15 一、递归的概念 ⚫例5 整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2+.+nk， 其中n1≥n2≥.≥nk≥1，k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。 例如：正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1