188 Intermediate C Programming
return f ( dx - 1 , dy ) + f( dx , dy - 1) ;18
Both of these versions do exactly the same thing. The compiler actually creates temporary
variables if local variables are not used.
13.3 The Tower of Hanoi
The listing below shows how to calculate the number of moves required to move n disks
in The Tower of Hanoi problem:
// hanoi1 . c1
// calc ulate the number of moves needed to move n disks2
#in clude < stdio .h >3
#in clude < stdlib .h >4
int f( i n t n)5
{6
/* Base case */7
i f (n == 1)8
{9
return 1;10
}11
/* Recu rsive case */12
return 2 * f (n - 1) + 1;13
}14
int main ( i n t argc , char * argv [])15
{16
int n;17
i f ( argc < 2)18
{19
printf (" need one positive integer . n") ;20
return EXIT _FAILUR E ;21
}22
n = ( in t ) strtol ( argv [1] , NULL , 10) ;23
i f (n <= 0)24
{25
printf (" need one positive integer . n") ;26
return EXIT _FAILUR E ;27
}28
printf (" f(% d) = % d . n" , n , f ( n) );29
return EXIT _SUCCES S ;30
}31
A more interesting program prints the solution—the sequence of disk moves that solves
the problem. To do this, we create a function called move that takes four arguments:
1. The disks to move. The disks are represented by positive integers, where 1 is the
smallest disk and 2 is the second smallest disk, etc.
2. The source pole
3. The destination pole
4. The additional pole
This program follows the procedure in Section 12.3: Move the top n − 1 disks to the
additional pole (i.e., C), then move the n
th
disk from A to B, and then move the top n − 1
disk from C to B. Notice how short and simple the code is.
Recursive C Functions 189
// hanoi2 . c1
// print the steps moving n disks2
#in clude < stdio .h >3
#in clude < stdlib .h >4
void move ( i n t disk , char src , char dest , char additio nal )5
{6
/* Base case */7
i f ( disk == 1)8
{9
printf (" move disk 1 from %c to %c n" , src , dest );10
return ;11
}12
/* Recu rsive case */13
move ( disk - 1, src , additional , dest ) ;14
printf (" move disk % d from % c to % cn " , disk , src , dest );15
move ( disk - 1, additional , dest , src );16
}17
int main ( i n t argc , char * argv [])18
{19
int n;20
i f ( argc < 2)21
{22
printf (" need one positive integer . n") ;23
return EXIT _FAILUR E ;24
}25
n = ( in t ) strtol ( argv [1] , NULL , 10) ;26
i f (n <= 0)27
{28
printf (" need one positive integer . n") ;29
return EXIT _FAILUR E ;30
}31
move (n , ’A ’, ’B ’, ’C ’);32
return EXIT _SUCCES S ;33
}34
When the input is 3, the program’s output is:
move disk 1 from A to B
move disk 2 from A to C
move disk 1 from B to C
move disk 3 from A to B
move disk 1 from C to A
move disk 2 from C to B
move disk 1 from A to B
This output matches the steps in Fig. 12.8.
190 Intermediate C Programming
13.4 Integer Partition
The implementation of formula (12.8) in C is shown below:
sum = 0;1
for (i = 1; i < n; i ++)2
{3
// the first value is i4
// f( n - i) ways for the remaining value of n - i5
sum += f (n - i );6
}7
sum ++; // first value is n and the remaining is zero8
Notice the nearly one-to-one mapping from the mathematical expression to the C code. The
complete program is shown below.
// part ition . c1
// impl ement the r ecursive relation for calculati ng2
// the number of par t itions for a positive integer3
#in clude < stdio .h >4
#in clude < stdlib .h >5
int f( i n t n)6
{7
int i;8
int sum = 0;9
/* Base case */10
i f (n == 1)11
{12
return 1; // only one way to p artition 113
}14
/* Recu rsive case */15
for (i = 1; i < n; i ++)16
{17
sum += f (n - i );18
}19
sum ++;20
return sum ;21
}22
int main ( i n t argc , char * argv [])23
{24
int n;25
i f ( argc < 2)26
{27
printf (" need one positive integer . n") ;28
return EXIT _FAILUR E ;29
}30
n = ( in t ) strtol ( argv [1] , NULL , 10) ;31
i f (n <= 0)32
{33
printf (" need one positive integer . n") ;34
return EXIT _FAILUR E ;35
Recursive C Functions 191
}36
printf (" f(% d) = % d . n" , n , f ( n) );37
return EXIT _SUCCES S ;38
}39
This program was executed with various arguments to produce the following result:
n f(n)
1 1
2 2
3 4
4 8
5 16
6 32
13.5 Factorial
Many books use factorial and Fibonacci numbers to motivate the need of recursion.
These are poor examples. This book does not start with these two popular examples for
good reasons, as explained below. The definition of factorial for positive integers or zero is:
f(n) =
(
1 when n is 0
n × f(n − 1) when n > 0
(13.1)
It is possible to define factorial for negative values or non integers; however, that definition
is beyond the scope of this book.
// fac torial1 .c1
#in clude < stdio .h >2
long i nt fac ( i n t n)3
{4
i f (n < 0)5
{6
printf (" n cannot be negative n ");7
return 0;8
}9
/* Base case */10
i f (n == 0)11
{12
return 1;13
}14
/* Recu rsive case */15
return n * fac ( n - 1);16
}17
By now, the main function should be quite easy to follow:
// ma infact o rial .c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
192 Intermediate C Programming
#d ef in e MAXN 204
long i nt fac ( i n t n) ;5
int main ( i n t argc , char * argv [])6
{7
int nval ;8
for ( nval = 0; nval <= MAXN ; nval ++)9
{10
long i nt fval = fac ( nval );11
printf (" fac (%2 d) = % ld n" , nval , fval );12
}13
return EXIT _SUCCES S ;14
}15
Here is the output of this program:
fac( 0) = 1
fac( 1) = 1
fac( 2) = 2
fac( 3) = 6
fac( 4) = 24
fac( 5) = 120
fac( 6) = 720
fac( 7) = 5040
fac( 8) = 40320
fac( 9) = 362880
fac(10) = 3628800
fac(11) = 39916800
fac(12) = 479001600
fac(13) = 6227020800
fac(14) = 87178291200
fac(15) = 1307674368000
fac(16) = 20922789888000
fac(17) = 355687428096000
fac(18) = 6402373705728000
fac(19) = 121645100408832000
fac(20) = 2432902008176640000
The function fac returns long int because the values quickly get too large for int when
n is greater than 12. The function fac is quite straightforward—a direct translation of the
mathematical definition. Why is this a bad example for introducing recursion? The reason
is that recursion is not necessary. It is possible to implement the same function without
using recursion.
// fac torial2 .c1
#in clude < stdio .h >2
long i nt fac2 ( in t n)3
{4
i f (n < 0)5
{6
printf (" n cannot be negative n ");7
return 0;8
}9
i f (n == 0)10
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.