- 60-中国科技信息2006年第三期chinascienceandtechnologyinformationfeb.2006科技论坛} }引言在计算机科学中，递归概念是递归调用方面，即函数或过程自身使用递归调用的算法是递归算法，递归调用没有终止运算的可能性，所以在适当的情况下必须终止递归调用。 计算机分析所需的资源数常常用和的形式或递推公式的形式来表示。 大多数算法的执行表现为根据一定条件反复执行几个循环，但这些循环往往可以用递归关系来表示。 这使得求解递归方程对算法分析非常重要。 1 )时间复杂度分析和递归方程算法的时间复杂度度量经常通过循环次数统计、基本操作频率统计、计算步长统计等进行分析。 以用分割统治法解决最大最小问题为例，问题记述如下。 企业老板拿着一袋金块，其中最重的选他优秀的员工，最轻的选他一般的员工。 可以将该问题转换为在具有n个元素的数组中查找关键字最大和最小的元素的问题。 其安装代码为整数数组A[]、数组的开始边界和结束边界low和high； 输出：最大元素e_max和最小元素e_min。 voidmaxmin(inta[]，int e_max，e_min，int low，int high ) { int mid，x1，y1，x2，y2； if () high-low )=1) if ) a[high]a[low] ) { e_max=A[high]； e_min=A[low]； } else { e_max=A[low]； e_min=A[high]； else{mid=(lowhigh )/2； maxmin(a，x1，y1，low，mid )； maxmin(a，x2，y2，mid 1，high )； e_max=max(x1，x2 )； e_min=min(y1，y2 )； c(n )表示算法对n个要素的数组执行的比较次数，通过将比较操作视为基本操作来测量算法的时间复杂度。 可以列举如下递归方程式。 2、生成函数求解递归方程式的定义1令a 0、a 1、a 2为实数系列，构建以下函数。 算法时间复杂度分析中递归方程的求解方法综述了ssdxn失眠的大树胡重庆文理学院数学与计算机科学系402160摘要。 算法分析中计算的复杂性表现为常用的递归关系，递归方程的求解有助于分析算法设计的好坏。 一般递归方程的求解方法有生成函数法、特征方程法、推理法等。 递归树法和主法给出了递归方程计算复杂度的渐进表示。 关键词：生成函数； 特征方程； 递归； 递归树； 主方法[中图分类号]TP301.6 [文献识别代码]A将函数g(z )称为系列a0、a1、a2、的生成函数. 哭泣的枫叶那契序列问题：假设兔子每隔一个月长成完美的棉花糖，完美的棉花糖每隔一个月生一次兔子。 第一个月有兔子。 n个月后有多少只兔子？ 假设t(n )、t ) n )分别表示第n个月的兔子、完美的棉花糖的数量，f ) n )是第n个月的兔子的总数，则t ) n )=t(n-1 ) t ) ) n )=t(n-1 ) 求解特征方程的递归方程除了用生成函数求解递归方程外，还可以用递归方程的特征方程求解。 3.1 k次常数系数线性一次递归方程定义2形是将上式称为递归方程的特征方程。 可以求出特征