先考虑特殊情况。递归出口然后假设n=k-1成立（第二数学归纳法是假设n≤k-1均成递归体立），再证明n=时成立，即假设“小问题”成立，再推导出“大问题”成立。递归出口相当于数学归纳法的特殊情况。递归体相当于数学归纳法的归纳步骤。区别：数学归纳法是一种论证方法，递归是算法和程序设计的一种实现技术。数学归纳法是递归求解问题的理论基础。16/66
先考虑特殊情况。 然后假设n=k-1成立（第二数学归纳法是假设n≤k-1均成 立），再证明n=k时成立，即假设“小问题”成立，再推导 出“大问题”成立。 递归出口 递归体 递归出口相当于数学归纳法的特殊情况。 递归体相当于数学归纳法的归纳步骤。 区别：数学归纳法是一种论证方法，递归是算法和程序 设计的一种实现技术。 数学归纳法是递归求解问题的理论基础。 16/66
递归的执行过程5.1.5简化的递归模型f(si)=mi求大问题f(sn):f(sn)=g(f(sn-1), Cn-1)分解（递推）和其值求f(sn)的分解过程如下：f(sn)↓f(Sn-1)--0-3f(s1)17/66
简化的递归模型 f(s1)=m1 f(sn)=g(f(sn-1)，cn-1) f(sn) ↓ f(sn-1) ↓ . ↓ f(s2) ↓ f(s1) 求f(sn)的分解过程如下： 求大问题f(sn)： 分解（递推）和其值 17/66
遇到递归出口发生“质变”，原递归问题便转化成可以直接求解的问题求值过程:f(s1)=mi+f(s2)=g(f(s1),C1)+f(s3)=g(f(s2),C2)f(Sn)=g(f(sn-1),Cn-1)18/66
遇到递归出口发生“质变” ，原递归问题便转化成可以直接求解的问题。 求值过程： f(s1)=m1 ↓ f(s2)=g(f(s1),c1) ↓ f(s3)=g(f(s2),c2) ↓ . ↓ f(sn)=g(f(sn-1),cn-1) 18/66
例如求5！。fun(5)=120fun(5)fun(4)fun(4)=24fun(3)fun(3)=61F慢书fun(2)fun(2)=2拉彩fun(1)返回119/66
例如求5!。 fun(5) fun(4) fun(3) fun(2) fun(1) r 返回1 fun(2)=2 fun(3)=6 fun(4)=24 fun(5)=120 19/66
系统内部如何执行递归算法一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。（1）执行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址。（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址进栈。（3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。20/66
一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用 函数和被调用函数是同一个函数。 为了保证递归函数的正确执行，系统需设立一个工作栈。 （1）执行开始时，首先为递归调用建立一个工作栈，其结构包括值 参、局部变量和返回地址。 （2）每次执行递归调用之前，把递归函数的值参和局部变量的当前 值以及调用后的返回地址进栈。 （3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部 变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。 20/66