A function subprogram may behave like a function in calculus, and return a value depending on its arguments. In the first example, we define a function whose value is the square of a positive argument and whose value is zero for non-positive argument. A function subprogram does not need to return a number, for example it may print some lines depending on its inputs, as in the Hanoi Towers program. A function may call itself in C, as in the power program or the factorial program. This process is called recursion. Of course, care has to be taken that the function doesn't call itself infinitely many times. A function need not even have arguments but be used to isolate part of the task.
/**********************************************************************
A. Treibergs 1-30-6
Program that defines a function subprogram and prints a table.
First form: function defined before main().
fun1.c
**********************************************************************/
#include <stdio.h>
#include <stdlib.h>
double
funct ( double x ) /* funct(x) is zero for negative x, x*x otherwise. */
{
double y;
if( x <= 0 )
y = 0.0;
else
y = x*x;
return y;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
int
main(void)
{
int i;
double x, y;
printf(" x f(x) f(f(x))\n");
printf(" ------- ----- -------\n");
for ( i = 0 ; i <= 20; i=i+1)
{
x = 0.1 * i - 1.0;
y = funct(x);
printf ( "%7.3f \t %6.3f\t\t %6.3f\n", x, y, funct(y) );
}
return EXIT_SUCCESS;
}
/**********************************************************************
A. Treibergs 1-30-6
Program that defines a function subprogram and prints a table.
Second form: function prototype before main(),
function subprogram after main().
fun2.c
**********************************************************************/
#include <stdio.h>
#include <stdlib.h>
double
funct ( double x); /* Function prototype. */
int
main(void)
{
int i;
double x, y;
printf(" x f(x) f(f(x))\n");
printf(" ------- ----- -------\n");
for ( i = 0 ; i <= 20; i=i+1)
{
x = 0.1 * i - 1.0;
y = funct(x);
printf ( "%7.3f \t %6.3f\t\t %6.3f\n", x, y, funct(y) );
}
return EXIT_SUCCESS;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
double
funct ( double x ) /* funct(x) is zero for negative x, x*x otherwise. */
{
double y;
if( x <= 0 )
y = 0.0;
else
y = x*x;
return y;
}
/**********************************************************************
A. Treibergs 1-30-6
Program that uses a function recursively to compute a positive integer
power of an integer. Not that it takes two integer arguments and
returns an integer. Also it inputs two numbers separated by white space.
pow1.c
**********************************************************************/
#include <stdio.h>
#include <stdlib.h>
int
power( int base, int exp)
{
int res;
if (exp == 0)
res = 1; /* Zeroth power is equal to 1 */
else
res = base * power ( base, exp-1 ); /* Recursive definition of power */
return res;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
int
main(void)
{
int m, n;
print f("Enter two positive integers, the base and the exponent : ");
scanf ("%d %d", &n, &m);
printf ("%d power of %d is equal to %d.\n", m, n, power(n,m) );
return EXIT_SUCCESS;
}
/**********************************************************************
A. Treibergs 1-30-6
Program that uses a function recursively to compute arbitrary integer
power of a double. Note that it takes a double and an integer argument
returns a double.
pow2.c
**********************************************************************/
#include <stdio.h>
#include <stdlib.h>
double
power ( double base, int exp )
{
double res;
if (exp < 0)
res = 1.0 / power ( base, -exp ); /* Negative power is 1/positive power */
else
if (exp == 0)
res = 1.0; /* Zeroth power is equal to 1 */
else
res = base * power ( base, exp-1 ); /* Recursive definition of power */
return res;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
int main(void)
{
int m;
double n;
printf ( "Enter the base and the exponent : ");
scanf ( "%lf %d", &n, &m);
printf ( "%d power of %lf is equal to %lG.\n", m, n, power(n,m) );
return EXIT_SUCCESS;
}
/**********************************************************************
A. Treibergs 1-30-6
Factorial function defined recursively.
fun3.c
**********************************************************************/
#include <stdio.h>
#include <stdlib.h>
int
fact ( int n )
{
int res;
if (n == 0)
res = 1; /* Factorial of 1 is equal to 1 */
else
res = n * fact(n-1); /* Recursive definition of factorial of n */
return res;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
int
main ( void )
{
int n;
printf ( "Enter a positive integer : ");
scanf ( "%d", &n );
printf ( "%d factorial is equal to %d.\n", n, fact(n) );
return EXIT_SUCCESS;
}
The Towers of Hanoi puzzle was invented by the Frenchman Eduard Lucas in 1883. It became enormously popular (the iPod shuffle or Rubik's Cube of its day?) If you search the internet you will find many sites that animate the moves and discuss the algorithms. There are several other ways to move the rings as well. One very nice site is http://en.wikipedia.org/wiki/Tower_of_Hanoi
Hey! How many moves does it take to solve the n-ring Hanoi's Tower problem? If qn denotes this number then q1=1, q2=3, q3=7, q4=15. In general the recursive nature of the solution says that q1=1 and qn = 2qn-1 + 1, roughly the number doubles each step. The difference equation can be solved to give qn = 2n - 1. To see an explanation of this solution go to Math Circle notes of Berton Earnshaw http://www.math.utah.edu/mathcircle/notes/earnshaw.pdf
/******************************************************************
Treibergs 2-2-6
Recursive Solution of the Towers of Hanoi Puzzle
Move left pile of n rings to right pole by moving one ring at
time from its pole to either one of the other two without placing
a larger ring on top of a smaller one.
L C R
II II II
II II II
(1111) II II
(22222222) II II
(333333333333) II II
(4444444444444444) II II
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
The program main calls the function mover(n,'L','R','C')
which prints the directions on moving the n rings from the
"source" pole labeled 'L' at the start, to the "target" pole labeled
'R' at the start with extra third "other" pole labeled 'C' at the
start. Mover, in turn, calls itself first to move n-1
rings from the "source" pole to the "other" pole, then, second, move
the n-th ring from "source" pole to the "target" pole and then, third,
it calls itself again to move n-1 rings now on the "other" pole to
the "target" pole.
hanoi.c
******************************************************************/
# include <stdio.h>
# include <stdlib.h>
void
mover( int num, char source, char target, char other);
int
main(void)
{
int n;
printf ("Towers of Hanoi Puzzle\n\n Enter number of rings : ");
scanf( "%d",&n);
if( n > 0)
{
mover( n, 'L', 'R', 'C');
}
else
printf("The number of rings must be positive.\n");
return EXIT_SUCCESS;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
void
mover( int n, char source, char target, char other)
{
if( n >0)
{
mover ( n - 1, source, other, target );
printf (" Move ring %2d from %c to %c\n", n, source, target);
mover ( n - 1, other, target, source );
}
return;
}
/* Treibergs 2-6-6
Function to compute factorial via recursion
today.c */
# include <stdio.h>
# include <stdlib.h>
unsigned long int
factr( int n); /* function prototype */
int
main(void)
{
int n;
printf ("Factorials\n\n Enter a number n = ");
scanf( "%d",&n);
if( n >= 0)
printf(" %4d ! = %lu\n", n, factr(n));
else
printf("The number must be positive.\n");
return EXIT_SUCCESS;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
unsigned long int
factr( int n)
{
if( n <= 1)
return 1UL;
else
return (unsigned long int)n * factr(n-1);
}
/* Treibergs 2-8-6
Program to solve Hanoi Tower Puzzle:
Move n rings from L to R pole.
today.c */
# include <stdio.h>
# include <stdlib.h>
void
mover( int n, char start, char finish, char temp)
{
if( n > 0)
{
mover(n-1, start, temp, finish);
printf(" Move ring %d from %c to %c \n", n, start, finish);
mover(n-1, temp, finish, start);
}
return;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
int
main(void)
{
int n;
printf(" Towers of Hanoi\n\n Please enter the number of rings :");
scanf( "%d", &n);
if(n>0)
mover(n,'L', 'R', 'C');
else
printf(" The number must be positive.\n");
return EXIT_SUCCESS;
}