递归的例子例3整数划分问题.1n= 1,m=1q(n,n)n<mq(n,m) =1 +q(n,n -1)n=mn>m>lq(n,m -l) +g(n -m,m)正整数n的划分数p(n)=q(n,n)。11niversity of Science and Technology of China
11 University of Science and Technology of China 递归的例子 = = = − + − + − = 1 1, 1 ( , 1) ( , ) 1 ( , 1) ( , ) 1 ( , ) n m n m n m n m q n m q n m m q n n q n n q n m 例3 整数划分问题 。 正整数n的划分数p(n)=q(n,n)
递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占角的存储空间都比非递归算法要多12niversity of cience and Technology of China
12 University of Science and Technology of China 递归小结 优点：结构清晰，可读性强，而且容易用数学归纳法 来证明算法的正确性，因此它为设计算法、调试程序 带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算 时间还是占用的存储空间都比非递归算法要多
NIYERSITOYOY4CHINA递归小结解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显用递推来实现递归函数3、通过变换能将一些递归转化为尾递归，从而迭代求出结果后两种方法在时空复杂度上均有较大改善，但其适用范围有限13niversity of cience andTechnology of China
13 University of Science and Technology of China 递归小结 解决方法：在递归算法中消除递归调用，使其转化为非递归算法。 1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法 通用性强，但本质上还是递归，只不过人工做了本来由编译器做的 事情，优化效果不明显。 2、用递推来实现递归函数。 3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限