这道题的关键在于理解递归转非递归与 “是否用栈” 的本质逻辑,和 “局部变量” 无关,核心看递归的调用上下文是否需要保存。
一、递归的本质:依赖 “调用栈”
递归函数执行时,系统会用调用栈保存:
- 每层递归的参数、返回地址、局部变量(不管是不是局部变量,只要递归嵌套,就需要保存上下文)。
比如经典的递归求和:
int sum(int n) {if (n == 1) return 1;// 递归调用,sum(n-1) 依赖上一层的 nreturn n + sum(n-1);
}
这里 sum(3)
调用 sum(2)
,sum(2)
调用 sum(1)
,每层的 n
(局部变量)会存在栈里。
二、“是否用栈” 的关键:是否需要模拟 “调用栈”
递归转非递归时,不管有没有局部变量,只要递归有多层嵌套(需要保存上下文),就可能需要用栈手动模拟调用栈。
反例 1(无局部变量,但需要栈):
// 递归打印 1~n,无局部变量(除了参数)
void print(int n) {if (n == 0) return;print(n-1);printf("%d ", n);
}
转非递归时,仍需用栈保存 n
的值(模拟调用栈的嵌套),否则无法按顺序打印 1 2 3
。
反例 2(有局部变量,但无需栈):
// 尾递归:递归调用在最后,无额外计算
int tail_sum(int n, int res) {if (n == 0) return res;// 递归调用后直接返回,无需保存复杂上下文return tail_sum(n-1, res + n);
}
这种尾递归可直接转迭代(用变量代替栈):
int iter_sum(int n) {int res = 0;for (int i = 1; i <= n; i++) {res += i; // 无需栈,迭代累加}return res;
}
此时,即使有局部变量(res
是函数参数,类似局部变量),也不用栈。
三、题目逻辑错误点
题目说 “只有使用局部变量的递归,转非递归才必须用栈”,但实际:
- 不用局部变量的递归(如
print
函数),转非递归可能也需要栈; - 用局部变量的递归(如尾递归
tail_sum
),转非递归可能不需要栈。
“是否用栈” 和递归的嵌套结构(是否需要保存上下文) 有关,和 “是否用局部变量” 无关。因此题目说法 错误