在循环

Question

解决复发我知道如何解决的递推关系，当他们不涉及任何额外的循环，即：

int recursive_method(int n){ 
    if(n == 1){ 
     return 1; 
    } 
    some constant statement; 
    recursive_method(n-1); 

    return n; } 

试图解决环路内复发像下面，当我的问题来了：

int recursive_method(int n){ 
     if(n == 1){ 
      return 1; 
     } 
     for(int i = 1; i<n; i++){ 
      some constant statement; 
      recursive_method(n-1); 
     } 
     return n; } 

当试图建立对这个问题的递推关系上面它看起来像

T(n) = 1 if n<2; 
     sum(from i=1 to n){T(n-1) + c} if n>=2 

换句话说，成本从1到n的总和？ 如果不是，我该如何去思考这样的问题？

Answer 1

您在递归情况下对T（n）的表达式是正确的，但它可以显着简化。具体地，请注意，在总和所做的工作是独立于求和指数的，所以可以改写

总和从i = 1到n {T（N-1）+ C}

为

NT（N - 1）+ CN

所以你会拥有

T（N）= 1（如果n ≤ 1）

T（N）= NT（N - 1）+ CN（否则）