我有一个要以尾递归形式编写的函数。该函数通过滚动 s
面骰子 n
次来计算获得 k
总和的方法数。我在 this answer 上看到了这个函数的数学解.具体如下:
我在 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))
}
}
正如我从 this answer 中学到的那样,我尝试以延续传递的方式重写该函数,但我没有成功。有没有办法以尾递归形式编写此函数?
编辑
我知道 R 没有针对尾递归进行优化。我的问题不是特定于 R 的,欢迎使用任何其他语言的解决方案。即使它是一种不针对尾递归进行优化的语言。
最佳答案
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
关于recursion - 一个卷积函数可以写成尾递归形式吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41585207/