fact(3) fact(2) fact(1) 真 假 真 假 真 假 调用 调用 fact(2) fact(1) fact(1) 计算 计算 3*fact(2) 2 fact(1) 返回 返回
11 3＝＝1 fact(3) 真 假 调 用 fact(2) 计 算 3*fact(2) fact(2) fact(1) 2＝ ＝1 真 假 调 用 fact(1) 计 算 2*fact(1) 1＝ ＝1 真 假 fact(1) ＝1 返 回 返 回
为了形象地描述递归过程,将上图改画成下图 fact(3) 真 3==1 假 调用fact(2) 2==1 真 假 调用fact(1) 假 返回 fact(2)=2*fact(1)返回 fact(3)=3*fact(2)返回 12
12 为了形象地描述递归过程，将上图改画成下图 fact(3) 真 假 3==1 调用 fact(2) 真 假 真 假 2==1 1==1 fact(2)=2*fact(1) 返回 fact(3)=3*fact(2) 返回 调用 fact(1) fact(1) =1 返回
在这个图中“内层”与“外层”有着相同的结构。它 们之间“你中有我,我中有你”,呈现相互依存的 关系。 为了进一步讲清递归的概念,将递归与递推做一比较 仍以求阶乘为例。 递推是从已知的初始条件出发,逐次去求所需要的阶 乘值。 如求3! 初始条件fact(1)=1 fact(2)=2*fact(1)=2 fact(3)=3 fact(2)=6
13 在这个图中“内层”与“外层”有着相同的结构。它 们之间“你中有我，我中有你”，呈现相互依存的 关系。 为了进一步讲清递归的概念，将递归与递推做一比较。 仍以求阶乘为例。 递推是从已知的初始条件出发，逐次去求所需要的阶 乘值。 如求3！ 初始条件 fact(1) = 1 fact(2) = 2*fact(1) = 2 fact(3) = 3*fact(2) = 6
这相当于从菜心“推到”外层。而递归算法的出发点 不放在初始条件上,而放在求解的目标上,从所求 的未知项出发逐次调用本身的求解过程,直到递归 的边界(即初始条件)。就本例而言,读者会认为 递归算法可能是多余的,费力而不讨好。但许多实 际问题不可能或不容易找到显而易见的递推关系, 这时递归算法就表现出了明显的优越性。下面我们 将会看到,递归算法比较符合人的思维方式,逻辑 性强,可将问题描述得简单扼要,具有良好的可读 性,易于理解,许多看来相当复杂,或难以下手的 问题,如果能够使用递归算法就会使问题变得易于 处理。下面举一个尽人皆知的例子哈诺( Hanoi)塔 问题
14 这相当于从菜心“推到”外层。而递归算法的出发点 不放在初始条件上，而放在求解的目标上，从所求 的未知项出发逐次调用本身的求解过程，直到递归 的边界（即初始条件）。就本例而言，读者会认为 递归算法可能是多余的，费力而不讨好。但许多实 际问题不可能或不容易找到显而易见的递推关系， 这时递归算法就表现出了明显的优越性。下面我们 将会看到，递归算法比较符合人的思维方式，逻辑 性强，可将问题描述得简单扼要，具有良好的可读 性，易于理解，许多看来相当复杂，或难以下手的 问题，如果能够使用递归算法就会使问题变得易于 处理。下面举一个尽人皆知的例子哈诺（Hanoi）塔 问题