可以用尾递归形式编写卷积函数吗？ [英] Can a convolution function written in tail recursive form?

问题描述

我有一个我想用尾递归形式写的函数。该函数通过滚动 s 双面骰 k 的总和的方法数> n 次。我已经在

我的参考递归在R中的实现是：

$ $ p $ sum_ways < - 函数（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的具体问题，任何其他语言的解决方案都是受欢迎的。即使它是一种不针对尾递归进行优化的语言。

解决方案

sapply 不是继续传递样式，所以你必须替换它。

这是一个Python中continuation-passing样式的翻译（另一种语言
计算获得总和k的方法数量，通过滚动一个s-sided die
n次，然后将答案传递给ctn。

如果k_sum < n_times或k_sum> n_times * s_side：
return ctn（0）
elif n_times == 1：
return ctn（1）
else：
f = lambda j，ctn：sum_ways_cps（ （1，s_side + 1，0，f，ctn）

def sum_cps（j，j_max，total_so_far，f，n_times - 1，k_sum_j，s_side，ctn）
return sum_cps ctn）：
计算x（x）到j_max的总和f（x），然后将答案传递给ctn。

if j> ; j_max：
return ctn（total_so_far）
else：
返回f（j，lambda结果：sum_cps（j + 1，j_max，total_so_far + result，f，ctn））


sum_ways_cps（2，7，6，print）＃6

I have a function that I want to write in tail recursive form. The function calculates the number of ways to get the sum of k by rolling an s sided die n times. I have seen the mathematical solution for this function on this answer. It is as follows:

My reference recursive implementation in R is:

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

I have tried to re-write the function in continuation passing style as I have learned from this answer, but I wasn't successful. Is there a way to write this function in tail-recursive form?

EDIT

I know that R doesn't optimise for tail-recursion. My question is not R specific, a solution in any other language is just as welcome. Even if it is a language that does not optimise for tail-recursion.

解决方案

sapply isn't in continuation-passing style, so you have to replace it.

Here's a translation to continuation-passing style in Python (another language that does not have proper tail calls):

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

这篇关于可以用尾递归形式编写卷积函数吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！