递归求半函数仅支持偶数计算，求适配奇数的改进方案

AI 小北

2026-8-18

问题分析与改进方案

你的代码在处理奇数时陷入无限递归，原因是当输入为奇数x=2k+1时，初始y=x=2k+1，每次递归y减2，最终会变为1，再执行pred(pred(y))得到-1，此时is_zero(y)永远为假，递归无法终止。

改进思路

要解决这个问题，需要在递归中新增对y=1的判断：

当y=0时，返回当前x（对应偶数的情况，此时x恰好是原数的一半）；
当y=1时，返回pred(x)（对应奇数的情况，此时x是k+1，减1后得到k，即原数的向下取整结果）；
当y>1时，继续递归调用half(pred(x), pred(pred(y)))。

判断y=1可以通过is_zero(pred(y))实现，因为pred(1)=0，此时is_zero(pred(y))返回真。

修改后的完整代码

#include <stdio.h>

int succ(int x) {
  return x+1;
}

int pred(int x) {
  return x-1;
}

int is_zero(int x) {
  return x == 0;
}

int is_pos(int x) {
  return x >= 0;
}

int half(int x, int y) {
    return is_zero(y) ? x : (is_zero(pred(y)) ? pred(x) : half(pred(x), pred(pred(y))));
}

int half1(int x) {
    return half(x,x);
}

int main() {
    int x;
    scanf("%d", &x);
    int z = half1(x);
    printf("%d\n", z);
    return 0;
}