离散数学─归纳与递归 南京大学计算机科学与技术系
内容提要 递归定义 结构归纳法 递归算法
递归定义（N上的函数） 递归地定义自然数集合N上的函数。 举例，阶乘函数F(n)=n!的递归定义 基础步骤：指定这个函数在0处的值； 递归步骤：给出从较小处的值来求出当前的值之规则。 举例，阶乘函数F(n)=n!的递归定义 F(0)=1 F(n)=nF(n-1) for n>0
Fibonacci 序列 Fibonacci 序列 {fn} 定义如下 其前几个数 证明：对任意n 0， 其中， f0 = 0, fn = fn – 1 + fn –2, 对任意n 2. 其前几个数 0, 1, 1, 2, 3, 5, 8, … 证明：对任意n 0， 其中，
归纳证明: Fibonacci 序列 验证：当n=0,1时，陈述正确。 对于k+1, 注意：2 = + 1，且n + 1 = n + n – 1 对任意n 1.
归纳证明: Fibonacci 序列
递归定义（集合） 递归地定义集合。 举例，正整数集合的一个子集S，定义如下： 基础步骤：指定一些初始元素； 递归步骤：给出从集合中的元素来构造新元素之规则； 排斥规则（只包含上述步骤生成的那些元素）默认成立 举例，正整数集合的一个子集S，定义如下： 2S 若xS且yS，则 x+yS。
递归定义（举例） 字母表上的字符串集合*。 字符串的长度（ *上的函数l）。 基础步骤：* （表示空串）; 递归步骤：若 * 且x ，则x * 。 字符串的长度（ *上的函数l）。 基础步骤：l()=0; 递归步骤：l(x) = l() +1, 若 * 且x
递归定义（举例） *上的字符串连接运算。 基础步骤：若 *，则 =; 递归步骤：若1 * 且2 * 以及x ，则 1 (2 x) = (1 2) x 。 // 1 2通常也写成1 2
递归定义（举例） 复合命题的合式公式。 基础步骤：T, F, p都是合式公式，其中p是命题变元; 递归步骤：若E和F是合式公式，则 (E)、(EF)、 (EF)和(EF) 都是合式公式。
结构归纳法 关于递归定义的集合的命题，进行结构归纳证明。 结构归纳法的有效性源于自然数上的数学归纳法 基础步骤：证明对于初始元素来说，命题成立; 递归步骤：针对生产新元素的规则，若相关元素满足命题，则新元素也满足命题 结构归纳法的有效性源于自然数上的数学归纳法
结构归纳法（举例） l(xy) = l(x) + l(y), x和y属于 * 。 证明 设P(y)表示：每当x属于 * ，就有l(xy) = l(x) + l(y) 。 基础步骤：每当x属于 * ，就有l(x) = l(x) + l() 。 递归步骤：假设P(y)为真，a属于 , 要证P(ya)为真。 即：每当x属于 * ，就有l(xya) = l(x) + l(ya) P(y)为真，l(xy) = l(x) + l(y) l(xya)= l(xy)+1= l(x) + l(y)+1=l(x) + l(ya)
广义结构归纳法（举例） NN是良序的 递归定义am,n 归纳证明 am,n= m + n(n+1)/2 a0,0 = 0 am,n= am-1,n +1 (n=0, m>0) am,n= am,n-1 +n (n>0) 归纳证明 am,n= m + n(n+1)/2 0 1 3 1 2 4 2 3 5
递归算法（欧几里德算法） 递归算法的正确性 递归算法的复杂性 （时间、空间） function gcd(a, b) // ab0, a>0 if b=0 return a else return gcd(b, a mod b) 递归算法的正确性 递归算法的复杂性 （时间、空间）
欧几里德算法的复杂性 Let r0=a, r1=b. qi1 for 1in qn2 because qn= rn-1/rn 1 Let r0=a, r1=b. qi1 for 1in qn2 because qn= rn-1/rn 1 rn1= f2, rn-12rn 2= f3 b=r1r2+r3 fn+fn –1=fn+1n-1 log10 b (n-1)log10 for n2 log10 >1/5
递归算法的设计
作业 教材[4.3, 4.4] P232-236：24, 32, 34, 47, 52 P244-245：36, 37