递归函数的三个过程（函数怎么递归过程是怎么样的求解，在线等）

本文目录

• 函数怎么递归过程是怎么样的求解，在线等
• 解递归方程的三个方法

函数怎么递归过程是怎么样的求解，在线等

这应该是定义的一种运算，没有实际的应用背景。你可以举例加深理解，比如:开始形参m,n为5,3，由于5不能被3整除，不满足if条件，转向递归，此时形参变为3,2；接着进行递归中的函数调用，经调用后，不满足if条件，转向递归，形参变为2,1；此时递归调用满足if条件，返回1

解递归方程的三个方法

1、主方法求解递归式

一种求解大部分递归式的公式。给出递归式: T(n) = a * T(n/b) + f(n) ，其中a》=1，b》1，f(n)是给定的函数，T(n)是定义在非负整数上的递归式。

2、递归树求解

用主方法求解不了的递归式，我们可以用递归树来猜测解的上界，然后用代入法来证明解的正确性。递归树的求解精确度取决于画递归树的精确度。

3、代入法

比如我们求解，递归式T(n) = 2T(n/2)+n，我们猜测解是O(nlgn)，我们要寻找到一个常数c，使得T(n)《=cnlgn。

即T(n) 《= 2c(n/2)lg(n/2)+n 《= cnlgn-cnlg2+n = cnlgn-cn+n

只要c》=1，T(n)《=cnlgn，所以我们的猜测是正确的。

要注意的是，代入法全凭经验，通常用递归树来确定上界，然后用代入法再证明。

扩展资料：

设p0，p1，…，pn，…是一个序列。如果pn和序列中在它前面的若干项联系起来的一个关系式对所有大于等于某个整数n0的整数n都是有效的，则称这个关系式为递归关系(recursive relation)式。

如：设(a0，a1，...，ar，...)是一个序列，把该序列中的ar和它前面的几个ai(0≤i《r)关联起来的方程称做一个递归关系。如关系式:ar=3ar-1 (r≥1)和错排数:Dn=(n-1)(Dn-1+Dn-2) (n=3，4，...)，都是递归关系。