第六章基于树的工程性实用递归算法.doc

第六章 基于树的递归算法 本章将在第一章简单介绍递归基本概念、递归的6.1 算法的递归 则fibonacci数列值与下标n的关系如表6-1所示。 表6-1 fibonacci数列 n 0 1 2 3 4 5 6 7 8 9 10 fib(n) 0 1 1 2 3 5 8 13 21 34 55 求和过程 0 1 0+1 1+1 1+2 2+3 3+5 5+8 8+13 13+21 21+34 ⒈ 基于递归的fibonacci算法实现，详见fibonacci1.c。long fib(long n) { long value = n; printf(\nCalcute fib(%ld)., n); if(n 1) value = fib(n-2)+fib(n-1); /* 按照公式进行递归调用 */ printf(\nValue of fib(%ld) is %ld., n, value); return value; } ⒉ 递归树（Recurren Tree） 由图6-1所示fib递归树可知，递归过程实际上是对一棵多叉树进行遍历操作，但这棵树并不是一棵各节点均不再变化的成熟型树，而应根据实际问题在树的相应节点处不断长出新的分叉，即多个不为空的子节点，这是一棵结构不确定的成长型树，有时还要不断修剪树枝以找出一条最佳路径。 递归调用的特点是，当遍历完某节点的所有同层兄弟之后，链表指针才能回溯至该节点的父节点，并在完成相应应用功能后，继续处理其他节点，即属于深度优先遍历递归树。对于二叉树来说，这种遍历方式称为后序遍历。 ⑵ 递归调用（Recurrent Calling）（Backtracking） ② 对于诸如走迷宫问题，从入口开始有多条不同分叉路径，只有一条能走到出口，那么在走到某一死胡同之后，就要回溯至上个路口，重新尝试下一条可能路径。对递归树而言，就是在某个叶节点无法长时新分叉时，应马上剪去这个分叉，并重新在父节点处长出新分叉，重新向下开始递归。具体内容可参见八皇后问题。 ⑷ 递归的终止 递归算法的关键是要了解问题何时已分解到最小项，即叶节点需要开始回溯操作；而何时仍需继续递归下去。在例6-1中，递归调用的终止条件为：n ≤ 1，并返回n值；当n 1时，则计算其前两项之和，如图6-1所示。 ⒊ 递归算法性能分析 ⑴ 时间分析 由于递归树中的每一个节点均表示一次调用，因此递归算法的执行时间与该递归树的节点总数成正比。在图6-1递归树中，共有9个节点，表示fib函数总共被调用9次，其中fib(4)一次，fib(3)一次，fib(2)二次，fib(1)三次，fib(0)二次。由于同一个fib(1)值会反复计算三次，而未能共享数据。同一个值的重复计算次数越多，有限计算机时间资源的浪费就越大，即算法的时间复杂度性能不佳。 ⑵ 空间分析 由于函数调用时需占用一定堆栈空间来保存现场数据，并在函数调用结束返回时释放，因此递归算法占用的堆栈空间与该递归树的深度成正比。递归层次越深，占用堆栈空间就越大，直接导致有限计算机空间资源的极大浪费，即算法的空间复杂度性能不佳。 表6-2 fibonacci数列与加法操作和递归调用次数的对应关系表 n fib(n+1)之值 加法次数 = fib(n+1)-1 函数调用次数 = 2 * fib(n+1) - 1 4 3 2 5 10 89 88 177 15 987 986 1973 20 10946 10945 21891 25 121393 121392 242785 30 1346269 1346268 2692537 由此可知，利用递归方法计算fib(n)的加法次数等于fib(n+1)-1。每个加法需要2次递归调用，再加上最开始一次调用，计算fib(n)时函数递归调用的次数等于2*fib(n+1)-1，如表6-2所示。 由表6-2可知，每当n增加5，加法次数和函数调用次数就会增加10倍，即fibonacci数列的递归算法时间和空间复杂度约为O(10n/5)，效率极差，无法与采用循环的非递归算法O(n)相提并论，如程序fibonac2所示。 ⒈ 基于非递归的fibonacci算法实现，详见程序fibonacci2.c。 ⒊ 非递归算法性能分析 ⑴ 时间分析 同样以n=4来调用非递归函数fib，则fib函数仅调用1次，即算法的非递归实现并无函数的反复递归调用过程；而fib(3)、fib(2)、fib(1)和fib(0)均只需计算一次，并未花费太多时间在数值的重复计算上，且数据还可以共用，因此采用非递归实现能够充分利用有限归算法中，同一内容有可能被重复计算，如fib(1)就曾多次调用，浪费时间 6.2 工程性实用递归算法解决