常见的递归形式 除基本的递归形式外,其它常见的递归 形式有四种,它们是: ■多变元递归 ■多步递归; ■嵌套递归; ■联立递归 2021/221 计算机算法设计与分析 6
2021/2/21 计算机算法设计与分析 6 常见的递归形式 ◼ 多变元递归； ◼ 多步递归； ◼ 嵌套递归； ◼ 联立递归 • 除基本的递归形式外，其它常见的递归 形式有四种，它们是：
多变元递归 例2:整数划分问题:将一个正整数n表示为 一系列正整数之和, n=n1+n2+…+nk 其中n1>n2≥…n21,k>1。 例如p(6)=11,即整数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 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 7 多变元递归 •◼例多变元递归就是递归元多于一个的递归。 2：整数划分问题：将一个正整数n表示为 一系列正整数之和， n = n1 + n2 +…+nk 其中n1≥n2≥…≥nk≥1, k≥1。 • 正整数n的一个这种表示称为正整数n的一个 划分。正整数n的不同的划分的个数成为正整 数n的划分数，记作ρ(n)。 • 例如ρ(6) = 11 ，即整数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
正整数的划分 在正整数的所有不同划分中,将最大加数n不 大于m的划分个数记为q(n,m),可以建立如下 的二元递归函数: q(n, m)i if(n< 1)(m<1) return 0 if(n m return 1 if(n===1)(n< m) return 1+q(n, n-1) return q(n, m-1)+q(n-m, m);) 整数n的划分数p(n)=q(n,n)。 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 8 正整数的划分 ◼ 在正整数的所有不同划分中，将最大加数n1不 大于m的划分个数记为q(n, m)，可以建立如下 的递归关系： ◼ 最简单情形：(1) q(n, 1)=1, q(1, m) =1 n, m≥1; ◼ 递归关系： (2) q(n, n) = 1 + q(n, n–1)，n＞1; ◼ 产生的新情况： ◼ (3) q(n, m) = q(n, m–1) + q(n–m, m), n＞m＞1 ◼ (4) q(n, m) = q(n, n), n＜m。 1 n = 1 或 m = 1 q(n, m) = 1 + q(n, n–1) n ≤ m q(n, m–1)+q(n–m, m) n＞m＞1 的二元递归函数： q(n, m) { if (n < 1) || (m < 1) return 0; if (n == 1) || (m == 1) return 1; if (n == 1) || (n < m) return 1 + q(n, n–1); return q(n, m–1) + q(n–m, m); } ◼ 整数n的划分数ρ(n) = q(n, n)
多步递归 若递归函数f(x,y),其中y是递归元,不仅与f(x, y-1)有关,而且与fx,y-2),……,乃至(x,0) 有关,则称为多步递归。 ■例如 Fibonacci数 n=0 F(n)=1 F(n-1)+F(n-2)n>1 Fibonacci函数是一个两步的递归函数 2021/221 计算机算法设计与分析 9
2021/2/21 计算机算法设计与分析 9 多步递归 ◼ 若递归函数f(x, y)，其中y是递归元，不仅与f(x, y–1)有关，而且与f(x, y–2)，……，乃至f(x, 0) 有关，则称为多步递归。 ◼ 例如Fibonacci函数： 1 n = 0 F(n) = 1 n = 1 F(n–1) + F(n–2) n > 1 ◼ Fibonacci函数是一个两步的递归函数
嵌套递归 ■所谓嵌套递归是指递归调用中又含有递归调用, 又称为多重递归 例如 Ackermann函数: +1 X=0 A(x,y)=A(x-1,1) 0 A(x-1,A(x,y-1)x,y>0 Ackermann函数是一个双重的递归函数。同时 它也是个二元递归。 2021/221 计算机算法设计与分析 10
2021/2/21 计算机算法设计与分析 10 嵌套递归 ◼ 所谓嵌套递归是指递归调用中又含有递归调用， 又称为多重递归。 ◼ 例如Ackermann函数： y + 1 x = 0 A(x, y) = A(x–1, 1) y = 0 A(x–1, A(x, y–1)) x, y > 0 ◼ Ackermann函数是一个双重的递归函数。同时 它也是个二元递归