Using the recurrent relation comb( n, m ) = comb( n-1, m ) + comb( n-1, m-1 ) we can write recursive function:
- Code: Select all
int comb( n, m )
{
if( n == 1 || m == 0 || n == m )
return 1;
else
return comb( n-1, m ) + comb( n-1, m-1 );
}
The problem is to eliminate recursion from this function. I have writen two functions, comb2 and comb3 to do this job. Comb2 is "classic" recursion elimination, but comb3 is using modified method in which n and m are treated as global variables.
Here is the complete program:
- Code: Select all
#include <stdio.h>
#include <stdlib.h>
int comb( int, int );
int comb2( int, int );
int comb3( int, int );
typedef struct cell {
int x, m, n, ret_add;
} cell;
typedef struct cell_stack {
cell c;
struct cell_stack *next;
} cell_stack;
void push_stack( cell, cell_stack ** );
cell top_stack( cell_stack * );
void pop_stack( cell_stack ** );
int empty_stack( cell_stack * );
void new_stack( cell_stack ** );
typedef struct cell2 {
int x, ret_add;
} cell2;
typedef struct cell_stack2 {
cell2 c;
struct cell_stack2 *next;
} cell_stack2;
void push_stack2( cell2, cell_stack2 ** );
cell2 top_stack2( cell_stack2 * );
void pop_stack2( cell_stack2 ** );
int empty_stack2( cell_stack2 * );
void new_stack2( cell_stack2 ** );
int main()
{
int m, n;
printf( "Input n: " );
scanf( "%d", &n );
if( n < 0 ) {
printf( "Wrong input\n" );
return 1;
}
printf( "Input m: " );
scanf( "%d", &m );
if( m < 0 || n < m ) {
printf( "Wrong input\n" );
return 1;
}
printf( "comb( n, m ) = %d\n" , comb( n, m ) );
printf( "comb2( n, m ) = %d\n" , comb2( n, m ) );
printf( "comb3( n, m ) = %d\n" , comb3( n, m ) );
return 0;
}
int comb( int n, int m )
{
if( n == 1 || m == 0 || m == n )
return 1;
else
return comb( n - 1, m ) + comb( n - 1, m - 1 );
}
int comb2( int n, int m )
{
cell cel;
int ret_val;
cel.n = n;
cel.m = m;
cel.ret_add = 0;
cell_stack *s;
new_stack( &s );
push_stack( cel, &s );
do {
cel = top_stack( s );
pop_stack( &s );
switch( cel.ret_add ) {
case 0:
if( cel.n == 1 || cel.m == 0 || cel.n == cel.m ) {
ret_val = 1;
break;
}
else {
cel.ret_add = 1;
push_stack( cel, &s );
(cel.n)--;
cel.ret_add = 0;
push_stack( cel, &s );
break;
}
case 1:
cel.x = ret_val;
cel.ret_add = 2;
push_stack( cel, &s );
(cel.n)--;
(cel.m)--;
cel.ret_add = 0;
push_stack( cel, &s );
break;
case 2:
ret_val += cel.x;
break;
}
} while( ! empty_stack( s ) );
return ret_val;
}
void push_stack( cell c, cell_stack **s_p )
{
cell_stack *tmp = malloc( sizeof( cell_stack ) );
tmp->next = *s_p;
tmp->c = c;
*s_p = tmp;
}
void new_stack( cell_stack **s_p )
{
*s_p = NULL;
}
cell top_stack( cell_stack *s )
{
return s->c;
}
void pop_stack( cell_stack **s_p )
{
cell_stack *tmp = *s_p;
*s_p = (*s_p)->next;
free( tmp );
}
int empty_stack( cell_stack *s )
{
if( s == NULL )
return 1;
else
return 0;
}
int comb3( int n, int m )
{
cell2 cel;
int ret_val = 0;
cel.ret_add = 0;
cell_stack2 *s;
new_stack2( &s );
push_stack2( cel, &s );
do {
cel = top_stack2( s );
pop_stack2( &s );
switch( cel.ret_add ) {
case 0:
if( n == 1 || m == 0 || n == m ) {
ret_val = 1;
break;
}
else {
cel.ret_add = 1;
push_stack2( cel, &s );
n--;
cel.ret_add = 0;
push_stack2( cel, &s );
break;
}
case 1:
cel.x = ret_val;
cel.ret_add = 2;
push_stack2( cel, &s );
m--;
cel.ret_add = 0;
push_stack2( cel, &s );
break;
case 2:
ret_val += cel.x;
n++;
m++;
break;
}
} while( ! empty_stack2( s ) );
return ret_val;
}
void push_stack2( cell2 c, cell_stack2 **s_p )
{
cell_stack2 *tmp = malloc( sizeof( cell_stack2 ) );
tmp->next = *s_p;
tmp->c = c;
*s_p = tmp;
}
void new_stack2( cell_stack2 **s_p )
{
*s_p = NULL;
}
cell2 top_stack2( cell_stack2 *s )
{
return s->c;
}
void pop_stack2( cell_stack2 **s_p )
{
cell_stack2 *tmp = *s_p;
*s_p = (*s_p)->next;
free( tmp );
}
int empty_stack2( cell_stack2 *s )
{
if( s == NULL )
return 1;
else
return 0;
}
The problem is that I cannot understand why comb3 is working right. Simple check by "hand" is showing that comb2 and comb3 are computing the value in different way. But the result is always the same. Why?
