## Lab Test II : Solution

### The program

```#include <stdio.h>

#define MAX_N 9
#define ARR_DIM 10

int s[ARR_DIM][ARR_DIM];

int srec(n,k) {
if (k > n) return (0);
if (k==0) return ( (n==0) ? 1 : 0 );
return((n-1)*srec(n-1,k)+srec(n-1,k-1));
}

void siter () {
int n, k;

for (n=0; n<=MAX_N; ++n) for (k=0; k<=n; ++k) {
if (k==0) s[n][k] = ((n==0) ? 1 : 0);
else if (k==n) s[n][k] = s[n-1][k-1];
else s[n][k] = (n-1)*s[n-1][k]+s[n-1][k-1];
}
}

int main ()
{
int n, k;

printf("Recursive method\n");
printf(" n | ");
for (k=0; k<=MAX_N; ++k) printf(" s(n,%d)",k);
printf("\n---+");
for (k=0; k<=7*(MAX_N+1); ++k) printf("-");
printf("\n");
for (n=0; n<=MAX_N; ++n) {
printf("%2d |", n);
for (k=0; k<=n; ++k)
printf("%7d",srec(n,k));
printf("\n");
}
for (k=0; k<=4+7*(MAX_N+1); ++k) printf("-");
printf("\n\n");

printf("Iterative method\n");
printf(" n | ");
for (k=0; k<=MAX_N; ++k) printf(" s(n,%d)",k);
printf("\n---+");
for (k=0; k<=7*(MAX_N+1); ++k) printf("-");
printf("\n");
siter();
for (n=0; n<=MAX_N; ++n) {
printf("%2d |", n);
for (k=0; k<=n; ++k)
printf("%7d",s[n][k]);
printf("\n");
}
for (k=0; k<=4+7*(MAX_N+1); ++k) printf("-");
printf("\n\n");
}
```

### Output

```Recursive method
n |  s(n,0) s(n,1) s(n,2) s(n,3) s(n,4) s(n,5) s(n,6) s(n,7) s(n,8) s(n,9)
---+-----------------------------------------------------------------------
0 |      1
1 |      0      1
2 |      0      1      1
3 |      0      2      3      1
4 |      0      6     11      6      1
5 |      0     24     50     35     10      1
6 |      0    120    274    225     85     15      1
7 |      0    720   1764   1624    735    175     21      1
8 |      0   5040  13068  13132   6769   1960    322     28      1
9 |      0  40320 109584 118124  67284  22449   4536    546     36      1
---------------------------------------------------------------------------

Iterative method
n |  s(n,0) s(n,1) s(n,2) s(n,3) s(n,4) s(n,5) s(n,6) s(n,7) s(n,8) s(n,9)
---+-----------------------------------------------------------------------
0 |      1
1 |      0      1
2 |      0      1      1
3 |      0      2      3      1
4 |      0      6     11      6      1
5 |      0     24     50     35     10      1
6 |      0    120    274    225     85     15      1
7 |      0    720   1764   1624    735    175     21      1
8 |      0   5040  13068  13132   6769   1960    322     28      1
9 |      0  40320 109584 118124  67284  22449   4536    546     36      1
---------------------------------------------------------------------------
```

### The program

```#include <stdio.h>

#define MAX_N 9
#define ARR_DIM 10

int S[ARR_DIM][ARR_DIM];

int Srec(n,k) {
if (k > n) return (0);
if (k==0) return ( (n==0) ? 1 : 0 );
return(k*Srec(n-1,k)+Srec(n-1,k-1));
}

void Siter () {
int n, k;

for (n=0; n<=MAX_N; ++n) for (k=0; k<=n; ++k) {
if (k==0) S[n][k] = ((n==0) ? 1 : 0);
else if (k==n) S[n][k] = S[n-1][k-1];
else S[n][k] = k*S[n-1][k]+S[n-1][k-1];
}
}

int main ()
{
int n, k;

printf("Recursive method\n");
printf(" n | ");
for (k=0; k<=MAX_N; ++k) printf(" S(n,%d)",k);
printf("\n---+");
for (k=0; k<=7*(MAX_N+1); ++k) printf("-");
printf("\n");
for (n=0; n<=MAX_N; ++n) {
printf("%2d |", n);
for (k=0; k<=n; ++k)
printf("%7d",Srec(n,k));
printf("\n");
}
for (k=0; k<=4+7*(MAX_N+1); ++k) printf("-");
printf("\n\n");

printf("Iterative method\n");
printf(" n | ");
for (k=0; k<=MAX_N; ++k) printf(" S(n,%d)",k);
printf("\n---+");
for (k=0; k<=7*(MAX_N+1); ++k) printf("-");
printf("\n");
Siter();
for (n=0; n<=MAX_N; ++n) {
printf("%2d |", n);
for (k=0; k<=n; ++k)
printf("%7d",S[n][k]);
printf("\n");
}
for (k=0; k<=4+7*(MAX_N+1); ++k) printf("-");
printf("\n\n");
}
```

### Output

```Recursive method
n |  S(n,0) S(n,1) S(n,2) S(n,3) S(n,4) S(n,5) S(n,6) S(n,7) S(n,8) S(n,9)
---+-----------------------------------------------------------------------
0 |      1
1 |      0      1
2 |      0      1      1
3 |      0      1      3      1
4 |      0      1      7      6      1
5 |      0      1     15     25     10      1
6 |      0      1     31     90     65     15      1
7 |      0      1     63    301    350    140     21      1
8 |      0      1    127    966   1701   1050    266     28      1
9 |      0      1    255   3025   7770   6951   2646    462     36      1
---------------------------------------------------------------------------

Iterative method
n |  S(n,0) S(n,1) S(n,2) S(n,3) S(n,4) S(n,5) S(n,6) S(n,7) S(n,8) S(n,9)
---+-----------------------------------------------------------------------
0 |      1
1 |      0      1
2 |      0      1      1
3 |      0      1      3      1
4 |      0      1      7      6      1
5 |      0      1     15     25     10      1
6 |      0      1     31     90     65     15      1
7 |      0      1     63    301    350    140     21      1
8 |      0      1    127    966   1701   1050    266     28      1
9 |      0      1    255   3025   7770   6951   2646    462     36      1
---------------------------------------------------------------------------
```