Can a convolution function be written in tail recursive form?

Question

I have a function that I want to write in tail recursive form. The function calculates the number of ways to get the sum k by rolling s single-sided stamp n times. I saw a mathematical solution to this function on this answer . It looks like this:

My recursive implementation in 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)) } } 

I tried to rewrite the function in the style of continuing the transfer, as I learned from this answer , but I failed. Is there a way to write this function in tail recursive form?

EDIT

I know that R does not optimize tail recursion. My question is not specific to R, a solution in any other language is also welcome. Even if it is a language that does not optimize tail recursion.

Answer 1

sapply not in a continuation style, so you need to replace it.

Here's a translation into the style of continuing transmission in Python (another language that doesn't have the right 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 

Answer 2

Try this (with recursion, we need to think about a linear recursive relation if we want to get a recursive version):

 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,kj)))) } } sapply(1:13, function(k) f(2, k)) # [1] 0 1 2 3 4 5 6 5 4 3 2 1 0