n=4结束11/66
n=4 结束 11/66
递归模型5.1.3递归模型是递归算法的抽象，它反映一个递归问题的递归结构。int fun(int n)//语句1{if (n==1)//语句2return(1);1/语句3else//语句4return(fun(n-1)*n);递归模型f(n)=1n=1n>1f(n)=n*f(n-1)12/66
递归模型是递归算法的抽象，它反映一个递归问题的递归结构。 int fun(int n) { if (n==1) //语句1 return(1); //语句2 else //语句3 return(fun(n-1)*n); //语句4 } f(n)=1 n=1 f(n)=n*f(n-1) n>1 递归模型 12/66
递归出口f(n)=1n=1f(n)=n*f(n-1)递归体n>1一般地，一个递归模型是由递归出口和递归体两部分组成。递归出口确定递归到何时结束，即指出明确的递归结束条件。递归体确定递归求解时的递推关系。13/66
f(n)=1 n=1 f(n)=n*f(n-1) n>1 递归出口 递归体 一般地，一个递归模型是由递归出口和递归体两部分组成。 递归出口确定递归到何时结束，即指出明确的递归结束条件。 递归体确定递归求解时的递推关系。 13/66
递归出口的一般格式如下：f(S1)=mi递归体的一般格式如下：f(Sn)=g(f(St)f(Sita),，f(Sn-)0Cj+12Cjo非递归函数大问题求解f(sn)转化f(si)f(Si+1)f(Sn-1)若千个相似子问题求解14/66
递归出口的一般格式如下： 递归体的一般格式如下： f(sn) f(si) f(si+1) . f(sn-1) 大问题求解 若干个相似子问题求解 转化 非递归函数 14/66
5.1.4递归与数学归纳法采用数学归纳法证明1+2++n=n（n+1）/2当n=1时，左式=1，右式=（1×2)/2=1，左右两式相等，等式成立。假设当n=k-1时等式成立，有1+2+…+(k-1)=k(k-1)/2。当n=k时，左式=1+2++k=[1+2++(k-1)+k=k(k-1)/2+k=k(k+1)/2。先考虑特殊情况。然后假设n=k-1成立（第二数学归纳法是假设n≤k-1均成立），再证明n=R时成立，即假设“小问题”成立，再推导出“大问题”成立。15/66
采用数学归纳法证明1+2+.+n=n(n+1)/2 当n=1时，左式=1，右式=(1×2)/2=1，左右两式相等，等式成立。 假设当n=k-1时等式成立，有1+2+.+(k-1)=k(k-1)/2。 当n=k时，左式=1+2+.+k=[1+2+.+(k-1)+k=k(k-1)/2+k=k(k+1)/2。 先考虑特殊情况。 然后假设n=k-1成立（第二数学归纳法是假设n≤k-1均成立），再证 明n=k时成立，即假设“小问题”成立，再推导出“大问题”成立。 15/66