컨볼 루션 (convolution) 기능을 꼬리 재귀 적 형태로 작성할 수 있습니까?

Question

꼬리 재귀 적 형태로 쓰고 싶은 기능이 있습니다. 이 함수는 s 양면 다이 n 번을 굴려서 k의 합계를 얻는 방법의 수를 계산합니다. this answer에서이 함수의 수학적 솔루션을 보았습니다. 그것은 다음과 같다 :

R 나의 참조 재귀 구현이 : 나는이 this answer에서 배운대로 스타일을 통과 계속에서 함수를 다시 쓰기 위해 노력했다

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

하지만, 나는 성공하지 못했습니다. tail-recursive 형식으로이 함수를 작성하는 방법이 있습니까?

편집

나는 R은 꼬리 재귀 최적화하지 않는다는 것을 알고있다. 내 질문은 R 특정하지 않습니다, 다른 언어로 솔루션을 환영합니다. 꼬리 재귀를 위해 최적화되지 않는 언어 인 경우에도 마찬가지입니다.

Answer 1

sapply가 계속-통과 스타일에없는, 당신은 교체해야하므로 그것. ?`Recall`에서

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

이 시도 (재귀와 함께, 우리는 우리가 꼬리 재귀 버전을 원하는 경우 선형 점화식의 생각해야) :

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