《大学计算机课件》递归.ppt

例：求n!的算法或程序 ——递归 define fact n cond n 1 1 n 1 * n fact n-1 程序的递归构造：自身调用自身，高阶调用递阶。 如何递归构造程序? 如何递归构造程序? 程序的递归构造：自身调用自身，高阶调用递阶。 程序的迭代构造---递推法 如何迭代构造程序? *… * * * * 1 1 2 3 4 …n Product ? Product * Counter Counter ? Counter + 1 define fact n fact-iter 1 1 n define fact-iter product counter max-count cond counter max-count product counter max-count fact-iter * counter product + counter 1 max-count fact 6 ? fact-iter 1 1 6 ? fact-iter * 1 1 + 1 1 6 ? fact-iter 1 2 6 ? fact-iter * 1 2 + 2 1 6 ?? fact-iter 2 3 6 ? fact-iter * 2 3 + 3 1 6 ?? fact-iter 6 4 6 ? fact-iter * 6 4 + 4 1 6 ? fact-iter 24 5 6 ? fact-iter * 24 5 + 5 1 6 ? fact-iter 120 6 6 ? fact-iter * 120 6 + 6 1 6 ? fact-iter 720 7 6 ? 720 define fact n fact-iter 1 1 n define fact-iter product counter max-count cond counter max-count product counter max-count fact-iter * counter product + counter 1 max-count 程序的迭代构造---递推法 如何迭代构造程序? 在700多年前，意大利有一位著名数学家斐波那契在他的《算盘全集》一书中提出了这样一道有趣的兔子繁殖问题。 ?如果有一对小兔，每一个月都生下一对小兔，而所生下的每一对小兔在出生后的第三个月也都生下一对小兔。那么，由一对兔子开始，满一年时一共可以繁殖成多少对兔子？ 用列举的方法可以很快找出本题的答案： 第一个月，这对兔子生了一对小兔，于是这个月共有2对（1+1 2）兔子。 第二个月，第一对兔子又生了一对兔子。因此共有3对（1+2 3）兔子。 第三个月，第一对兔子又生了一对小兔而在第一个月出生的小兔也生下了一对小兔。所以，这个月共有5对（2+3 5）兔子。 第四个月，第一对兔子以及第一、二两个月生下的兔子也都各生下了一对小兔。因此，这个月连原先的5对兔子共有8对（3+5 8）兔子。 列表如下： 就是说，由一对兔子开始，满一年时一共可繁殖成377对小兔。 Fibonacci数列 特别值得指出的是，数学家斐波那契没有满足于这个问题有了答案。他进一步对各个月的兔子对数进行了仔细观察，从中发现了一个十分有趣的规律，就是后面一个月份的兔子总对数，恰好等于前面两个月份兔子总对数的和，如果再把原来兔子的对数重复写一次，于是就得到了下面这样的一串数：???1，1，2，3，5，8，13，21，34，55，89，144，233，377……后来人们为了纪念这位数学家，就把上面这样的一串数称作斐波那契数列，把这个数列中的每一项数称作斐波那契数。斐波那契数具有许多重要的数学知识，用途广泛。 斐波纳契数列（ Fibonacci ），又称黄金分割数列 在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。 Fibonacci数列 例： Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为： F 0 1; F 1 1; F 2 F 1 +F 0 2; F 3 F 2 +F 1 3; F 4 F 3 +F 2 3+2 5;… … 递归定义 递推计算/迭代