仅使用is_zero、succ、pred单递归实现分数最简约分是否可行？

可以实现，我们可以将求最大公约数、分子除法、分母除法三个过程合并到同一递归流程中，仅使用指定的三个辅助函数完成，不需要额外调用gcd或除法函数。

实现思路 #

我们通过状态标记将递归划分为三个连续阶段，全程仅使用is_zero判断零值、succ做加1、pred做减1运算：

1. 第一阶段复用题目给出的减法版欧几里得逻辑，递归计算输入分子分母的最大公约数
2. 第二阶段用逐次减除数计数的方式模拟除法，计算分子除以最大公约数的商
3. 第三阶段用同样的模拟除法逻辑计算分母除以最大公约数的商，最终返回约分后的分数对

参考实现 #

// 初始调用方式：reduce_fraction(输入分子, 输入分母, 输入分子, 输入分母, 0, 0, 0, 0)
function reduce_fraction(orig_a, orig_b, x, y, g, quo, rem, state) {
  // 状态0：计算gcd(x,y)，g为公共约数中间值
  if (is_zero(state)) {
    if (is_zero(x)) {
      if (is_zero(y)) {
        // 已算出最大公约数为g，进入分子除法阶段，rem初始化为g，x重置为原分子
        return reduce_fraction(orig_a, orig_b, orig_a, orig_b, g, 0, g, 1);
      }
      return reduce_fraction(orig_a, orig_b, g, y, 0, quo, rem, 0);
    }
    if (is_zero(y)) {
      return reduce_fraction(orig_a, orig_b, x, g, 0, quo, rem, 0);
    }
    return reduce_fraction(orig_a, orig_b, pred(x), pred(y), succ(g), quo, rem, 0);
  }
  // 状态1：计算 orig_a / g 的商，存在quo中
  else if (is_zero(pred(state))) {
    if (is_zero(x)) {
      // 分子除法完成，商为succ(quo)，存入orig_a，进入分母除法阶段
      return reduce_fraction(succ(quo), orig_b, orig_a, orig_b, g, 0, g, 2);
    }
    if (is_zero(rem)) {
      // 凑完一个除数单位，商加1，余数重置为g
      return reduce_fraction(orig_a, orig_b, x, y, g, succ(quo), g, 1);
    }
    // 余数、剩余分子各减1
    return reduce_fraction(orig_a, orig_b, pred(x), y, g, quo, pred(rem), 1);
  }
  // 状态2：计算 orig_b / g 的商，存在quo中
  else {
    if (is_zero(y)) {
      // 分母除法完成，返回结果对
      return [orig_a, succ(quo)];
    }
    if (is_zero(rem)) {
      // 凑完一个除数单位，商加1，余数重置为g
      return reduce_fraction(orig_a, orig_b, x, y, g, succ(quo), g, 2);
    }
    // 余数、剩余分母各减1
    return reduce_fraction(orig_a, orig_b, x, pred(y), g, quo, pred(rem), 2);
  }
}

复杂度说明 #

总递归步数为O(a + b)，和单独计算gcd再做两次除法的时间开销一致，且全程为尾递归实现，空间开销仅为固定的8个参数，不会随输入大小增长。如果需要进一步减少参数数量，可以通过参数复用将辅助参数压缩到5个，逻辑与上述实现一致。

内容的提问来源于stack exchange，提问作者MaiaVictor