Une fonction de convolution peut-elle être écrite sous forme récursive?

Question

J'ai une fonction que je veux écrire en forme récursive de la queue. La fonction calcule le nombre de façons d'obtenir la somme de k en lançant une matrice s fois n fois. J'ai vu la solution mathématique pour cette fonction sur this answer. Il se présente comme suit:

Ma référence mise en œuvre récursive en R est:

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

J'ai essayé de réécrire la fonction dans la continuité de style qui passe comme je l'ai appris de this answer, mais Je n'ai pas réussi. Existe-t-il un moyen d'écrire cette fonction sous forme récursive?

EDIT

Je sais que R n'optimise pas pour la queue-récursion. Ma question n'est pas spécifique à R, une solution dans une autre langue est la bienvenue. Même si c'est un langage qui n'optimise pas pour la récursivité de la queue.

Answer 1

sapply n'est pas dans le style passage de continuation, de sorte que vous devez remplacer il.

est une traduction Voici le style passage de continuation en Python (une autre langue qui ne pas ont des appels de queue appropriés):

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

Essayez cette (avec récursion, nous devons penser à une relation de récurrence linéaire si nous voulons une version récursive de la queue):

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