CS13002 Programming and Data Structures | Spring semester |
Functions and recursion
Imagine a hotel with infinitely many rooms 0,1,2,... On a rainy night all the rooms numbered 1,2,3,... are occupied by tenants. Room number 0 is used as the reception, it being opposite to the entrance. Every tenant was enjoying TV and waiting for a sumptuous dinner being prepared in the adjacent restaurant.
All of a sudden a bus carrying another infinite number of passengers arrives in front of the hotel's entrance. The chauffeur meets the manager and requests him to give rooms to all the passengers. It was a stormy night and there were no other hotels in the vicinity. So the manager devises a plan. He first relocates the existing tenants, so that the tenant at room no m goes to room no 2m-1 for all m=1,2,3,... He numbers the new guests -1,-2,-3,... and allocates the room 2m for passenger -m. He then writes a small computer program that notifies people of the new room allotment. He uses the following function:
0 if n = 0, f(n) = 2m - 1 if n = m > 0, 2m if n = -m for some m > 0.Everybody seems happy at this. Only the boarder of room no 224,036,583-1 (the largest known prime number of today, a 7235733-digit number) raises an objection indicating that he has to move too many rooms ahead. He insists that the current occupant of room number n should not be asked to shift by more than n/2 rooms. The manager complies and comes up with a second function:
g(n) = The manager allegedly wrote a C program. His initial program looked like:
#include <stdio.h> int f ( int n ) { if (n == 0) return (0); else if (n > 0) return (2*n-1); else return (-2*n); } int main () { int n; while (1) { printf("Input n : "); scanf("%d",&n); printf("Room number for %d is %d.\n", n, f(n)); } }After the request of Mr. Mersenne the XLI, the manager changed his program to:
#include <stdio.h> int g ( int n ) { int m; if (n == 0) return (0); else if (n < 0) return (-3*n); else { m = (n + 1)/2; if (n % 2 == 0) return (3*m-1); else return(3*m-2); } } int main () { int n; while (1) { printf("Input n : "); scanf("%d",&n); printf("Room number for %d is %d.\n", n, g(n)); } }There is a technical problem here. Though the hotel in the story has infinitely many rooms and the bus carried infinitely many passengers, C's integers are limited in size (32 or 64 bits). But then since this is a story, we may take liberty to imagine about a fabulous C compiler that supports integers of any size!
Translating mathematical functions in C
The above example illustrates how we can write functions in C. A function is expected to carry out a specific job depending on the argument values passed to it. After the job is accomplished, the function returns some value to the caller. In the above example, the function f (or g) accepts as an argument the number of the tenant, computes the room number of the tenant and returns this value to the place where it is called.
The basic syntax of writing a function goes like this:
return_type function_name ( list_of_arguments ) { function body }The argument list should be a comma-separated list of type-name pairs, where type is any valid data type and name is any legal formal name of a variable. Argument values can be accessed inside the function body using these names.
The return type of a function should again be a valid data type (like int, float, char *). A function may even choose to return no explicit values in which case its return type is to be mentioned as void.
The function body starts with a declaration of local variables. These variables together with the function arguments are accessible only in the function body and not outside it.
After the declarations one writes the C statements that compute the specific task that the function is meant for. The function returns a value using the statement:
return (return_value);The parentheses around return_value are optional. In case a function is expected to return nothing (i.e., void), the return statement looks like:
return;The return statement not only returns a value (possibly void) to the caller, but also returns the control back to the place where it is called. In case no explicit return statements are present in the function body, control goes back to the caller after the entire body of the function is executed.
Calling a function uses the following syntax:
function_name ( argument_values )Here argument values are provided as a comma-separated list of expressions. The formal names of the function arguments have absolutely nothing to do with the expressions passed during the call. However, the number of arguments and their respective types in a function call must match with those that are declared in the function header. In some cases data of different types are implicitly typecast when passed to functions, but it is advisable that you do not rely too much on C's automatic typecasting mechanism. That may lead to unwelcome run-time errors.
Functions may call other functions in the function body. In fact, a function call can be treated as an expression. It is like referring to a+b as add(a,b). Just because your keyboard does not support enough symbols, you have to call your functions by special names.
A function is regarded as an isolated entity that can perform a specific job. Therefore, if that specific job is to be carried out several times (possibly) with different argument values, functions prove to be useful. Functions also add to the legibility and modularity of programs, thereby enhancing simpler debugging. It is a bad practice to write long monolithic programs. We encourage you to break up the monolithic structure into logically coherent parts and implement each part as a function.
Functions (like loops) provide a way in which the standard sequential top-to-bottom flow of control is disturbed. This is the reason why functions may pose some difficulty to an inexperienced programmer. But the benefits they provide far outweigh one's efforts to master them. Guess what, you too must master them!
Example: If a program requires computation of several gcd's, it is advisable to write a function and call it with appropriate parameters as and when a gcd is to be calculated.
#include <stdio.h> int gcd ( int a , int b ) { int r; /* Check for errors : gcd(0,0) is undefined */ if ((a==0) && (b==0)) return (0); /* Make the arguments non-negative */ if (a < 0) a = -a; if (b < 0) b = -b; /* Special case : gcd(a,0) = a */ if (b == 0) return (a); /* The Euclidean gcd loop */ while (1) { r = a % b; if (r == 0) return (b); a = b; b = r; } } int main () { int i, j, s; s = 0; for (i=1; i<=20; ++i) { for (j=i; j<=20; ++j) { s += gcd(j,i); } } printf("The desired sum = %d\n", s); }Example: In all the previous examples we have made the function call at only one place. One may replace this call by an explicit code carried out in the function. However, if the same function is called multiple times, inserting an equivalent code at all call locations increases the size of the code and calls for separate maintenance of the different copies. This is your first tangible benefit of using functions.
Think of a situation when a committee of n members need be formed. The committee must have a core team consisting of at least two members and no more than one-third of the entire committee. In how many ways the core committee may be selected?
Here is a program that computes this number: function1.c
#include <stdio.h> int factorial ( int n ) { int prod = 1, i; for (i=2; i<=n; ++i) prod *= i; return(prod); } int binomial ( int n , int r ) { return(factorial(n)/(factorial(r)*factorial(n-r))); } int main () { int n, i, s = 0; printf("Total number of members : "); scanf("%d",&n); for (i=2; i<=n/3; ++i) s += binomial(n,i); printf("Total number of ways = %d\n", s); }Example: Here is a more complicated example. Suppose we want to print the square root of an integer truncated after the third digit following the decimal point. We use the standard algorithm taught in the school. The algorithm finds successive digits in the square root. The following example illustrates a typical computation of a square root:
153 | 12.369 1 | +----+ 22 | 53 | 44 +--- 243 | 900 | 729 +----- 2466 | 17100 | 14796 +------- 24729 | 230400 | 222561 +--------- 7839Here is the complete source code: function2.c#include <stdio.h> int nextDigit ( int r , int s , int grp ) /* Here r is whatever remains, s is the sqrt found so far, and grp is the next two digits to be considered. */ { int d = 0; /* Keep on searching for the next digit in the square root */ while ((20*s+d)*d <= 100*r+grp) ++d; /* Here d is just one bigger than the correct digit */ return(d-1); } void printSqrt ( int n ) { int s, /* Square root found so far */ r, /* Whatever remains */ d, /* next digit */ nl, /* Number of digits to the left of the decimal point */ nr = 3, /* Number of digits to the right of the decimal point */ grp[8], /* 2-digit groups */ sgn, /* Sign of n */ i; /* An index */ if (n < 0) { sgn = 1; n = -n; } else sgn = 0; if (n == 0) { nl = 1; grp[0] = 0; } else { nl = 0; while (n != 0) { grp[nl] = n % 100; /* Save next 2-digit group */ n /= 100; ++nl; } } /* Initialize */ s = 0; r = 0; /* First print the digits to the left of the decimal point */ for (i=nl-1; i>=0; --i) { d = nextDigit(r,s,grp[i]); printf("%d",d); r = (100 * r + grp[i]) - (20 * s + d) * d; s = 10 * s + d; } /* Print the decimal point */ printf("."); /* Print digits after the decimal point */ for (i=0; i<nr; ++i) { d = nextDigit(r,s,0); printf("%d",d); r = 100 * r - (20 * s + d) * d; s = 10 * s + d; } /* Square root of negative numbers should be imaginary */ if (sgn) printf("i"); printf("\n"); } int main () { int n; printf("Enter an integer : "); scanf("%d",&n); printSqrt(n); }Example: C provides many built-in functions. For example, the main function is a built-in function and must be present in any executable program. It returns an int value. It may also accept arguments. Here is the complete prototype of main:
int main ( int argc , char *argv[] ) { ... }One cannot call the main function from any other function in a program. If that is the case, who calls it and who uses its return value? The external world! When you run your program from a shell (possibly by typing ./a.out), you can pass (command-line) arguments to main. Moreover, when the program terminates, the return value of main is returned to the shell. You may choose to use the value for doing something useful.
Think of a call like this:
./a.out -5 3.1416 foo.txtWhen the main function starts execution, its argc parameter receives the value 4, because the total number of arguments including ./a.out is 4. The other argument argv is actually an array of arrays of characters. argv[0] gets the string "./a.out", argv[1] the string "-5", argv[2] the string "3.1416", and argv[3] the string "foo.txt". You can process these values from inside the main function. For example, you may supply a file name, some initial values, etc. via command-line arguments.
Some other built-in C functions include printf and scanf. A queer thing about these functions is that they support variable number of parameters. You can also write functions with this property, but we won't discuss it here.
Function prototypes
As long as a function is defined earlier (in the program) than it is called, there seems to be no problem. However, if the C compiler meets a function call before seeing its definition, it assumes that the function returns an int. Eventually the compiler must encounter the actual definition of the function. If the compiler then discovers that the function returns a value of type other than int, it issues a mild warning message. Compilation then proceeds successfully. However, when you run this program, you may find awkward run-time errors. That happens because the run-time system typecasts data of another type to int. That may create troubles in esoteric situations.
The way out is to always define a function earlier than it is called. Unfortunately, there is a situation where this cannot be done, namely, when a function egg() calls a function chicken() and the function chicken() also calls egg(). Which function will then be defined earlier?
The most graceful way to tackle this problem is to define the prototype of a function towards the beginning of your program. The prototype only mentions the return type and parameter types. The body may be (and must be) defined somewhere else, even after it is called. A function prototype looks like the first line of the function followed by a semicolon (instead of its body surrounded by curly braces).
return_type function_name ( argument_list );For example, the gcd, nextDigit and printSqrt functions defined above have the following prototypes:
int gcd ( int a , int b ); int nextDigit ( int r , int s , int grp ); void printSqrt ( int n );During a prototype declaration the names of the variables play no roles. It is the body that is expected to make use of them, and the prototype has no body at all. So these names may be blissfully omitted. That is, it is legal to write:
int gcd ( int , int ); int nextDigit ( int , int , int ); void printSqrt ( int );When you actually define the function, its header must faithfully match with the prototype found earlier.
Archiving C functions
Function prototypes are also useful during packaging of C functions in libraries. We explain the concept with an example. Assume that you are writing a set of useful tools to be used by foobarnautic scientists and engineers. The subject deals with two topics: foomatics and bargodics. You plan to write your foomatic functions in two files foo1.c and foo2.c, the first containing the basic tools and the second some advanced tools. For bargodics too you plan to write two C sources bar1.c and bar2.c. Later you realize that some bargodic topics are so advanced that they may better be called esoteric and should be placed in a third file bar3.c. All these five files have C functions, each meant for doing some specific job, like computing fooctorials, barnomial coefficients etc. However, none of these files should have a main function. A future user of your library will write the main function in her program, call your foobarnautic functions from her program and finally compile and run her program to unveil foobarnautic mysteries.
You first write the would-be useful functions in five files as mentioned above. You then compile each such file to an object file (not an executable file, since no file has a main).
cc -c -o foo1.o foo1.c cc -c -o foo2.o foo2.c cc -c -o bar1.o bar1.c cc -c -o bar2.o bar2.c cc -c -o bar3.o bar3.cFive object files foo1.o, foo2.o, bar1.o, bar2.o and bar3.o are obtained after successful compilation. You then join these object files to an archive (library):
ar rc libfoobar.a foo1.o foo2.o bar1.o bar2.o bar3.oThe archive command (ar) creates the library libfoobar.a. You may optionally run the following utility on this archive in order to add some book-keeping information in the archive:
ranlib libfoobar.aNow your library is ready. Copy it to a system directory if you have write permission there, else store it somewhere else, say, in the directory /tmp/foobar/lib.
Now when the future user plans to use your library, she simply compiles her program fooexplore.c (with main) as:
cc fooexplore.c -lfoobarif the library libfoobar.a resides in a system directory. If not, she should specifically mention the directory of the library and compile her program as:
cc fooexplore.c -L/tmp/foobar/lib -lfoobarBut... Something goes wrong, may be terribly wrong. Her compilation attempt issues a hell lot of warning messages. In fact, cc may even refuse to compile fooexplore.c. That was your fault, not the user's. You have missed to do some vital things. As soon as the frustrated programmer rings you up, you realize your fault. Now do the remaining things.
Create header files foo1.h, foo2.h, bar1.h, bar2.h and bar3.h. These files should contain only the following:
For example, foo1.h may look like:
- All new type definitions that you used in your library.
- All global variables and constants you used in your library.
- Prototypes of all functions defined in the library.
/************************************************************************** * foo1.h : Header file for basic foomatic utilities * * Created by : 04FB1331 Foolan Barik * * Last updated : January 08, 2005 * * Copyright 2005 by the Dept of Foobarnautic Engg, IIT Kharagpur, India * **************************************************************************/ /* Prevent accidental multiple #inclusion of this header file */ #ifndef _FOO1_H #define _FOO1_H /* New type definitions */ typedef unsigned long int fooint; typedef long double fooreal; typedef unsigned char foochar; ... /* Macros */ #define _FOO_BAR_TRUE 1 #define _FOO_BAR_FALSE 0 #define _FOO_BAR_PI 3.141592653589793238462643383 ... /* Global constants */ static const fooint foorams[8] = { 0xf00ba000, 0xf002ba00, 0xf0046ba0, 0xf008acba, 0xba0f0000, 0xba01f000, 0xba035f00, 0xba079bf0 }; ... /* Function prototypes. */ /* These functions are external to the user's programs. */ /* So use the extern keyword. */ extern fooint fooctorial ( fooint ) ; extern fooreal fooquation ( fooreal , fooint * , foochar ) ; ... #endifIf the source foo1.c contains these definitions, remove them from the C file and instead #include "foo1.h" towards the beginning of foo1.c. Do not define any function in a header file.
Do the above for all sources. Recompile your library, copy the new libfoobar.a once again to an appropriate directory.
Then choose a suitable directory for putting the headers. If you have permission to write in the system's include directory (usually /usr/include), create a directory foobar under this directory and copy your five header files to this new directory. If you do not have permission to write in /usr/include, create the directory /tmp/foobar/include and copy the header files there. Call back the user and notify her of these new developments.
The user then adds the following lines to her source code fooexplore.c.
#include <foobar/foo1.h> #include <foobar/foo2.h> #include <foobar/bar1.h> #include <foobar/bar2.h> #include <foobar/bar3.h>or#include "/tmp/foobar/include/foo1.h" #include "/tmp/foobar/include/foo2.h" #include "/tmp/foobar/include/bar1.h" #include "/tmp/foobar/include/bar2.h" #include "/tmp/foobar/include/bar3.h"depending on where you put the header files. Eureka! Her program now compiles and churns out unthinkably sublime foobarnautic data. She immediately rings you up again. You are afraid if any other thing went wrong. But you receive by your bewildered ears that she is thanking you profusely and inviting you for a tasty dinner in a posh downtown restaurant!
Built-in libraries
Well, you don't always have to write libraries. You can use libraries written by others. Think of the square root printer we have designed earlier. If you have to write every such basic function yourself, when will you write programs that solve your own problems?
Fortunately, many libraries are available in the standard C developer's distribution. Here we describe some of the most useful ones.
The math library
One useful library is the C math library. In order to use the library you should include the header file <math.h>. Do it after you include <stdio.h>. But that's not all. This inclusion makes accessible to your program only the function prototypes and some constant declarations. In order to link the function definitions you should also use the -lm flag during compilation time.
cc myMathHeavyProg.c -lmOnce you are given a library, the designer of the library should also specify in a document how to use the library, i.e., what new data types and constants are defined in it and what each function defined in the archive does. Here follows a high-level description of some useful mathematical functions defined in the C math library.
- double sqrt (double x);
- Returns the square root of the real number x.
- double pow (double x, double y);
- Returns the real number xy.
- double floor (double x);
- Returns the largest integer smaller than or equal to x.
- double ceil (double x);
- Returns the smallest integer larger than or equal to x.
- double fabs (double x);
- Returns the absolute value |x| of x.
- double exp (double x);
- Returns ex, where e = 2.7182818284... = 1+(1/1!)+(1/2!)+(1/3!)+... is the famous number you encountered in your calculus course.
- double log (double x);
- Returns the natural logarithm of x, i.e., the real logarithm of x to the base e.
- double log10 (double x);
- Returns the real logarithm of x to the base 10.
- double sin (double x);
double cos (double x);
double tan (double x);- The standard trigonometric functions. The argument should be specified in radians.
- double asin (double x);
double acos (double x);
double atan (double x);
double atan2 (double x, double y);- The inverse trigonometric functions. acos returns a value in the range [0,pi], asin and atan in the range [-pi/2,+pi/2], and atan2 in the range [-pi,+pi].
- double sinh (double x);
double cosh (double x);
double tanh (double x);- The standard hyperbolic trigonometric functions.
In addition to the above functions, math.h also defines the following useful constants:
#define M_E 2.7182818284590452354 /* e */ #define M_LOG2E 1.4426950408889634074 /* log_2 e */ #define M_LOG10E 0.43429448190325182765 /* log_10 e */ #define M_LN2 0.69314718055994530942 /* log_e 2 */ #define M_LN10 2.30258509299404568402 /* log_e 10 */ #define M_PI 3.14159265358979323846 /* pi */ #define M_PI_2 1.57079632679489661923 /* pi/2 */ #define M_PI_4 0.78539816339744830962 /* pi/4 */ #define M_1_PI 0.31830988618379067154 /* 1/pi */ #define M_2_PI 0.63661977236758134308 /* 2/pi */ #define M_2_SQRTPI 1.12837916709551257390 /* 2/sqrt(pi) */ #define M_SQRT2 1.41421356237309504880 /* sqrt(2) */ #define M_SQRT1_2 0.70710678118654752440 /* 1/sqrt(2) */The ctype library
Include the header <ctype.h> in order to access several character-related functions. You don't have to link any special library during compilation time. Many of these functions return Boolean values (true and false). However, C does not have a default Boolean data type. Here the Boolean value is returned as an integer (int) with the convention that 0 means "false" and any non-zero value means "true".
- int isalpha (int c);
- Returns true if and only if c is an alphabetic character ('A'-'Z' and 'a'-'z').
- int isupper (int c);
- Returns true if and only if c is an upper-case alphabetic character ('A'-'Z');
- int islower (int c);
- Returns true if and only if c is a lower-case alphabetic character ('a'-'z');
- int isdigit (int c);
- Returns true if and only if c is a decimal digit ('0'-'9');
- int isxdigit (int c);
- Returns true if and only if c is a hexadecimal digit ('0'-'9', 'A'-'F' and 'a'-'f').
- int isalnum (int c);
- Returns true if and only if c is an alphanumeric character ('A'-'Z', 'a'-'z' and '0'-'9').
- int isspace (int c);
- Returns true if and only if c is a white space character (space, tab, new-line, form-feed, carriage-return).
- int isprint (int c);
- Returns true if and only if c is a printable character (0x20-0x7e).
- int ispunct (int c);
- Returns true if and only if c is a printable character other than space, letter and digit.
- int isgraph (int c);
- Returns true if and only if c is a graphical character (0x21-0x7e).
- int iscntrl (int c);
- Returns true if and only if c is a control character (0x00-0x1f and 0x7f).
- int tolower (int c);
- If c is an upper-case letter, the corresponding lower-case letter is returned. Otherwise, c itself is returned.
- int toupper (int c);
- If c is a lower-case letter, the corresponding upper-case letter is returned. Otherwise, c itself is returned.
The stdlib library
The standard library may be included by including the header <stdlib.h>. No separate libraries need be linked during compilation time.
- int atoi (const char *s);
- Returns the integer corresponding to the string s. For example, the string "243" corresponds to the integer 243.
- long atol (const char *s);
- Returns the long integer corresponding to the string s. For example, the string "243576809" corresponds to the integer 243576809L.
- double atof (const char *s);
- Returns the floating point number corresponding to the string s. For example, the string "243576.809" corresponds to the floating-point number 2.43576809e05 (in the scientific notation).
- int rand ();
- Returns a random integer between 0 and RAND_MAX. In our lab RAND_MAX is 231-1.
- void srand (unsigned int s);
- Seed the random number generator by the integer s. A natural seed is the current system time. The following statement does this.
srand((unsigned int)time(NULL));In order to use the time function, you should #include <time.h>.
- int abs (int n);
- Returns the absolute value |n|of the integer n.
- long labs (long n);
- Returns the absolute value |n|of the long integer n.
- int system (const char *s);
- Passes the string argument s to be executed by the shell. For example, system("clear"); clears the screen.
Passing parameters
In C all parameters are passed by value. This means that for a call like
u = fooquation(x+y*z,&n,c);the arguments are first evaluated and subsequently the values are copied to the formal parameters defined in the function header:
long double fooquation ( long double x , unsigned long *p , unsigned char c ) { long double w; ... return(w); }During the call, the formal parameter x gets the value of the expression x+y*z, the pointer p gets the address of n and the formal parameter c obtains the value stored in the variable c during the time of the call. The formal arguments x,p,c are treated in fooquation as local variables. Any change in these values is not reflected outside the function. Thus the variables x,y,z,c in the caller function are unaffected by whatever fooquation does with the formal arguments x,p,c. The caller variable n is an exception. We didn't pass n straightaway to fooquation, we instead passed its address. So fooquation receives a copy of this address in its formal argument p. If the function modifies the pointer p, this does not change the address of n in the caller. However, fooquation may wish to write to the address passed to p. This modifies n, but not &n.
If you want to modify the value of some variable in a function, pass to the function a pointer to the variable.
Here is a failed attempt to swap the values of two variables:
void badswap ( int a , int b ) { int t; t = a; a = b; b = t; } int main () { int m = 51, n = 23; printf("m = %d, n = %d.\n", m, n); badswap(m,n); printf("m = %d, n = %d.\n", m, n); }The program prints:
m = 51, n = 23. m = 51, n = 23.The call of badswap produces no effect on m and n. In order to produce the desired effect, use the following strategy:
void swap ( int *ap , int *bp ) { int t; t = *ap; *ap = *bp; *bp = t; } int main () { int m = 51, n = 23; printf("m = %d, n = %d.\n", m, n); swap(&m,&n); printf("m = %d, n = %d.\n", m, n); }This time the program prints:
m = 51, n = 23. m = 23, n = 51.
Animation example : parameter passing in C
Now what should you do if you want to change a pointer? The answer is simple: pass a pointer to the pointer. How? We will give an answer to this new question later. Hold your patience.
Recursive functions
Recall that certain functions are defined recursively, i.e., in terms of itself. For example, consider the function F that maps n to the n-th Fibonacci number, i.e., F(n) = Fn. (In fact, every sequence is a function in a natural way.) We then have:
0 if n = 0, F(n) = 1 if n = 1, F(n-1) + F(n-2) if n >= 2.It is then tempting to write F as follows:
int F ( int n ) { if (n == 0) return (0); if (n == 1) return (1); return (F(n-1)+F(n-2)); }Does it work? The potential problem is: if F calls F itself with different parameter values, what would be the formal argument n for F. Every new invocation of F is expected to erase the old value of n. That would lead to error. In the above example, when F(n-1) returns, we have to make a second invocation F(n-2). Now if by this time the value of n has changed, we expect to get incorrect results. So what is the way out?
The answer is: there is no way out. In fact, there has not been any problem at all. The above function perfectly works.
Older languages like FORTRAN (designed in the 50's) used to face a problem, and there was again no way out. You cannot call a function from itself. That is, recursion was strictly prohibited.
C A R Hoare first proposed a way to work around with this problem. He introduced the concept of nests which we nowadays refer to as stacks. Every time a function is called, its formal parameters and local variables are pushed to the top of the call stack. In this way different invocations refer to different memory locations for accessing variables of the same name. When a function returns, its local data are popped out of the stack and control returns to the caller function for which variables reside in the current top of the stack.
The first high-level language that supported recursion was ALGOL. Most languages designed after that (late sixties onward) support recursion. C is no exception. In fact, the latest version of FORTRAN (FORTRAN 90) also supports recursion.
Animation example : recursive computation of Fibonacci numbers
Interactive animation : recursive computation of Fibonacci numbers
Here is another example: recursive computation of the factorial function.
int factorial ( int n ) { if (n < 0) return (-1); /* Error condition */ if (n == 0) return (1); /* Basis case */ return(n * factorial(n-1)); /* Recursive call */ }
Animation example : recursive computation of the factorial function
Interactive animation : recursive computation of the factorial function
Example: [Merge sort]
This is a very interesting recursive sorting technique. The array to be sorted is first divided in two halves of nearly equal sizes. Each half is then recursively sorted. Two sorted subarrays are then merged to form the final sorted list. Recursion stops when the array is of size 1. Such an array is already sorted.
The correctness of this algorithm can be established by the principle of strong mathematical induction. The base case (arrays of size 1) is obvious. For the inductive step, it suffices to prove that the merging routine correctly merges two sorted arrays. We leave out the details here.
Animation example : merge sort
Interactive animation : merge sort
Here is a recursive implementation of the merge sort algorithm. For simplicity, we work with a global array, so that we do not have to bother about passing the array as a function argument.
#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAXSIZE 1000 int A[MAXSIZE]; /* Function prototypes */ void mergeSort ( int, int ); void merge ( int, int, int ); void printArray ( int ); void mergeSort ( int i , int j ) /* i and j are the leftmost and rightmost indices of the current part of the array being sorted. */ { int mid; if (i == j) return; /* Base case: an array of size 1 is sorted */ mid = (i + j) / 2; /* Compute the mid index */ mergeSort(i,mid); /* Recursively sort the left half */ mergeSort(mid+1,j); /* Recursively sort the right half */ merge(i,mid,j); /* Merge the two sorted subarrays */ } void merge ( int i1, int j1, int j2 ) { int i2, k1, k2, k; int tmpArray[MAXSIZE]; i2 = j1 + 1; k1 = i1; k2 = i2; k = 0; while ((k1 <= j1) || (k2 <= j2)) { if (k1 > j1) { /* Left half is exhausted */ /* Copy from the right half */ tmpArray[k] = A[k2]; ++k2; } else if (k2 > j2) { /* Right half is exhausted */ /* Copy from the left half */ tmpArray[k] = A[k1]; ++k1; } else if (A[k1] < A[k2]) { /* Left pointer points to a smaller value */ /* Copy from the left half */ tmpArray[k] = A[k1]; ++k1; } else { /* Right pointer points to a smaller value */ /* Copy from the right half */ tmpArray[k] = A[k2]; ++k2; } ++k; /* Advance pointer for writing */ } /* Copy temporary array back to the original array */ --k; while (k >= 0) { A[i1+k] = tmpArray[k]; --k; } } void printArray ( int s ) { int i; for (i=0; i<s; ++i) printf("%3d",A[i]); printf("\n"); } int main () { int s, i; srand((unsigned int)time(NULL)); printf("Array size : "); scanf("%d",&s); for (i=0; i<s; ++i) A[i] = 1 + rand() % 99; printf("Array before sorting : "); printArray(s); mergeSort(0,s-1); printf("Array after sorting : "); printArray(s); }Here is a sample run of the program:
Array size : 20 Array before sorting : 21 74 40 94 78 75 58 91 11 7 86 77 76 20 45 56 94 32 90 51 Array after sorting : 7 11 20 21 32 40 45 51 56 58 74 75 76 77 78 86 90 91 94 94Example: [Quick sort]
Another recursive sorting technique is called the quick sort. For random arrays quick sort turns out to be one of the practically fastest sorting algorithms. Invented by C A R Hoare, this algorithm demonstrates the necessity for the facility of recursion in a high-level language. Inspired by this (and other) needs, Hoare himself wrote a commercial compiler for the language ALGOL 60.
Here we describe a simple version of the quick sort algorithm that employs auxiliary storage for partitioning the array. The idea is to choose a pivot, typically the first element of the array. All the remaining elements are partitioned into two collections, the first containing those array elements that are less than the pivot and the second containing the elements not less than the pivot. Then the original array is replaced by the smaller part followed by the pivot followed by the larger part. With this partitioning the pivot is now in the correct position. The smaller and larger parts are then recursively sorted by the quick sort algorithm. Once again the correctness of this algorithm can be rigorously established using the principle of strong mathematical induction.
Animation example : quick sort with extra storage
The complete implementation of the quick sort algorithm can be found here.
#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAXSIZE 1000 int A[MAXSIZE]; void quickSort ( int i , int j ) { int pivot; int leftArray[MAXSIZE], rightArray[MAXSIZE]; int lsize, rsize; int k, idx; if (i == j) return; pivot = A[i]; k = i; lsize = rsize = 0; /* Separate out the left and right parts */ while (k < j) { ++k; if (A[k] < pivot) leftArray[lsize++] = A[k]; else rightArray[rsize++] = A[k]; } /* Copy back the left part, the pivot and the right part to the original array */ k = i; for (idx=0; idx<lsize; ++idx) A[k++] = leftArray[idx]; A[k++] = pivot; for (idx=0; idx<rsize; ++idx) A[k++] = rightArray[idx]; if (lsize > 0) quickSort(i,i+lsize-1); /* Recursive call on the left part */ if (rsize > 0) quickSort(j-rsize+1,j); /* Recursive call on the right part */ } void printArray ( int s ) { int i; for (i=0; i<s; ++i) printf("%3d",A[i]); printf("\n"); } int main () { int s, i; srand((unsigned int)time(NULL)); printf("Array size : "); scanf("%d",&s); for (i=0; i<s; ++i) A[i] = 1 + rand() % 99; printf("Array before sorting : "); printArray(s); quickSort(0,s-1); printf("Array after sorting : "); printArray(s); }The partitioning of the array can be done in-place, i.e., without using extra storage. We won't go to the details here. The following animation implements quick sort with in-place partitioning.
Animation example : in-place quick sort
Recursion or iteration?
The divide-and-conquer algorithms like merge sort and quick sort give rise to a new genre of algorithm design and analysis techniques. Until recursion could be realized, implementing these algorithms was really non-trivial.
However, recursion is not really an unadulterated boon. To exemplify this issue, let us compare the performances of the iterative version of the Fibonacci number generation function and of the recursive version described above. Computation of Fn by the iterative version (using simple loops) requires n-1 additions and some additional overheads proportional to n.
But what about the recursive version? Let Sn denote the number of additions performed by the iterative method for the computation of Fn. We evidently have:
Sn = Define the sequence
Tn = Sn + 1 for all n = 0,1,2,...It follows that
Tn = Thus T0 = F1 and T1 = F2. By induction we then have Tn = Fn+1, i.e.,
Sn = Fn+1 - 1.If n = 25, we have Sn = 121392, whereas for n = 50, we have Sn = 20365011073. Compare these figures with the very small numbers (respectively 24 and 49) of additions performed by the iterative method. The reason for this poor performance of the recursive algorithm is that many Fi are computed multiple times. For example, Fn computes both Fn-1 and Fn-2, whereas Fn-1 also computes Fn-2. It is absolutely unnecessary to recompute the same value again and again. But unless we do something, we cannot eliminate this massive amount of multiple computations.
It is, therefore, often advisable to replace recursion by iteration. If some function makes only one recursive call and does nothing after the recursive call returns (except perhaps forwarding the value returned by the recursive call), then one calls this recursion a tail recursion. Tail recursions are easy to replace by loops: since no additional tasks are left after the call, no book-keeping need be performed, i.e., there is no harm if we simply replace the local variables and function arguments by the new values pertaining to the recursive call. This leads to an iterative version with the loop continuation condition dictated by the function arguments.
The factorial and Fibonacci routines that we presented earlier are not tail-recursive. The factorial routine performs a multiplication after the recursive call returns, and so it feels the necessity to store the formal parameter n. With the following implementation this need is eliminated. Here we pass to the recursive function an accumulating product.
int facrec ( int n , int prod ) { if (n < 0) return (-1); if (n == 0) return (prod); return (facrec(n-1,n*prod)); } int factorial ( int n ) { return (facrec(n,1)); }The straightforward iterative version of this is the following:
int faciter ( int n ) { int prod; if (n < 0) return (-1); prod = 1; /* Corresponds to facrec(n,1) */ while (n > 0) { /* Corresponds to the sequence of recursive calls */ prod *= n; /* Second argument in the recursive call */ n = n - 1; /* Change the formal parameter */ } return (prod); }For the Fibonacci number generator the following strategy reduces the overhead of recursion to something proportional to n. This function returns both Fn and Fn-1. But since a function cannot straightaway return two values simultaneously, the returning of Fn-1 is effected by pointers. Since the computation of Fn requires only two previous values, the efficient (linear) behavior is restored by the following recursive implementation.
int F ( int n , int *Fprev ) { int Fn_1, Fn_2; if (n == 0) { *Fprev = 1; return (0); } if (n == 1) { *Fprev = 0; return (1); } Fn_1 = F(n-1,&Fn_2); *Fprev = Fn_1; return (Fn_1+Fn_2); }This function is not tail-recursive, but that does not matter much. In the base case, it computes (F0,F1). From these values it computes (F1,F2), and from these the values (F2,F3), and so on. Eventually, we get (Fn-1,Fn) which contains the desired number Fn.
Interactive animation : fast recursive computation of Fibonacci numbers
In general, it is not an easy matter to replace recursion by iteration (or more ambitiously by tail-recursion). Whenever the replacement idea is intuitive and straightforward, one may go for it. After all, recursion has some overheads. In most cases, however, we have to look more deeply into the structure of the problem in order to devise a suitable iterative substitute. Memoization and dynamic programming techniques often help. But these topics are too advanced to be dealt with in this introductory course.
Now here is again an obfuscated code for you. Determine what the following function computes. Express the return value as a function of the input integer n. Assume that n >= 0.
int foo ( int n ) { int s = 0; while (n--) s += 1 + foo(n); return s; }