Fifth Week Examples: Functions

Following D. Milicic Fifth Week Examples.

Function Subprograms


A complicated program may be divided into smaller and simpler subprograms which are called "functions" in C. These subprograms in turn may be subdivided into smaller sub-subprograms. This way a complicated task may be understood in broad strokes, without worrying about the details at first. Then each of the subprograms can be further subdivided, and so on, dividing the complicated task into simple pieces. This is called structured programming.

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.


Function and Function Prototype examples.

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

One way to define a function is to put the function declaration and the statemets for the function before main(void). The other is to declare the function prototype before the main program and then place the function subprogram after the main program.
/**********************************************************************
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;
}



Power

A simple example of using a function recursively to compute the integer power of an integer.
/**********************************************************************
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;
}

Factorial


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



Towers of Hanoi Puzzle

The object of the game is to move the pile of rings from the left pole to the right pole by moving one ring at a time. The only condition is that rings have to be moved from one pole to another in such a way that a ring is always placed onto an empty pole or onto a larger ring. We shall develop a program to describe the solution. Our solution is based on induction on the number of rings to be moved. If there is one ring then we just move the ring from where it starts to where it wants to end up. Then assuming we can move a pile of n - 1 rings, we first move the top n - 1 rings from the left pole to the middle pole, then move the nth ring from the left pole to the right pole, and then move the n - 1 rings from the middle pole to the right pole. The roles of the "source", "target" and "other" poles varies for each of these moves. The program calls the function mover which calls itself inductively.

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;

}