1、递归的概念 2、递归函数的设计 3、递归过程与递归工作栈 4、例 5、递归过程的非递归化 八、递归 1、递归的概念 2、递归函数的设计 3、递归过程与递归工作栈 4、例 5、递归过程的非递归化

1、递归的概念 在数学上，一个正整数的阶乘通常用以下公式进行定义： n! = n×(n－1)×· · · ×1, 这种技法作为阶乘函数不是很严密。 正规的阶乘定义应为 1 if n = 0 n! = n ×(n－1)! If n ＞0 4! = 4 ×3! = 4 ×(3 ×2!) = 4 ×(3 ×(2 ×1!)) = 4 ×(3 ×(2×(1×0!))) = 4 ×(3 ×(2×(1×1))) = 4 ×(3 ×(2×1)) = 4 ×(3 ×2) 利用前一次由较小 = 4 ×6 值计算出的结果。 = 24

long Fractorial(long n) 递归的定义 若一个对象部分地包含它自己，或用它自己给自己下定义，称这 个对象是递归的；若一个过程直接地或间接地调用自己，则称这 个过程是递归的过程。 long Fractorial(long n) { if (n = = 0) return 1; else return n﹡fractorial(n-1); } 用递归的情况 ⑴定义是递归的； ⑵数据结构是递归的； 如：①一个结点，其指针域为NULL，是一个单链表； ②一个结点，其指针域指向一个单链表，仍是一个单链表。 ⑶问题的解法是递归的。

2、递归函数的设计 每一个递归过程由两部分组成： ⑴一个最小的基础情况，它不需用递归来处理； ⑵一个通用的方法(又称递归步骤)，它根据先前某次值求当前值， 这一步骤应该导致过程的终止。 使用 if– else 语句，if 语句块判断递归结束的条件，else语句块处 理递归的情况。 幂函数计算 xn = 1 n = 0 x﹡x（n-1） n ＞0 float Fractorial（float x，int n） { if （n = = 0） return 1 else return x ﹡Fractorial（x，n-1） }

递归函数的设计 Hanoi塔问题 结束条件：只有一块盘子，将这一盘子直接送到柱C 递归过程：用C柱过渡，将A柱上的盘子送到柱B 直接把A柱上最后一个盘子移到C 将A柱为过渡， 将B柱上(n-1)个盘子移到C void Honoi (int t, string A, string B, string C) { if (n = = 1) cout<<“move”<<A<<“to”<<C<<endl else hanoi( n – 1, A, C, B); cout<<“move”<<A<<“to”<<C<<endl; hanoi( n – 1, B, A, C); }

3、递归过程与递归工作栈 下图反映了阶乘函数计算函数调用过程 4! = 4 ×3! = 4 ×(3 ×2!) = 4 ×(3 ×(2 ×1!)) = 4 ×(3 ×(2×(1×0!))) = 4 ×(3 ×(2×(1×1))) = 4 ×(3 ×(2×1)) = 4 ×(3 ×2) = 4 ×6 = 24 参数 计算 返回 0 0! = 1 1 参数 计算 返回 1 1×fractorial(0) 1 参数 计算 返回 2 2×fractorial(1) 2 参数 计算 返回 3 3×fractorial(2) 6 参数 计算 返回 4 4×fractorial(3) 24 主程序 main

4、例 ⑴折半查找 终止条件：查找成功或子表成为空表； 递归步骤：按中间值与关键字大小确定在下子表或上子表中继续 查找。 template<class T> int BinSearch(T A[ ], int low, int high, T key) { int midl; T midvalue; if (low>high) return (-1); else mid = (low+high)/2; midvalue = A[mid];

例(折半查找) // 终止条件：找到key if (key = = midvalue) return mid; // 若key<midvalue, 则查下子表；否则，查上子表 else if (key < midvalue) // return BinSearch（A, low, mid – 1, key); else return BinSearch ( A, mid+1, high, key); }

Fibonacci数列 Fibonacci 数列的定义 1 若n = 1或2 F(n) = F(n –1)+F(n – 2) 若n>2 终止条件：F(1) = F(2)=1 递归步骤： F(n) = F(n –1)+F(n – 2) long Fib(int n) { if (n = =1‖n = =2) return 1 else return Fib(n-1)+Fib(n – 2) }

5、递归过程的非递归化 用单纯的循环方式非递归化 阶乘的非递归算法 long Factorial (long n) { int prod = 1, i; if (n > 0) for (i = 1; i< = n; i+ +) prod*=i; return prod; }

递归过程的非递归化 用迭代法非递归化 Fib(6) Fib(5) Fib(4) Fib(4) Fib(3) Fib(3) Fib(2)

迭代法计算Fibonacci数列 Fibonacci数列的迭代计算 long FibIter(int n) { long twoback =1, oneback = 1, current; int i; // FibIter(1) = FibIter(2) = 1 if (n = =1‖n = =2) return 1; // current = twoback+oneback, n>=3 else for (i =3; i <=n; i + +) current = twoback + oneback; twoback = oneback; oneback = current; }

作 业 书面作业 10.6 10.11 上机题 10.1 10.2 10.9