文档介绍：第5章递归算法 递归的概念 递归算法的执行过程 递归算法的设计方法 设计举例 递归的概念存在算法调用自己的情况: 若一个算法直接的或间接的调用自己本身,则称这个算法是递归算法。阶乘函数的常见定义是: 1 问题定义是递推的也可定义为: 写成函数形式,则为: 这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数,称公式( 6 – 3)是阶乘函数的递推定义式。 2. 问题的解法存在自调用例如:折半查找算法查找 17 递归算法的执行过程例1:阶乘的递归算法 public static long fact(int n){ long y; if (n < 0){ throw new Exception(" 参数错! "); } if (n == 0) return 1; else { y = fact(n-1); return n * y; } } 设计一个计算 3!的主函数如下,用来说明递归算法的执行过程: static void Main(string[] args){ long fn; try { fn = fact(3); ("fn = " + fn); } catch (Exception e) { (); } } 主函数用实参 n = 3 调用了递归算法 fact(3) ,而fact(3) 要通过调用 fact(2) 、fact(2) 要通过调用 fact(1) 、fact(1) 要通过调用 fact(0) 来得出计算结果。 fact(3) 的递归调用过程如下图所示,其中, 实线箭头表示函数调用,虚线箭头表示函数返回,此函数在返回时函数名将带回返回值。 main . . . fn= fact(3) return(3 *y) 11 26 fact(3) . . .y= fact(2) return(2 *y) . . . fact(2) y= fact(1) . . .y= fact(0) fact(1) fact(0) return 1 return(1 *y) 递归算法的设计方法递归算法既是一种有效的算法设计方法,也是一种有效的分析问题的方法。递归算法求解问题的基本思想是:对于一个较为复杂的问题,把原问题分解成若干个相对简单且类同的子问题,这样较为复杂的原问题就变成了相对简单的子问题;而简单到一定程度的子问题可以直接求解;这样,原问题就可递推得到解。适宜于用递归算法求解的问题的充分必要条件是: (1)问题具有某种可借用的类同自身的子问题描述的性质(2)某一有限步的子问题(也称作本原问题)有直接的解存在。当一个问题存在上述两个基本要素时,设计该问题的递归算法的方法是: (1)把对原问题的求解表示成对子问题求解的形式。(2)设计递归出口。例3 设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的描述是:设有 3 根标号为 A,B,C 的柱子,在 A 柱上放着 n 个盘子, 每一个都比下面的略小一点,要求把 A 柱上的盘子全部移到 C柱上,移动的规则是:( 1 )一次只能移动一个盘子;( 2 )移动过程中大盘子不能放在小盘子上面;( 3 )在移动过程中盘子可以放在 A,B,C的任意一个柱子上。 问题分析:可以用递归方法求解 n个盘子的汉诺塔问题。基本思想:1个盘子的汉诺塔问题可直接移动。 n个盘子的汉诺塔问题可递归表示为,首先把上边的 n-1 个盘子从 A柱移到 B柱,然后把最下边的一个盘子从 A柱移到 C柱,最后把移到 B柱的 n-1 个盘子再移到 C柱。 4个盘子汉诺塔问题的递归求解示意图如图所示。 2 134 ABC