清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1递归的概念 例3 Ackerman函数 前2例中的函数都可以找到相应的非递归方式定义: n!=1.2·3…(n-1) n+1 F(n) 但本例中的 Ackerman函数却无法找到非递归的定义
2.1 递归的概念 例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函数却无法找到非递归的定义
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1递归的概念 例3 Ackerman函数 A(n,m)的自变量m的每一个值都定义了一个单变量函数 M=0时,A(n,0)=n+2 M=1时,A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2,和A(1,1)=2故 A(n,1)=2*n ·M=2时,A(n,2)=AAn-1,2,1)=2A(n-1,2),和 A(1,2)=A(A(0,2),1)=A(11)=2,故A(n,2)=2^n。 x32 M=3时,类似的可以推出 M=4时,A(n,4)的增长速度肀常快,以至于没有适当的数学式 子来表示这一函数
2.1 递归的概念 例3 Ackerman函数 • A(n，m)的自变量m的每一个值都定义了一个单变量函数： • M=0时，A(n,0)=n+2 • M=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故 A(n,1)=2*n • M=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和 A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n 。 • M=3时，类似的可以推出 • M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式 子来表示这一函数。 n 2 2 2 2
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1递归的概念 例3 Ackerman函数 定义单变量的 Ackerman函数A(n)为, A(n)=A(n,n)。 定义其拟逆函数an)为:an)=min伙 A()≥n}。即α(n)是使n≤A(k成立的最小的k α(n)在复杂度分析中常遇到。对于通常所见到 的正整数n,有m)≤4。但在理论上(n)没有 上界,随着n的增加,它以难以想象的慢速度 趋向正无穷大
2.1 递归的概念 例3 Ackerman函数 • 定义单变量的Ackerman函数A(n)为， A(n)=A(n，n)。 • 定义其拟逆函数α(n)为：α(n)=min{k｜ A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k 值。 • α(n)在复杂度分析中常遇到。对于通常所见到 的正整数n，有α(n)≤4。但在理论上α(n)没有 上界，随着n的增加，它以难以想象的慢速度 趋向正无穷大
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1递归的概念 例4排列问题 设计一个递归算法生成n个元素{r12.,rn}的全排列。 设R={12…,rn是要进行排列的n个元素,R=R{r} 集合X中元素的全排列记为perm(xX) r)perm(X表示在全排列perm(X)的每个排列前加上前 缀得到的排列。R的全排列可归纳定义如下 当n=1时,perm(R=(),其中r是集合R中唯一的元素 当n>1时,perm(R由(r1)perm(R1),(r2)perm(R2), rn)perm(Rn构成
2.1 递归的概念 例4 排列问题 设计一个递归算法生成n个元素{r1 ,r2 ,…,rn }的全排列。 设R={r1 ,r2 ,…,rn }是要进行排列的n个元素，Ri=R-{ri }。 集合X中元素的全排列记为perm(X)。 (ri )perm(X)表示在全排列perm(X)的每一个排列前加上前 缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n>1时，perm(R)由(r1 )perm(R1 )，(r2 )perm(R2 )，…， (rn )perm(Rn )构成
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1递归的概念 例5整数划分问题 将正整数n表示成一系列正整数之和:n=n1+n2++nk 其中n1≥n2≥…2nk≥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
2.1 递归的概念 例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