C Programming - Functions (Part-I) Page - 3

Page 3 of 3

Author: Brian Moriya Published on: 23rd May 2006 | Last Updated on: 22nd Jul 2011

C Programming - Functions (Part-I)

Recursion

Recursion is a powerful tool that can really simplify your code if you find that you have a problem that can be solved by using it. A recursive function is one that calls itself one or more times. One example of recursive functions is operations on binary trees. Binary trees are an advanced data structure, but all operations on them are considered recursive in nature. Traversing linked lists is another recursive problem, but linked lists too are an advanced topic.

Ads

Recursion is a powerful tool, but it takes a lot of careful planning so it can be difficult to implement, and many programmers will simply pass it up because of this. In order to successfully implement a recursive function, you must identify one or more exit conditions for stopping the recursive calls. If you do this wrong, your code will enter an endless loop and cause a stack overflow because of all the function calls.

Recursion is never necessary, and many never use it in practice because of the time it takes to design the problem is often longer than just coding it iteratively. In these days where agile development is king, time is everything. It is still good to know in case you do come across a problem recursive in nature, or see it in somebody else's code.

Most examples of recursion are rather contrived, and to be honest this programmer has never used it in C (Python yes, C no) since learning it in college. Calculating factorials, tower of Hanoi, and the Sieve of Eratosthenes are common ones for explaining recursion without going into too advanced of concepts. Calculating factorials is simple enough to explain the concept so we are going to write a very quick sample to do just that.

You may remember the definition of factorials from math courses, you may not. The point to take home is that the recursive function calc_factorial in calc_factorial.c calls itself until the base case is resolved and it returns 1 instead of n – 1.

calc_factorial.c:

Sample Code

#include <stdio.h>
int calc_factorial(int n);
int main() {
int i; int n_values[5] = {1, 2, 5, 3, 9}; int factorials[5];
for (i = 0; i < 5; i++) { factorials[i] = calc_factorial(n_values[i]);
}
for (i = 0; i < 5; i++) { printf("Factorial of %d is %d", n_values[i], factorials[i]); printf("n");
}
}
int calc_factorial(int n) {
int n_minus_one; int next_n;
//Base case for exiting the recursion is a value of 1.
if (n <= 1) {
return 1;
} else {
//Otherwise return the next iteration's n value. n_minus_one = n - 1; next_n = n * calc_factorial(n_minus_one);
return next_n;
}
}

Here is the output of calc_factorial:

Multi-File Programs

All but the most simple programs written in C will have multiple source files. There are two types of source files in C, header files and implementation files.

Header files are where all your function prototypes, global variables, constants, and the like goes. You have been using header files all along; stdio.h, for example. Header files use the .h extension and are accessed by your implementation files by #include statements. At compile time, #include essentially sticks the header file where you use it in your program so you can access anything that was declared in the header file, right in your program as though you had typed it there.

Implementation files are where you put the function definitions, and actually "do stuff." Basically all the stuff from our examples so far from the end of the main function to the end of the file is what goes into an implementation file, and what is above main goes into a header file. Usually main will go into it is own source file called main.c.

Lets turn our printxy example into a simple multi-file C program.

printxy.h:

Sample Code

#ifndef _PRINT_XY_
#define _PRINT_XY_
void printxy(int x[], int y[]);
#endif

We move just our function prototypes into printxy.h. If we were still using x and y globally we would move them here as well. The #ifndef, #define, and #endif are macros that make sure we do not have problems with redeclaring functions or variables when multiple source files try to use the same header files.

#ifndef checks if the token has been declared someplace else. The token is whatever you want it to be. Conventionally it uses the underscore and capital naming style you see above. Naming it after your header file name is the most common way to decide on the token.

So if #ifndef does not find that token anyplace else, it will define it using the #define statement. Use #define to actually set your token.

#endif simply goes at the end of what code you want to be protected under the umbrella of your token. It does not necessarily have to go at the end of the file.

printxy.c:

Sample Code

#include <stdio.h>
#include "printxy.h"
void printxy(int x[], int y[]) { int i = 0;
for (i = 0; i < 3; i++) {
printf("value of x: %d, ", x[i]);
printf("value of y: %d", y[i]);
printf("n");
}
}

Our implementation file is where we move our definition of the printxy function to. We must not forget to include our new header file. We used the " " instead of < > because it is not a built-in standard header, it is defined right here in the program. That was not so hard, was it?

main.c:

Sample Code

#include "printxy.h"
int main(int argc, char *argv[]) {
int x[3], y[3]; int i;
for (i = 0; i < 3; i++) { x[i] = i; y[i] = 10;
}
printxy(x, y);
for (i = 0; i < 3; i++) { x[i] += y[i];
}
printxy(x, y);
for (i = 0; i < 3; i++) { y[i]++;
} printxy(x, y);
return 0;
}

Finally our main function is alone in its own file. Easy to find by maintainers and yourself if your program grows to many source files. Now all our main has to import is the printxy.h header file. That is really the only difference from before, besides the deletion of the printxy prototype and definition.

You might be thinking this seems like more trouble than it is worth. You are right, for this program. Try to imagine a program with 10 or more header and source files. Probably scares you, but that is because I have not told you the best part yet. You only put code that relates to eachother into header files together.

You come up with some sort of grouping for them before breaking them up. Print functions in one header, math functions in another, input-getting functions in another, or both input and output like stdio. Whatever you want, those are just some ideas. It really does make things easier to maintain, especially if you use descriptive names. Just make sure your header and corresponding implementation files have matching names like we did here.

Ads

When compiling these multi-file programs from the command-line, you just list all the files instead of the one file like before. I use gcc, I do not know how to use any others so I will use that as an example. I will show you how I compile printxy1.c and how I compile this multi-file version using gcc.

1 file:

Sample Code