Getting help recursive C programming

Question

Given an array of length n, and the requirement is to write the program to calculate the number of sub-sequences of length m of that given array.

Below is the code to do it. Please, have a look.

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=%d\n", answer);

    answer += recCountSubseq(seqLength, length-1, s);  /* s[length-1] is not in subseq */
    printf("increased answer is %d\n", answer);

    return answer;
}

void countSubseq(int seqLength, int length, int s[]) {    
    printf("#subseq = %d\n", 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;
}

---

Now, my question: Why is the value of seqLength decreasing each time, and how exactly is this code working ?

Answer 1

The function has undefined behaviour because at least variable seqLength was not initialized:

int seqLength;

And the task is not clear. If you have an array with n elements then the number of continious subsequencies of length m where m <= n is equal to n - m + 1.

So writing such a function does not make great sense.:) Moreover I do not see even where in the function there is an access to the array passed as the third argument.:)

Insetad I can suggest you the following function. At least it has some sense.:)

#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 subsequencies\n", recCountSubseq( a, sizeof( a ) / sizeof( *a ), 3 ) );

    return 0;
}

Its output is

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

I think you are incorrectly interpretating the assignment and its solution. You should check their descriptions anew.

Answer 2

From my understanding, you need to get from the user the length of the sub-sequence, which is not being done in your code.

If my guess is correct, then the main() function would look like this:

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