正在获取递归C编程的帮助

Question

给定一个长度为n的数组，要求编写程序计算该给定数组的长度为m的子序列数。

下面是代码。请看一下。

int recCountSubseq(int seqLength, int length, int s[]) {
    int answer;
    if (seqLength == 0) {       /* Base case: found a subseq of correct length */
        return 1;
    }
    if (seqLength >= length) {  /* Base case: only possible is seqLength == length*/
        return (seqLength==length);
    }
    /* Recursive case: two branches */
    answer = recCountSubseq(seqLength-1, length-1, s); /* s[length-1] is in subseq*/
    printf("answer=%dn", answer);
    answer += recCountSubseq(seqLength, length-1, s);  /* s[length-1] is not in subseq */
    printf("increased answer is %dn", answer);
    return answer;
}
void countSubseq(int seqLength, int length, int s[]) {    
    printf("#subseq = %dn", recCountSubseq(seqLength, length, s));    
}
int main() {
    int length;
    scanf("%d", &length);
    int seqLength;
    int i;
    int s[100];
    for (i=0;i<length; i++) {
        scanf("%d", &s[i]);
    }
    countSubseq(seqLength, length, s);
    return 0;
}

---

现在，我的问题是：为什么seqLength的值每次都在减少，这个代码到底是如何工作的？

Answer 1

函数具有未定义的行为，因为至少变量seqLength未初始化：

int seqLength;

任务还不清楚。如果您有一个包含n元素的数组，那么长度为m的连续子序列的数量，其中m <= n等于n - m + 1。

因此，编写这样一个函数没有多大意义。：）此外，我甚至看不出函数中哪里有对作为第三个参数传递的数组的访问。：）

我可以向你建议以下功能。至少它有一定的道理

#include <stdio.h>
size_t recCountSubseq( const int a[], size_t n, size_t m )
{
    if ( m <= n )
    {
        for ( size_t i = 0; i < m; i++ ) printf( "%d ", a[i] );
        printf( "n" );
    }
    return n <= m ? n == m : 1 + recCountSubseq( ++a, --n, m );
}
int main( void )
{
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    printf( "There are %zu subsequenciesn", recCountSubseq( a, sizeof( a ) / sizeof( *a ), 3 ) );
    return 0;
}

其输出为

1 2 3 
2 3 4 
3 4 5 
4 5 6 
5 6 7 
6 7 8 
7 8 9 
There are 7 subsequencies

我认为你对作业及其解决方案的解释有误。你应该重新检查他们的描述。

Answer 2

根据我的理解，您需要从用户那里获得子序列的长度，而这在您的代码中没有完成。

如果我的猜测是正确的，那么main（）函数看起来像这样：

int main(array<System::String ^> ^args)
{
  int length;
  printf("Length of array:");
  scanf("%d", &length);
  int seqLength;
  printf("Length of sub-seq:");
  scanf("%d", &seqLength);
  int i;
  int s[100];
  printf("Array of %d elements:", length);
  for (i=0;i<length; i++)
  {
    scanf("%d", &s[i]);
  }
  countSubseq(seqLength, length, s);
  return 0;
}