Можно ли записать функцию свертки в хвостовой рекурсивной форме?

У меня есть функция, которую я хочу написать в хвостовой рекурсивной форме. Функция вычисляет количество способов получить сумму k, бросая s односторонний кубик n раз. Я видел математическое решение этой функции в этом ответе. Это выглядит следующим образом:

введите описание изображения здесь

Моя справочная рекурсивная реализация в R:

sum_ways <- function(n_times, k_sum, s_side) {
  if (k_sum < n_times || k_sum > n_times * s_side) {
    return(0)
  } else if (n_times == 1) {
    return(1)
  } else {
    sigma_values <- sapply(
      1:s_side, 
      function(j) sum_ways(n_times - 1, k_sum - j, s_side)
    )
    return(sum(sigma_values))
  }
}

Я попытался переписать функцию в стиле продолжения передачи, как я узнал из этого ответа, но я не успешный. Есть ли способ записать эту функцию в хвостовой рекурсивной форме?

ИЗМЕНИТЬ

Я знаю, что R не оптимизирует хвостовую рекурсию. Мой вопрос не относится к R, решение на любом другом языке также приветствуется. Даже если это язык, который не оптимизирован для хвостовой рекурсии.


recursion functional-programming dynamic-programming continuation-passing tail-recursion
person refik    schedule 11.01.2017    source источник
comment
Посмотрите на ?Recall.   -  person IRTFM    schedule 11.01.2017
comment
@ 42- Я рад узнать об этом, спасибо, но я не видел, как это могло бы помочь, так как у меня нет сложностей, связанных с изменением имени функции   -  person refik    schedule 11.01.2017
comment
В этом случае рекурсия не будет очень эффективной реализацией, используйте динамическое программирование / мемоизацию для сохранения уже вычисленных значений f и их повторного использования.   -  person Sandipan Dey    schedule 11.01.2017
comment
@sandipan Когда мне понадобилась эта функция, я написал свою эталонную реализацию и использовал ее с мемоизацией. Все работало нормально. На данный момент мне не нужна улучшенная реализация, я просто хочу знать, применима ли хвостовая рекурсия в этом случае.   -  person refik    schedule 11.01.2017

Ответы (2)


arrow_upward
2
arrow_downward

sapply не в стиле передачи продолжения, поэтому вам необходимо его заменить.

Вот перевод стиля передачи продолжения в Python (другой язык, который не имеет правильных хвостовых вызовов):

def sum_ways_cps(n_times, k_sum, s_side, ctn):
    """Compute the number of ways to get the sum k by rolling an s-sided die
    n times. Then pass the answer to ctn."""

    if k_sum < n_times or k_sum > n_times * s_side:
        return ctn(0)
    elif n_times == 1:
        return ctn(1)
    else:
        f = lambda j, ctn: sum_ways_cps(n_times - 1, k_sum - j, s_side, ctn)
        return sum_cps(1, s_side + 1, 0, f, ctn)

def sum_cps(j, j_max, total_so_far, f, ctn):
    """Compute the sum of f(x) for x=j to j_max.
    Then pass the answer to ctn."""

    if j > j_max:
        return ctn(total_so_far)
    else:
        return f(j, lambda result: sum_cps(j + 1, j_max, total_so_far + result, f, ctn))


sum_ways_cps(2, 7, 6, print)  # 6
person Jason Orendorff    schedule 11.01.2017
comment
Вау, прочитав его, я получил переполнение стека. Строго говоря, будет ли sum_ways_cps считаться хвостовой рекурсией? - person refik; 12.01.2017
comment
Рекурсия здесь состоит в том, что sum_ways_cps хвостовые вызовы sum_cps, хвостовые вызовы f, хвостовые вызовы sum_ways_cps. - person Jason Orendorff; 14.01.2017
comment
Можно ли это записать как одну функцию? - person Eren Tantekin; 15.01.2017
comment
@ErenTantekin. Главное препятствие - это состояние алгоритма. Исходный алгоритм содержит не хвостовые рекурсивные вызовы, и всякий раз, когда происходит один из них, локальные переменные вызывающего (представляющие оставшуюся работу) сохраняются в стеке. Версия в этом ответе использует цепочку продолжений (лямбды) для представления той же информации. Если вы хотите избежать использования лямбда-выражений, вам придется представлять информацию другим способом (возможно, используя что-то вроде cons). - person Jason Orendorff; 20.01.2017

arrow_upward
1
arrow_downward

Попробуйте это (с рекурсией нам нужно подумать о линейном рекурсивном отношении, если мы хотим хвостовую рекурсивную версию):

f <- function(n, k) {
  if (n == 1) {                 # base case
    return(ifelse(k<=6, 1, 0))
  } else if (k > n*6 | k < n) { # some validation
    return(0)
  } 
  else {
    # recursive calls, f(1,j)=1, 1<=j<=6, otherwise 0  
    return(sum(sapply(1:min(k-n+1, 6), function(j) f(n-1,k-j))))  
  }
}

sapply(1:13, function(k) f(2, k))
# [1] 0 1 2 3 4 5 6 5 4 3 2 1 0
person Sandipan Dey    schedule 11.01.2017
comment
Это почти то же самое с моей реализацией. Я думаю, что это не квалифицируется как хвостовая рекурсия, потому что финальное действие - это не призыв к самому себе, а скорее несколько обращений к самому себе, а не суммирование. - person refik; 11.01.2017
comment
@refik, поскольку исходное рекурсивное отношение находится в форме свертки (которая включает суммирование нескольких вызовов f), точная рекурсивная реализация также будет того же типа. Если мы можем выразить рекуррентное отношение, например f(n,k)=f(n-p,r)+g(r), для некоторых целых чисел p, r и некоторой функции g, то его можно записать как хвостовую рекурсивную функцию. - person Sandipan Dey; 11.01.2017
comment
Разве это не ответ: нет, это невозможно, потому что ... вместо того, чтобы попробовать это ...? - person refik; 11.01.2017
comment
@refik не уверен, может быть, есть какая-то хорошая формула повторения, которую мы не знаем. нам нужно думать. Я просто попытался придумать какое-то рекурсивное решение, несколько близкое к вашим требованиям. - person Sandipan Dey; 11.01.2017