中小学教育资源及组卷应用平台 《递归》作业 一、选择题 1. 以下关于递归的描述中，正确的是： A. 递归函数必须有一个基本情况（或称为终止条件） B. 递归函数必须无限进行下去 C. 递归函数不能调用自身 D. 递归函数的效率总是比迭代高 答案：A 解析：递归函数必须有一个基本情况，即不再调用自身的条件，否则会导致无限递归，最终栈溢出。选项B错误，因为递归必须有终止条件。选项C错误，因为递归函数的定义就是函数直接或间接地调用自身。选项D错误，递归和迭代各有优劣，具体效率取决于问题的性质和实现方式。 2. 在计算阶乘的递归函数中，n! = n (n-1)! 是一个： A. 基本情况 B. 递归情况 C. 边界条件 D. 初始条件 答案：B 解析：递归情况是指函数通过自身调用来解决问题的一部分，而基本情况是不需要进一步调用自身的条件。在这个阶乘的例子中，n! = n (n-1)! 是通过递归调用来计算的，因此是递归情况。 3. 斐波那契数列的递归定义是 F(n) = F(n-1) + F(n-2)，其中F(0) = 0, F(1) = 1。这里的F(0)和F(1)是： A. 递归调用 B. 基本情况 C. 边界条件 D. 初始条件 答案：B 解析：在斐波那契数列的递归定义中，F(0) = 0 和 F(1) = 1 是基本情况，因为它们不再需要进一步的递归调用。 4. 以下哪个不是递归算法的特点？ A. 自顶向下解决问题 B. 分而治之 C. 需要大量的内存空间 D. 适用于所有类型的问题 答案：D 解析：递归算法通常适用于可以分解为更小子问题的问题，但并不是所有类型的问题都适合用递归来解决。选项A、B、C都是递归算法的典型特点。 5. 在二分查找算法中，如果搜索范围为空，则应该： A. 继续搜索 B. 返回中间元素 C. 返回-1（或任何表示未找到的值） D. 抛出异常 答案：C 解析：在二分查找算法中，如果搜索范围为空，说明目标值不存在于数组中，此时应返回一个特殊值（如-1）表示未找到。 6. 汉诺塔问题的递归解法中，移动n个盘子从源柱子到目标柱子需要的最少步数是： A. 2^n - 1 B. n^2 C. n! D. n(n-1)/2 答案：A 解析：根据汉诺塔问题的递归定义，移动n个盘子需要的步数是移动n-1个盘子的步数加上移动最底下的盘子的步数再加上移动剩下的n-1个盘子的步数。这个递推关系可以通过数学归纳法证明其解为2^n - 1。 二、填空题 7. 在递归函数中，基本情况也被称为_____条件。 答案：终止 解析：基本情况也被称为终止条件，因为它标志着递归调用的结束。 8. 递归函数的两个主要组成部分是_____情况和基本情况。 答案：递归 解析：递归函数由递归情况和基本情况组成，递归情况用于分解问题，基本情况用于结束递归。 9. 在计算斐波那契数列的第n项时，如果n小于等于1，则直接返回n，这是递归函数的_____条件。 答案：基本情况（或终止条件） 解析：在斐波那契数列的递归定义中，当n小于等于1时，函数直接返回n，这是基本情况。 10. 递归函数在执行过程中会消耗一定的_____空间。 答案：栈 解析：递归函数在执行过程中会在调用栈上保存每一层调用的信息，因此会消耗一定的栈空间。 11. 在二分查找算法中，每次将搜索范围缩小为原来的一半，这是利用了递归的_____思想。 答案：分而治之 解析：二分查找算法通过每次将搜索范围缩小一半来查找目标值，这正是“分而治之”思想的体现。 122. 在快速排序算法中，通过一次_____操作将数组分为两部分，然后对每部分分别进行排序。 答案：分区（或划分） 解析：快速排序算法的核心在于分区操作，通过选择一个基准值将数组分为两部分，使得左边的元素都小于基准值，右边的元素都大于基准值。 13. 在汉诺塔问题中，将n-1个盘子从辅助柱子移动到目标柱子所需的步数是_____步。 答案：2^(n-1) - 1 解析：根据汉诺塔问题的递归定义，移动n-1个盘子所需的步数是2^(n-1) - 1。 14. ... ...
~~ 您好，已阅读到文档的结尾了 ~~
