4 递推与递归.ppt

递归算法总体思想 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 递归算法总体思想 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 递归算法总体思想 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。 递推与递归的关系 相同点：数据元素之间的关系可以用抽象的、严格的公式表示出来，且不论是递推关系式还是递归公式，都具有边界条件。 不同点：递推是从边界条件出发，通过递推关系式求f(n)的值，从边界到目标解的过程清楚直观；而递归是从函数自身出发来达到边界条件，在通往边界的递归过程中，系统需要用栈把每次调用的现场（中间结果）保存下来，供递归返回时使用（恢复现场）。递归程序是高度概括的，并不能体现出这个复杂的过程，实际上这是由操作系统来完成的。 关系：递归与递推可以相互转换，具体应用时主要看哪种解法更加简便高效(测试递归法求FIB数列的效率)。 描述递归定义的函数或求解递归问题的过程称为递归算法。 递归算法有其致命的缺点：执行的效率很低，尤其在边界条件设置不当的情况下，极有可能陷入死循环或者内存溢出的窘境。 递归算法一般适用在三个场合： 1、数据的定义形式是递归的，如Fibonacci数列； 2、数据之间的逻辑关系（数据结构）是递归的，如树、图等的定义和操作； 3、某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束，如汉诺塔问题。 所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。 递归小结 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 解决方法：在递归算法中消除递归调用，使其转化为非递归算法。 采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。 用递推来实现递归函数。 1、递推和动态规划概述 递推是从问题的初始状态（由已知的若干数据项表示）出发，通过状态之间的逻辑关系，逐步地层层推进，实现状态的转移，从而达到目标状态（期望的最终结果）的解题方法。简单说来，递推就是指一个数的序列H1，H2，H3，……，Hn，其中Hn可用H1，……，Hn-1来表示。本题的初始状态为fib(1)=1，fib(2)=1。状态之间的关系为fib(n) = fib(n-1) + fib(n-2)。目标状态为fib(n)。