Блог

Можно ли уменьшить дробь до наименьшей формы за один рекурсивный проход, не используя никакой вспомогательной функции, кроме 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 .

Я специально ищу решение, которое сокращает используемое пространство (количество вспомогательных аргументов) и используемое время (общее количество рекурсивных шагов).

Мы можем написать простую функцию, которая имитирует ту же gcd структуру, что и у вас, но которая возвращает дробь в уменьшенной форме:

 -- 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