畳み込み関数を末尾の再帰形式で記述することはできますか？

Question

私はテールの再帰的な形で書く機能を持っています。この関数は、の合計を得る方法の数を、sの両面ダイn回を丸めて計算します。私はthis answerでこの関数の数学的解を見てきました。私は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)) 
    } 
} 

、しかし：Rで

マイ参照再帰的な実装は次のようになります。それは以下の通りです。私は成功しなかった。 tail-recursive形式でこの関数を書く方法はありますか？

EDIT

私は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