AP 计算机科学 A - 单元 10：递归

递归 (Recursion)

点击看答案

一个方法直接或间接调用自身来解决问题的编程技巧。

基本情况 (Base Case)

点击看答案

递归算法中的终止条件。当满足此条件时，方法不再调用自身，并返回一个值。

递归情况 (Recursive Case / Step)

点击看答案

算法中方法再次调用自身的部分，通常处理一个更小或更简单的子问题。

无限递归 (Infinite Recursion)

点击看答案

递归调用链没有正确的终止条件，导致方法无休止地调用自身。

栈溢出错误 (StackOverflowError)

点击看答案

当递归深度太大，耗尽了调用栈的内存空间时抛出的运行时错误。

调用栈 (Call Stack)

点击看答案

一种用于存储有关程序中活动子程序（方法）信息的数据结构。每次递归调用都会在栈顶添加一个新帧。

递归追踪 (Recursive Tracing)

点击看答案

手动跟踪递归方法的执行过程，记录每次调用的参数值和最终的返回值。

阶乘 (Factorial) 的递归定义

点击看答案

n! = n * (n-1)! 基本情况：0! = 1

斐波那契数列 (Fibonacci) 的递归定义

点击看答案

fib(n) = fib(n-1) + fib(n-2) 基本情况：fib(0) = 0, fib(1) = 1

递归与迭代 (Recursion vs. Iteration)

点击看答案

递归使用方法调用；迭代使用循环（for, while）。任何递归算法都可以用迭代重写，反之亦然。

辅助方法 (Helper Method)

点击看答案

一个通常为 private 的方法，被另一个 public 方法调用以启动或管理递归过程，常用于传递额外参数。

分治算法 (Divide and Conquer)

点击看答案

一种基于递归的算法思想：将问题分解为相似的子问题，递归解决子问题，然后合并结果。

归并排序 (Merge Sort)

点击看答案

一种典型的分治排序算法。递归地将数组分成两半并排序，然后将已排序的两半合并。

二分查找 (Binary Search) 的递归实现

点击看答案

在有序数组中，比较中间元素与目标值。根据比较结果，对数组的左半部分或右半部分进行递归查找。

递归的缺点是什么？

点击看答案

可能效率较低（由于重复计算），并有导致栈溢出错误的风险。

递归的优点是什么？

点击看答案

对于某些问题（如树的遍历），代码更简洁、更易于理解和实现。