C - From The Top (part 7)

Functions 2 & Recursion

We have already seen what functions do, but how are they made up?

A function prototype looks like this:

The prototype enables the compiler to know what data type is returned and sent to the function and allocate that amount of space for it (remember, different return and variable types require a different amount of memory). If you don't define the return type, int is assumed. This is fine for a void and int function, but will mess things up if it's a double!

While the compiler can, in general, convert from one function type to another, some it can't (for instance, an int to pointer conversion). The prototype enables this sort of error to be caught.

One drawback is, if you use a multiple file source code (more of this later), the compiler won't catch them.

Owing to the fact that C has been around for ages, but wasn't standardised until 1989, prototypes don't need to be used. This is to maintain backwards compatibility. You still need to say what the return type is, but not the prototypes.

The old style declaration looks like this

double amount();
(code)
double amount(double s1, double s2, double s3)
{
 return s1+s2*s3;
}

as you can see, the function itself defines the prototype and not the declaration at the beginning of the code. The big problem with not declaring the prototypes in the formal declaration at the start is that the function itself can be sent the wrong number of parameters and the compiler won't generate an error telling you of this. This type of declaration is known as the forward declaration.

Problems caused by standardisation

This did cause problems when C was standardised. The first was how to get around the old declarations not having a parameter list. This was simply done by the compilers saying that if nothing is there, nothing can be done about it! There may be parameters, but there may not.

It didn't solve the problem though. Suppose you had the following piece of code using the forward declaration.

void dotted_line()
{
 int i;
 for (i=0; i<80; i++) printf(".");
}

This will do absolutely nothing, though it is supposed to print a line of dots. It's not down to the old style declaration though.

What was needed is the void statement. This explicitly tells the compiler that there are no arguments and anything calling this function with arguments is wrong. The code's first line should be:

void dotted_line (void)

The second problem comes when C performs an automatic type promotion.

This is when a char is converted to an int, and float to a double. Without the type declarations, this can occur. However, with the declarations made, the automatic type promotions are not made.

The final point to note is that it is possible to make a variable length argument list. This follows the form

int funct (int a, ... );

This specifies the function funct with one int parameter and a variable number of parameters. This can be very useful! Take printf and scanf; both normally have two arguments (say %d and &var). The actual protocol for printf is

int printf(const char * , ...);

the const char * is just the likes of %d; however, it can have as many arguments as you'd like it to have, and that is down to the ... preceding the brackets.

There is only one function without a prototype: main. main is normally given one of two return types: void and int. void is used when the function returns no values.

Call by value and reference

In languages like Basic, arguments can be passed to the subroutines in one of two ways: call by value and call by reference.

Call by value copies the value passed over into the formal parameter of the subroutine, e.g.

PROCdosomething(1001)
:
:
DEFPROCdosomething(a%)

Changes made to the parameter have no effect on the argument (the 1001) used to call it with.

Call by reference is when the address of the argument is copied across to a parameter. The subroutine uses this address to access the argument. Changes made will then affect the original argument.

C uses call by value as the default, but you have already seen that, by the use of pointers, call by reference can be used. I'm going to use a very nice piece of code here to demonstrate this point.

#include <stdio.h>
void swap (int *i, int *j);
int main(void)
{
 int num1, num2;
 num1=100;
 num2=800;
 printf("num1 : %d, num2 : %d\n",num1,num2);
 swap(&num1,&num2);
 printf("num1 : %d, num2 : %d\n",num1,num2);
 return 0;
}
void swap(int *i, int *j)
{
 int temp;
 temp=*i;
 *i=*j;
 *j=temp;
}

This routine passes over two integer pointers and swaps them around.

Sending arrays to a function

Sending an array across a function can be done in one of three ways, but the function declaration will look different.

You can use

void func_1(int num[5]);
void func_2(int num[]);
void func_3(int *num);

Even though the declarations look different, the routines are the same. Take a look at this :

#include <stdio.h>
void f1(int num[5]), f2(int num[]), f3(int *num);
int main(void)
{
 int numbers[5]={2,4,6,8,10};
 f1(numbers);
 f2(numbers);
 f3(numbers);
 return 0;
}
void f1(int nos[5])
{
 int loop;
 for (loop=0;loop<5;loop++)
 printf("%d ",nos[loop]);
}
void f2(int nos[])
{
 int loop;
 for (loop=0;loop<5;loop++)
 printf("%d ",nos[loop]);
}
void f3(int *nos)
{
 int loop;
 for (loop=0;loop<5;loop++)
 printf("%d ",nos[loop]);
}

The outcome is the same no matter what you do, but the f3 function is the more efficient - it passes over an address, not the array.

Recursion

Recursion is when a function calls itself until a condition is met.

For instance, the following code prints 9 to 0 by the use of a recursive function.

#include <stdio.h>
void recurse(int i);
int main(void)
{
 recurse(0);
 return 0;
}
void recurse(int i)
{
 if (i<10)
 {
  recurse(i+1);
  printf("%d ",i);
 }
}

What happens though?

The function recurse is first passed 0. Obviously this is less than 10, so the function is called again with the original number + 1 (so it's now 1). This keeps going until recurse is passed with the number 10. This causes it to return to its previous calling and prints the number 9. recurse then starts calling backwards until 0 is reached (the original call). When this is reached, the function returns to the calling routine and the program terminates.

The recursion can be thought of here as a spiral staircase. Once you've hit stair 10, you've got to come down to stair 9, then 8 and so on until you're back at the bottom of the stairs.

There is a single problem with a recursive call, and one you may have encountered with some programs. All values are stored on something called the stack. When the recursion is called, all parameters and local variables are stored there. This may seem like no great shakes, but think about it this way. Inside the recursion is an if statement. Without this, the recursion will just go mad and use up all the memory and the program will crash. When this happens, you get the ubiquitous "internal error; no room on stack". report - and don't we just love seeing that pop up from time to time!

Recursion can be used to copy strings as well. The following does it.

#include <stdio.h>
void rcopy(char *s1, char *s2);
int main(void)
{
 char string[80];
 rcopy(string,"this is a nice test!");
 printf(string);
 return 0;
}
void rcopy(char *s1, char *s2)
{
 if (*s2)
 {
  *s1++ = *s2++;
  rcopy(s1,s2);
  }
 else *s1='\0';
}

This works by assigning the character pointed to by s2, to that pointed to by s1, then incrementing the pair. This carries on until the end of s2 is reached (this is what the if (*s2) line does). The null terminator is then added onto the end of s1 to tell the program where s1 ends (or in more literal terms, where string ends).

While recursion is fun, it does take a long time to execute, and an iterative function is often likely to be more efficient.

Recursion can work across functions as well. Take, for instance, this example:

#include <stdio.h>
void f1(int a),f2 (int b);
int main(void)
{
 f1(30);
 return 0;
}
void f1(int a)
{
 if (a) f2(a-1);
 printf("%d ",a);
}
void f2(int b)
{
 printf(".");
 if (b) f1(b-1);
}

This will display the following

...............0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

Why? I'll let you puzzle that one out!

Next time, using the filing system.


Source: Archive Magazine 13.7
Publication: Archive Magazine
Contributor: Paul Johnson