参考答案及解析

题目1：汉诺塔问题

判断题：1.√ 2.√ 3.√
选择题：4.A 5.C
解析：移动次数公式为2^n-1，4个盘子需要15次。aux是辅助柱子。

题目2：斐波那契数列

判断题：1.√ 2.√ 3.√
选择题：4.C 5.A
解析：fib(2)在fib(6)的计算中被调用5次。修改后逻辑相同但更清晰。

题目3：阶乘计算

判断题：1.√ 2.√ 3.×
选择题：4.A 5.B
解析：递归调用顺序是从n递减到0。n为负数会无限递归。

题目4：字符串反转

判断题：1.√ 2.√ 3.√
选择题：4.A 5.A
解析：递归过程是"abc"→"bc"→"c"。修改后从后往前反转，功能相同。

题目5：数组求和

判断题：1.√ 2.√ 3.√
选择题：4.C 5.A
解析：返回值顺序是5+(4+(3+(2+(1+0))))。修改后使用指针偏移，功能相同。

题目6：最大公约数

判断题：1.√ 2.√ 3.√
选择题：4.A 5.D
解析：辗转相除过程如A所示。增加递归基a==b可以减少递归深度。

题目7：快速幂运算

判断题：1.√ 2.√ 3.√
选择题：4.C 5.A
解析：递归调用序列如C所示。n==0时已经返回1，不需要额外判断。

题目8：集合子集

判断题：1.√ 2.√ 3.√
选择题：4.A 5.A
解析：第一层生成空集和以每个元素开头的子集。移动后缺少空集。

题目9：全排列

判断题：1.√ 2.√ 3.√
选择题：4.C 5.A
解析：start=0时，i=0,1,2分别对应1,1,2。删除跳过重复的检查会产生重复排列。

题目10：数独求解

判断题：1.√ 2.√ 3.√
选择题：4.C 5.C
解析：计算整个棋盘的行索引。删除回溯操作会导致棋盘状态错误。

题目11：表达式求值

判断题：1.√ 2.√ 3.√
选择题：4.A 5.A
解析：遇到'*'时sign还是'+'。修改后会包含括号，导致无限递归。

题目12：N皇后问题

判断题：1.√ 2.√ 3.√
选择题：4.B 5.A
解析：第32行移除皇后实现回溯。修改后功能相同但每次都会检查合法性，效率低。