使用递归的数字序列

Question

我想像这样计算数字序列：

n*(n-1)+n*(n-1)*(n-2)+n*(n-1)*(n-2)*(n-3)+n*(n-1)*(n-2)*(n-3)*(n-4)+...+n(n-1)...(n-n)

例如 n=5 总和等于 320.

我有一个函数，计算一个元素：

int fac(int n, int s)
{
    if (n > s)
        return n*fac(n - 1, s);
    return 1;
}

Answer 1

好的，没什么好写的。如果你想解决这个递归问题，我建议使用 2 种方法。（由于 recrusiv faculty，复杂性一团糟，运行时间会随着大数而急剧增加！）

  int func(int n){
     return func(n, 2);
   }

   int func(int n, int i){
        if (i < n){
           return n*(fac(n-1,n-i)+func(n, i + 1));      
        }else return 0;
    }


     int fac(int i,int a){
         if(i>a){
           return i*fac(i-1, a);
         }else return 1;
      }

Answer 2

是这样的吗？

function fac(int n, int s)
{
    if (n >= s)
        return n * fac(n - 1, s);
    return 1;
}

int sum = 0;
int s = 4;
n = 5;
while(s > 0)
{
    sum += fac(n, s);
    s--;
}
print sum; //320

无循环版本：

int fac(int n, int s)
{
    if (n >= s)
        return n * fac(n - 1, s);
    return 1;
}

int compute(int n, int s, int sum = 0)
{
    if(s > 0)
        return compute(n, s - 1, sum + fac(n, s));
    return sum;
}

print compute(5, 4); //320

Answer 3

为每个被加数重新计算阶乘非常浪费。相反，我建议使用记忆。如果您重新订购

n*(n-1) + n*(n-1)*(n-2) + n*(n-1)*(n-2)*(n-3) + n*(n-1)*(n-2)*(n-3)*...*1

你得到

n*(n-1)*(n-2)*(n-3)*...*1 + n*(n-1)*(n-2)*(n-3) + n*(n-1)*(n-2) + n*(n-1)

注意你是如何从 1..n 的乘积开始，然后加上 1..n 除以 1 的乘积，然后加上除以 1*2 的乘积，依此类推

我认为您的函数的更有效定义是（在 Python 中）：

def f(n):
    p = product(range(1, n+1))
    sum_ = p
    for i in range(1, n-1):
        p /= i
        sum_ += p
    return sum_

这个定义的递归版本是：

def f(n):
    def go(sum_, i):
        if i >= n-1:
            return sum_
        return sum_ + go(sum_ / i, i+1)
    return go(product(range(1, n+1)), 1)

最后但同样重要的是，您还可以通过使用 reduce 生成被加数列表来定义函数而无需任何显式递归（这更 'functional' -- 就像在函数式编程中一样 - - 样式):

def f(n):
    summands, _ = reduce(lambda (lst, p), i: (lst + [p], p / i),
                         range(1, n),
                         ([], product(range(1, n+1))))
    return sum(summands)

这种风格在函数式编程语言如Haskell中非常简洁； Haskell 有一个函数调用 scanl，它简化了加数的生成，因此定义只是：

f n = sum $ scanl (/) (product [1..n]) [1..(n-2)]

使用递归的数字序列

sequence of numbers using recursion

recursion

sequence