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.

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

/********************************************************************** 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 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 *n*th 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 *q _{n}* denotes this number
then

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