文档介绍：基本概念题:
6-1 什么叫递归?
6-2 适宜于用递归算法求解的问题的充分必要条件是什么?什么叫递归出口?
6-3 阶乘问题的循环结构算法和递归结构算法哪个的时间效率好,为什么?
6-4 非递归函数调用时系统要保存哪些信息?递归函数调用时系统要保存哪些信息?系统怎样保存递归函数调用时的信息?
6-5 什么叫运行时栈?什么叫运行时栈中的活动记录?
6-6 叙述递归算法的执行过程。
复杂概念题:
6-7 推导求解n阶汉诺塔问题要执行的移动操作(即算法中printf()函数的调用)次数。
6-8 我们讨论过的折半查找函数设计如下:
int BSearch(elemtype a[], elemtype x, int low, int high)
{
int mid;
if(low>high) return -1;
mid =(low+high)/2;
if(x == a[mid]) return mid;
if(x < a[mid]) return (BSearch(a,x,low,mid-1));
else return (BSearch(a,x,mid+1,high));
}
讨论如果把上述折半查找函数中最后两语句改为如下形式能否实现算法的设计要求,为什么?
if(x < a[mid]) BSearch(a,x,low,mid-1);
else BSearch(a,x,mid+1,high);
算法设计题:
6-9 要求:
(1)写出求1,2,3,......,n的n个数累加的递推定义式;
(2)编写求1,2,3,......,n的n个数累加的递归算法,假设n个数存放在数组a中。
6-10 要求:
(1)写出求1,2,3,......,n的n个数连乘的递推定义式;
(2)编写求1,2,3,......,n的n个数连乘的递归算法,假设n个数存放在数组a中。
6-11 设a是有n个整数类型数据元素的数组,试编写求a中最大值的递归算法。
6-12 设计输出如下形式数值的算法。
1
2 2
3 3 3
......
n n n ... n
要求:
(1)把算法设计成递归结构的算法;
(2)画出上述递归算法的调用执行过程;
(3)把算法设计成循环结构。
*6-13 背包问题。设有一个背包可以放入物品的重量为s,现有n件物品,重量分别为w[0],w[1],...,[n-1]。问题是能否从这n件物品中选择若干件放入此背包中使得放入的重量之和正好等于s。如果存在一种符合上述要求的选择,则称此背包问题有解;否则称此背包问题无解。试用分而治之的算法设计方法设计求解背包问题的函数。
提示:此背包问题的递推定义如下(其中True表示有解,False表示无解):
上机实****题:
6-14 折半查找问题。,折半查找问题的递归算法见例6-2。要求:
(1