关于递推算法的描述,正确的是( )。
A:递推表现为函数自己调用自己
B:递推从已知初值出发,利用递推关系逐步推出后续结果
C:递推只能用于指数复杂度问题
D:递推一定需要回溯
正确答案:B
答案解析
递推是一种通过已知初始条件,依据明确的递推关系,逐次计算后续各项值的计算过程。每一步的结果由前一步或前几步的结果直接推导得出,不涉及函数自我调用机制。该过程适用于多种复杂度的问题,可在常数、线性或更高阶的时间复杂度下实现,具体取决于递推关系的结构和计算方式。递推过程为单向推进,不需要回溯已计算结果或尝试其他路径,也不要求问题具备回溯特性。其核心在于构建正确的递推公式并正确初始化起始值。
试卷来源:202603 CCF-GESP编程能力等级认证C++四级真题