除了 is_zero、succ 和 pred 之外，不使用任何辅助函数，是否可以在单次递归过程中将分数化简为最低形式？

Question

除了 is_zero、succ 和 pred 之外，是否可以在单次递归传递中将分数化简为最低形式？例如，如果我们想以这种方式实现 gcd，我们可以这样写：

// gcd(a, b, c) returns the greatest common divisor of `a+c` and `b+c`
function gcd(a, b, c)
  if is_zero(a):
    if is_zero(b):
      c
    else:
      gcd(c, b, 0)
  else:
    if is_zero(b):
      gcd(a, c, 0)
    else:
      gcd(pred(a), pred(b), succ(c))

注意这个函数是如何直接递归的，除了is_zero、succ和pred之外没有使用任何辅助函数。不过，它确实需要一个额外的参数来存储结果。它也是尾递归的，但这不是必需的。我的问题是：是否可以这样做，但是 reduce_fraction?

// reduce_fraction(a, b, ...) returns a pair 
// with the `a/b` fraction in the lowest form
function reduce_fraction(a, b, ...):
  ...

请注意，不允许使用 GCD 实现 reduce_fraction：

function reduce_fraction(a,b):
  return (a / gcd(a,b), b / gcd(a,b))

因为reduce_fraction会调用2个辅助函数（gcd和/），这是定义允许的不。它必须是仅使用 is_zero、succ 和 pred.

的直接递归

我正在专门寻找一种解决方案来减少 space 使用（辅助参数的数量）和使用的时间（总递归步骤）。

Answer 1

我们可以编写一个简单的函数来模仿您拥有的相同 gcd 结构，但是 returns 简化形式的分数：

-- redBad n d delta reduces the fraction (n+delta)/(d+delta)
redBad 0 0 delta = (1, 1)
redBad 0 d delta = case redBad delta d 0 of
    (n', d') -> (n', n'+d')
redBad n 0 delta = case redBad n delta 0 of
    (n', d') -> (n'+d', d')
redBad n d delta = redBad (n-1) (d-1) (delta+1)

“啊！”，你大叫，“但是那使用了一个名为 + 的辅助函数！”！好的没问题;我们将使用评论中描述的“模式”技巧。模式0是gcd计算；方式1为加法运算

-- redGood n d delta 0 reduces the fraction (n+delta)/(d+delta)
-- redGood n d delta 1 produces the fraction (n+delta)/d
redGood 0 0 delta 0 = (1, 1)
redGood 0 d delta 0 = case redGood delta d 0 0 of
    (n', d') -> case redGood d' n' n' 1 of
        (d'', n'') -> (n'', d'')
redGood n 0 delta 0 = case redGood n delta 0 0 of
    (n', d') -> redGood n' d' d' 1
redGood n d delta 0 = redGood (n-1) (d-1) (delta+1) 0
redGood n d 0 mode = (n, d)
redGood n d delta mode = redGood (n+1) d (delta-1) mode

除了 is_zero、succ 和 pred 之外，不使用任何辅助函数，是否可以在单次递归过程中将分数化简为最低形式？

Is it possible to reduce a fraction to the lowest form in a single recursive pass, using no auxiliary functions other than is_zero, succ and pred?

algorithm

haskell

recursion

functional-programming

greatest-common-divisor